Modern organisations rely intensively on information and communication technology infrastructures. Such infrastructures oer a range of services from simple mail transport agents or blogs to complex e-commerce platforms, banking systems or service hosting, and all of these depend on distributed systems. The security of these systems, with their increasing complexity, is a challenge. Cloud services are replacing traditional infrastructures by providing lower cost alternatives for storage and computational power, but at the risk of relying on third party companies. This risk becomes particularly critical when such services are used to host privileged company information and applications, or customers' private information. Even in the case where companies host their own information and applications, the advent of BYOD (Bring Your Own Device [48]) leads to new security related issues.

In response, our research investigated the characterization and detection of malicious activities at the operating system level and in distributed systems composed of multiple hosts and services.

We have shown that intrusions in an operating system spawn abnormal information ows, and we developed a model of dynamic information ow tracking, based on taint marking techniques, in order to detect such abnormal behavior. We track information ows between objects of the operating system (such as les, sockets, shared memory, processes, etc.) and network packets owing between hosts. This approach follows the anomaly detection paradigm. We specify the legal behavior of the system with respect to an information ow policy, by stating how users and programs from groups of hosts are allowed to access or alter each other's information. Illegal information ows are considered as intrusion symptoms. We have implemented this model in the Linux kernel 4 , as a Linux Security Module (LSM), and we used it as the basis for practical demonstrations. The experimental results validated the feasibility of our new intrusion detection principles.

Résumé en Français

Les systèmes d'information actuels, qu'il s'agisse de réseaux d'entreprises, de services en ligne ou encore d'organisations gouvernementales, reposent très souvent sur des systèmes distribués, impliquant un ensemble de machines fournissant des services internes ou externes. La sécurité de tels systèmes d'information est construite à plusieurs niveaux (défense en profondeur). Lors de l'établissement de tels systèmes, des politiques de contrôle d'accès, d'authentication, de ltrage (rewalls, etc.) sont mises en place an de garantir la sécurité des informations. Cependant, ces systèmes sont très souvent complexes, et évoluent en permanence. Il devient alors dicile de maintenir une politique de sécurité sans faille sur l'ensemble du système (quand bien même cela serait possible), et de résister aux attaques auxquelles ces services sont quotidiennement exposés.

C'est ainsi que les systèmes de détection d'intrusions sont devenus nécessaires, et font partie du jeu d'outils de sécurité indispensables à tous les administrateurs de systèmes exposés en permanence à des attaques potentielles.

Les systèmes de détection d'intrusions se classient en deux grandes familles, qui dièrent par leur méthode d'analyse: l'approche par scénarios et l'approche comportementale. L'approche par scénarios est la plus courante, et elle est utilisée par des systèmes de détection d'intrusions bien connus tels que Snort [START_REF] Roesch | Snort -lightweight intrusion detection for networks[END_REF], Prélude [START_REF] Zaraska | Prelude ids: current state and development perspectives[END_REF] et d'autres. Cette approche consiste à reconnaître des signatures d'attaques connues dans le trac réseau (pour les IDS réseau) et des séquences d'appels systèmes (pour les IDS hôtes). Il s'agit donc de détecter des comportements anormaux du système liés à la présence d'attaques. Bien que l'on puisse ainsi détecter un grand nombre d'attaques, cette approche ne permet pas de détecter de nouvelles attaques, pour lesquelles aucune signature n'est connue. Par ailleurs, les malwares modernes emploient souvent des techniques dites de morphisme binaire, an d'échapper à la détection par signatures. L'approche comportementale, à l'inverse de l'approche par signature, se base sur la modélisation du fonctionnement normal du système. Cette approche permet ainsi de détecter de nouvelles attaques tout comme des attaques plus anciennes, n'ayant recours à aucune base de données de connaissance d'attaques existantes. Il existe plusieurs types d'approches comportementales, certains modèles sont statistiques, d'autres modèles s'appuient sur une politique de sécurité.

Dans cette thèse, on s'intéresse à la détection d'intrusions dans des systèmes distribués, en adoptant une approche comportementale basée sur une politique de sécurité. Elle est exprimée sous la forme d'une politique de ux d'information. Les ux d'informations sont suivis via une technique de propagation de marques (appelée en anglais taint marking ) appliquées sur les objets du système d'exploitation, directement au niveau du noyau. De telles approches existent également au niveau langage (par exemple par instrumentation de la machine virtuelle Java, ou bien en modiant le code des applications) [START_REF] Myers | A decentralized model for information ow control[END_REF][START_REF] Myers | Protecting privacy using the decentralized label model[END_REF] ou encore au niveau de l'architecture [START_REF] Vachharajani | Rie: An architectural framework for user-centric information-ow security[END_REF][START_REF] Zeldovich | Hardware enforcement of application security policies using tagged memory[END_REF] (en émulant le microprocesseur an de tracer les ux d'information entre les registres, pages mémoire etc.), et permettent ainsi une analyse ne des ux d'informations. Cependant, nous avons choisi de nous placer au niveau du système d'exploitation, an de satisfaire les objectifs suivants:

• Détecter les intrusions à tous les niveaux du système, pas spéciquement au sein d'une ou plusieurs applications.

• Déployer notre système en présence d'applications natives, dont le code source n'est pas nécessairement disponible (ce qui rend leur instrumentation très dicile voire impossible).

• Utiliser du matériel standard présent sur le marché. Il est très dicile de modier physiquement les microprocesseurs, et leur émulation a un impact très important sur les performances du système.

Vue d'ensemble

Nous avons ainsi étendu un modèle de propagation de marques, en nous appuyant sur des techniques existantes, issues de précédents travaux au sein de l'équipe CIDre. Ensuite, ce modèle de propagation a été implémenté via la réalisation d'un prototype. Ce nouveau modèle permet de prendre en compte les spécicités du suivi de ux d'information dans un système d'exploitation de type Unix, mais peut aussi être utilisé dans des environnements distribués. Ce modèle attache des marques (ou tags ) aux objets du système d'exploitation, dans le but de suivre leur propagation tout au long de la vie du système. Les objets tels que les chiers, les processus et les sockets réseau sont ainsi marqués par chaque ux d'information. Nous avons implémenté ce modèle dans le noyau Linux, en tant que module de sécurité. La conception et l'implémentation de ce modèle représentent la première contribution de cette thèse. Nous avons publié et présenté ce modèle lors de la conférence internationale ICC 2011 (IEEE International Conference on Communications) [START_REF] Geller | Information ow control for intrusion detection derived from mac policy[END_REF].

Nous avons ensuite étendu ces travaux an de prendre en considération les ux d'information sur le réseau. Cette extension du modèle permet de dénir une politique réseau an de contrôler les interactions autorisées entre les applications ou utilisateurs vis à vis de l'information surveillée.

Cette politique dénit d'une part quelles informations sont autorisées à quitter le système via le réseau, et d'autre part dans quelles conditions de nouvelles informations, arrivant par le réseau depuis des sources connues ou inconnues, sont autorisées à se mélanger avec des informations existantes sur le système surveillé. Cette politique est dénie de manière globale au système. Les règles qui concernent l'information sortante protègent la condentialité des données, tandis que les règles qui concernent l'information entrante protègent leur intégrité. La possibilité de dénir une telle politique pour protéger des données privées ore de nouvelles solutions quant à la détection de violations de la vie privée ou au vol d'informations personnelles. Cette seconde contribution a été publiée et présentée lors de la conférence internationale AISC 2012 (Australasian Information Security Conference) [START_REF] Tronel | A taint marking approach to condentiality violation detection[END_REF].

Enn, notre dernière contribution concerne la généralisation du précédent modèle à la détection d'intrusions en environnement distribué. En prenant de multiples machines (que nous réunissons en groupes de machines) en considération, il devient possible de dénir une politique adaptée à des systèmes plus complexes, tout en gardant une approche à grain n, c'est à dire en conservant une spécication ne de la politique. Une telle politique est dénie à l'échelle d'un groupe de machines.

Elle est distribuée au sein de chaque machine du groupe, et dénit les interactions autorisées entre processus de machines diérentes, ainsi qu'entre processus locaux. Cette dernière contribution a donné lieu à une publication, qui a été acceptée et présentée lors de la conférence internationale ICC 2013 [START_REF] Hauser | Distributed intrusion detection, an approach based on taint marking[END_REF].

Modèle de détection

Notre modèle de détection fait intervenir des marques appelées tags an de suivre les ux d'information entre objets du système d'exploitation surveillé. Ces objets sont considérés comme conteneurs d'information, et à tout moment, nous souhaitons pouvoir déterminer le contenu de chaque objet an de vérier qu'il correspond à un état normal du système. La spécication de cet état normal, ou contenu normal, se fait via une politique de sécurité. Cette politique dissocie les données passives du code actif des applications: le code d'une application est considéré comme passif lorsqu'il est stocké dans un chier, mais il est considéré comme actif lorsque qu'il est en cours d'exécution.

Cette distinction nous permet d'exprimer nement la politique de sécurité. Nous considérons ainsi comme étant de l'information tout élément passif (donnée ou code stockés) ou actif (code en cours d'exécution).

La dénition de la politique ainsi que le suivi de ux d'informations font intervenir quatre types de tags :

• Les tags d'information, ou information tags, décrivent le contenu des objets (ou conteneurs ) auxquels ils sont attachés, à tout instant. Ils contiennent des meta-informations, permettant de décrire individuellement chaque élément d'information.

• Les tags de politique, ou policy tags, décrivent la politique des objets auxquels ils sont attachés. Ils décrivent quelles sont les combinaisons légales d'information que ces objets peuvent contenir. Toute déviation vis à vis de cette politique indique un comportement anormal du système.

• Les tags de politique d'exécution, ou execute policy tags, décrivent le comportement légal des processus résultant de l'exécution de code marqué. Ils sont attachés aux chiers exécutables.

Ces tags ne sont utilisés qu'au moment de l'exécution, an de déterminer les tags de politique des processus.

• Le tag de politique réseau, ou network policy tag, détermine les interactions légales entre processus et données vis à vis du réseau. Il détermine quels processus (en se basant sur la marque du code exécuté) peuvent légalement recevoir ou envoyer quelles informations à quels autres processus distants, au sein d'un système distribué. Il n'existe qu'un seul tag de politique réseau par machine, celui-ci dénit toutes les interactions légales entre processus, information et réseau.

Ce modèle a été implémenté dans le noyau Linux, sous la forme d'un module de sécurité. Nous suivons les ux d'information entre les chiers, les sockets réseau, les zones de mémoire partagée, les les de messages, les inodes etc. Cette implémentation utilise des mécanismes standard du noyau, et les opérations complexes utilisent des structures de données optimisées an de limiter l'impact sur les performances. Le code a été testé sur plusieurs architectures, et a été reporté comme fonctionnel sur la plateforme Android.

Résultats expérimentaux

Les travaux réalisés au sein de cette thèse ont été vériés expérimentalement dans plusieurs cas de gure. Outre les tests de validation de l'implémentation vis à vis du modèle mis en ÷uvre, nous avons réalisé deux scénarios correspondant à des cas d'utilisation réels d'un système de détection d'intrusions. Dans le premier cas, les attaques contre la condentialité ont été visées. Ce premier scénario met en ÷uvre une attaque contre le navigateur web Firefox 1 , en utilisant une version vulnérable du plugin Java Nous avons ainsi déployé une politique de sécurité décrivant le comportement légal des processus composant le service distribué, localement sur chaque système ainsi que sur le réseau lors de leurs communications. Cette politique autorise le serveur web ainsi que le serveur de bases de données à traiter des requêtes concernant un seul des deux sites web à la fois. Ceci est rendu possible par le fait que, Apache et PostgreSQL créent un nouveau processus pour traiter chaque connexion, et en aucun cas les informations des deux sites ne sont mélangées lorsque le système fonctionne normalement. L'attaque que nous avons déployée injecte un script PHP contenant du code malveillant, en utilisant la vulnérabilité présentée précédemment, sur le site public (seul site accessible depuis l'extérieur).

L'attaquant a ainsi la main sur le processus en question, et peut désormais eectuer des requêtes concernant le second site web. Dès lors qu'il eectue une telle requête, le processus attaqué, qui jusqu'alors était marqué avec des informations du site web public, se voit également marqué avec des informations du site web privé, et viole ainsi la politique de sécurité. Une alerte est levée sur la machine locale (le serveur web), et toute connexion entre le processus infecté et un processus d'une autre machine supervisée provoque la contamination de ce dernier, levant ainsi des alertes sur les autres machines.

Évaluation

Une évaluation de notre modèle et de son implémentation est présentée en conclusion du chapitre 8.

En terme de performances, notre implémentation ajoute une pénalité maximale de 30% en terme de consommation mémoire, et de 40% en terme de consommation CPU. Le temps maximal d'exécution de certaines opérations peut également s'élever à 300% dans des conditions extrêmes, limite dûe à une utilisation excessive du système de chier, que l'on estime aisément contournable à l'aide d'optimisations (présentées dans la section 7.8).

L'évaluation de systèmes de détection d'intrusions fait généralement intervenir la notion de taux de faux positifs et de faux négatifs. Par conception, notre approche est conservatrice et surapproxime à tout moment la quantité d'information impliquée dans les ux d'informations.

Ceci a pour eet de limiter très fortement la présence de faux négatif, qui à l'exception de canaux cachés ou de défauts dans la dénition de la politique de sécurité, sont considérés comme inexistants dans notre système. Par ailleurs, le taux de faux positifs est directement lié à la précision avec laquelle nous observons les ux d'information. Nous identions ainsi deux cas de gure: les cas où nous sommes contraints d'eectuer une forte surapproximation, par exemple lors de l'utilisation de mémoire partagée entre plusieurs processus, et les cas où nous eectuons une surapproximation plus modérée. Dans le premier cas, un grand nombre de faux positifs est généré, rendant dicile l'utilisation de notre système. Ceci est dû au niveau d'abstraction auquel nous nous plaçons dans le système. Depuis le noyau, il est impossible d'observer de façon exacte les accès à la mémoire eectués par les applications. Il s'agit de la principale limitation de notre approche, et nous envisageons plusieurs solutions an d'aner l'analyse des ux. Dans le second cas, la précision de notre analyse est plus ne, et nous sommes ainsi capables de détecter les intrusions avec un faible taux de faux positifs. Ces aspects sont présentés plus en détails dans la section 8.4 de ce manuscrit.

Nous avons ainsi mis en ÷uvre et implémenté un modèle de détection d'intrusions au niveau noyau, capable de détecter les intrusions aussi bien dans des machines isolées, qu'au sein de systèmes distribués. La mise en ÷uvre d'expérimentations nous a permis de valider notre approche de détection, et d'identier ses limitations. Des travaux en cours au sein de l'équipe CIDre s'appuient sur notre travail, et ont pour objectif de mettre en ÷uvre des mécanismes de coopération entre des moniteurs de suivi de ux à plusieurs niveaux (niveau langage et niveau système d'exploitation), visant ainsi un anement du suivi de ux an de réduire les taux de faux positifs.

Cette thèse est organisée de la manière suivante: la première partie, composée des deux premiers chapitres, présente le contexte de recherche dans lequel notre travail s'inscrit. Le chapitre 1 introduit les fondements de notre approche, ainsi que les travaux précédents existants dans la littérature. Le chapitre 2 compare la base de notre modèle avec les modèles classiques de contrôle d'accès et de contrôle de ux d'information.

La seconde partie de cette thèse présente notre première contribution. Le chapitre 3 détaille notre modèle de détection d'intrusions, et le chapitre 4 présente son implémentation.

Enn, la dernière partie de cette thèse présente l'extension de notre modèle au réseau et aux sys-tèmes distribués, dans les chapitres 5 et 6, suivie de nos résultats expérimentaux dans le chapitre 8.

Contents

Introduction

Over the last decade, the huge development of internet and home networks led to new online services, social networks and online mass market. Information systems have been expanded to t more and more users with increasing data volumes. This made distributed systems very common and widely used. Nowadays, popular services store large amounts of user data online, in the cloud. It is thus desirable that the underlying systems oer good security properties. Such security properties have to be dened and implanted into each system component through a security policy.

This is dened as a set of rules specifying how the system is authorized to manage information, i.e., what is legal within the system in terms of information and operations. Existing mechanisms have been designed to implant such policies, such as access control and rewalls. However, these are very dicult to maintain in complex growing environments, where perpetual bug xes in software development make evasion possible for potential attackers.

As a result of this, intrusion detection systems (IDSes) have become a necessary addition to the security infrastructure of nearly every organization. IDSes typically record information from observed events and notify the system administrators when possibly illegal events occur. Most of the current approaches focus on misuse detection, by detecting patterns of abnormal behavior of the monitored system, i.e., these are based on learned proles or signatures of known attacks.

Such approaches generally generate a high number of false positives, making it dicult for system administrators to successfully identify real attacks. Furthermore, these systems are not able to detect previously unseen attacks also known as zero day attacks. An alternative approach to misuse detection is anomaly detection, describing deviations from an established normal state of the monitored system.

The aim of this research is to investigate the characterization and detection of malicious activities at the operating system level and in distributed systems composed of groups of hosts. Our approach follows the anomaly detection paradigm. It is based on a security policy describing the legal behavior of the system, an approach also known as policy-based intrusion detection. Detection of illegal activity is done by tracking information ows within the operating system and between

hosts. An information ow policy denes the legal behavior of the system, by determining where information is allowed to ow, and which users or programs are allowed to access it. Any violation of this policy is considered as a symptom of intrusion, and raises an alert.

In order to achieve these goals, we have rst designed and implemented a model of taint marking, labeling objects of the operating system with tags, so as to track their content by propagating taint data. Objects such as les, sockets and processes, amongst others, are tainted. It was implemented in the Linux kernel as a Linux security module. The design and implementation of this model represents our rst contribution.

The consideration of network aspects, such as the policy regarding network interaction of applications, users and containers of information (e.g., les, memory pages, etc.), represents our second contribution. This includes an extension of our model and implementation so as to take network sockets and packets into consideration. We introduced a network policy, dening the legality of information ows involving outgoing data, in terms of condentiality, and incoming new data, in terms of integrity. It denes how new and possibly untrusted data is allowed to mix with data already present in the system. Specifying such a policy for e.g., private user data oers a novel solution for tracking privacy violations caused by applications.

Finally, our last contribution is the generalization of this approach in order to detect intrusions in distributed systems. Taking multiple hosts into account (we gather hosts in groups, in which each host is aware of the others), allows us to specify a distributed policy suitable for larger systems, while keeping a high granularity. Such a policy is distributed at the host level in each group, and denes the legal interactions between processes running on dierent hosts. It states how pieces of authorized information may be accessible by applications and users from any given host of a group.

The model and implementation that we present in this thesis focus on the condentiality and integrity aspects of information. Attacks against availability are not covered by our approach.

We only use o-the-shelf components on commodity hardware, and the only trusted code is our modied operating system kernel.

The reminder of this thesis is organized as follows. The rst part introduces the context of this research. It rst presents the necessary background in terms of access control, rewalls and information ow control. After this, related work in the eld is reviewed and compared to our approach. The second part focuses on intrusion detection in isolated hosts. It presents our model of intrusion detection based on taint marking and its implementation. The last part presents the extensions of our model and implementation to detect intrusion detection in network and distributed environments, as well as our experiments and results.

Chapter 1

Background and Related Work

This Ph.D. project focuses on detecting intrusions at the operating system kernel level, based on an information ow tracking model implemented on top of access control mechanisms (the Linux Security Modules). These three aspects are central to our approach, therefore, this chapter provides an overview of the background literature in these elds. Access control is rst introduced, opposing traditional discretionary access control coming as standard with most operating systems, with mandatory access control as implemented in SELinux amongst others. Classic information ow control models are then introduced, followed by modern decentralized approaches as well as related work in terms of information ow tracking and taint marking. Finally, an overview of existing research in the eld of intrusion detection is presented.

Traditional security mechanisms

When it comes to secure information systems, rewalls and access control provide basic security by enforcing OS and network level security properties. These are available in most if not all operating systems. The rst part of this chapter is dedicated to these mechanisms, and highlights their shortcomings with respect to the problem we aim to address.

Firewalls

Firewalls are devices or software that lter network trac at dierent layers of the ISO network model. They can be set up to restrict access to a personal machine or a company's network from other untrusted networks, thus creating trust boundaries [START_REF] Ingham | A History and Survey of Network Firewalls[END_REF]. Individuals can use software rewalls on their personal/portable computers to dene and enforce policies concerning both incoming and outgoing network trac.

Deep Packet Inspection (DPI) rewalls identify anomalous patterns in trac volumes by inspecting both the headers and content of packets. They provide the capability of identifying anomalous network trac as well as managing normal trac. They also form the core of many commercially-available rewalls and intrusion detection systems (IDS). Tamer et al. [1] present a survey of the Deep Packet Inspection algorithms, implementation techniques, research challenges and their usage in several existing technologies for intrusion detection systems. Some of the highlighted challenges include the complexity of research algorithms, the ever-increasing number of attack signatures (which negatively impacts on performance) and the increasing prevalence of encrypted data which DPI cannot examine.

Considering the problem we seek to address, that is, detecting intrusions in potentially complex distributed systems, rewalls have several limitations:

• Regular (i.e. non DPI) rewalls lter trac based on reduced sets of properties, extracted from packets headers. This is not suitable when dealing with advanced security policies.

• DPI rewalls can be used to analyse network trac in a more ne-grained manner, however, since both the packets headers and packets content are analyzed, the overall process implies high performance overhead.

Access control

Access control is the fundamental security mechanism of all operating systems. Though the generic concept of access control exists in many forms, and may be applied to any kind of resource (e.g. databases, web content etc.) our primary focus in this thesis is operating system security. Amongst the available variants of access control, Discretionary Access Control (DAC), Mandatory Access Control (MAC) and Role Based Access Control (RBAC) are most commonly implemented in commodity operating systems. The following rst introduces the notion of access control policy, along with the various mechanisms to represent it, and then presents those three access control variants, as well as implementations of MAC in modern operating systems.

Access control policy

When setting up a system, it is important to clearly understand the security requirements that are involved, and to list them explicitly. This is done by specifying a policy. It is dened at a high level of abstraction, and it represents a concise and formalized set of goals and requirements [2]. In the case of access control, the security policy (access control policy) denes how subjects (e.g. users or processes) are allowed to access objects (e.g. les), by specifying a set of authorized operations (e.g. read, write). Common representations of such policies include Lampson's matrix, access control lists and capabilities.

In 1974, Lampson described an access control matrix [START_REF] Butler | [END_REF]. It is a table indexed by subject and object (Lampson uses the term resources ). The cells of the matrix contain access attributes that specify the kinds of access each subject is allowed to perform on each object. For each object, the corresponding column lists all the kinds of access any subjects have to that object.

Access Control Lists (ACL) associate each object with an access control list, which is a column in Lampson's matrix. ACLs are the most common way to represent access control authority relationships in modern operating systems. An ACL species which subjects are allowed to operate on the object, as well as which operations are permitted. When using ACLs, objects are identied by path names and other forgeable 1 references. On UNIX, ACLs contain an owner, a group, and rights in (R,W,X) standing for read, write, execute respectively. Dierent rights can be assigned for the owner, the group and the other subjects.

Another way to express an access control policy is to use capabilities. A Capability is a communicable and (assumed) unforgeable token of authority. A user or process that possesses a capability will have the right to access certain objects, as described by this capability. Processes can perform some operations on capabilities such as deleting them, passing them to another process or transforming them into less privileged ones. Capabilities are implemented as privileged data structures residing in kernel memory. A capability system associates each subject with a list of capabilities Interface for Unix" (POSIX) capabilities are a dierent kind of capabilities, and are not associated with any object. A process owning a POSIX capability will have some privileges associated with some operations, like listening to ports under 1024 which normally requires root privileges. It is a coarse grained approach aimed to parcel the power of the root user, avoiding the use of setuid.

Discretionary access control

Discretionary access control (DAC) is the most commonly used access control mechanism and is the default on UNIX based systems. Access is restricted given the identity and the group of subjects trying to access objects. It is said to be discretionary because subjects are able to transfer certain permissions to each other at their own discretion. This involves security related issues in systems where end-to-end security policies need to be enforced.

Role Based Access Control

With Role Based Access Control (RBAC), the permissions to perform operations are assigned to specic roles. Permissions are not directly assigned to subjects, but to roles instead. It diers from the ACLs and allows ner grain management of user rights. User rights are managed in a way that has a meaning at the application or OS level, rather than using low level attributes. It has been

shown to be a good model for implementing the separation of duties.

2 Each subject and object has a set of security attributes, and any operation requires to test that it conforms to the policy.

It is therefore a particular case of mandatory access control.

Mandatory access control

Mandatory access control (MAC) is based on authorization rules (policy) enforced by the operating system, that are not modiable by users (it is not discretionary). The Trusted Computer System Evaluation Criteria (TCSEC) [START_REF]Trusted computer system evaluation criteria (orange book)[END_REF], also known as Orange Book, denes MAC as a means of restricting access to objects based on the sensitivity (as represented by a label) of the information contained in the objects and the formal authorization (i.e., clearance) of subjects to access information of such sensitivity. A later publication from the NSA [START_REF] Loscocco | The inevitability of failure: The awed assumption of security in modern computing environments[END_REF] states that this view of MAC is tightly coupled with Multi Level Security (MLS, see Section 1.2.1), and is insucient to meet the needs of either the US Department of Defense or private industry as it ignores critical properties such as intransitivity and dynamic separation of duty. In response, the NSA proposed a more general notion of mandatory security that was rst introduced by the Secure Computing Corporation [START_REF]Dtos general system security and assurability assessment report[END_REF]. A mandatory security policy is considered to be any security policy where the denition of the policy logic and the assignment of security attributes is tightly controlled by a system security policy administrator [START_REF] Loscocco | The inevitability of failure: The awed assumption of security in modern computing environments[END_REF].

Generally speaking, mandatory access control policies are expressed in terms of security labels attached to subjects and objects [START_REF] Sandhu | Lattice-based access control models[END_REF], as is the case with MLS systems. A label on an object is called a security classication, and a label on a subject is called a security clearance.

With MAC, regular users cannot change the classication of information, and the policy is enforced by the operating system at the kernel level (see the following subsection about MAC frameworks). Some works have been focusing on the verication of the policy consistency against a given set of security goals [START_REF] Chen | Information ow query and verication for security policy of security-enhanced linux[END_REF][START_REF] Herzog Joshua | Information ow in operating systems : Eager formal methods[END_REF]. By using MAC mechanisms, one can nely control the operations each subject is allowed to perform on the objects of the system. When congured correctly, those mechanisms can signicantly improve security by rejecting illegal accesses that would have been allowed otherwise.

2 Also known as segregation of duties, it is a concept of having more than one person required to complete a task.

MAC frameworks

Advances in common operating systems include the improvement of access control mechanisms.

While traditional discretionary access control remains widely used, previous research on mandatory access control has led to implementations in common operating systems, such as Linux, FreeBSD, MacOS X and Windows. Examples include SELinux [START_REF] Vance | Implementing SELinux as a Linux Security Module[END_REF], AppArmor [START_REF]Apparmor, application security for linux[END_REF], Smack [START_REF] Schauer | The simplied mandatory access control kernel[END_REF], Tomoyo [START_REF] Harada | Access policy generation system based on process execution history[END_REF] for Linux, and TrustedBSD [START_REF] Watson | The trustedbsd mac framework: Extensible kernel access control for freebsd 5.0[END_REF] for FreeBSD. When used in so-called enforcement mode, they block illegal accesses to objects. When used in permissive mode, their behavior is comparable to an intrusion detection system, and alerts are logged when the policy is violated.

The following describes SELinux and AppArmor in further details.

SELinux [START_REF] Vance | Implementing SELinux as a Linux Security Module[END_REF] AppArmor [START_REF]Apparmor, application security for linux[END_REF] is a simple MAC implementation available in the Linux kernel as an alternative to SELinux. AppArmor aims to be easier to use and congure than SELinux. It is used by default by Novell in their products and comes with a predened policy, and a set of generic denitions to ease the diculty of creating new policies.

A signicant amount of work has been done on dening default security policies for SELinux and AppArmor, oering rules for many server applications interacting with insecure data coming from unknown clients through network connections. This makes those tools valuable for system administrators, reducing the work needed to set up complex security policies in real life systems.

Distributed MAC

With the growing number of distributed environments and services across the internet, especially during the last decade, researchers have focussed their interest on the extension of mandatory access control [START_REF] Mccune | Shamon: A system for distributed mandatory access control[END_REF][START_REF] Hernandez | Enforcing mandatory access control in distributed systems using aspect orientation[END_REF][START_REF] Wu | Information ow control in cloud computing[END_REF] policies to distributed systems so as to control interaction between applications of multiple hosts.

Limitations of access control

Access control, and especially MAC systems are useful to enforce strict policies, dramatically improving the security of operating systems. As compared to traditional discretionary access control, MAC oers tight control over access to objects by subjects or processes, in a centralized fashion.

However, access control focuses on the access to resources (i.e., system objects containing information), rather than information, and does not make any distinction between the two. Information ow control and taint marking models allow for more exibility. The next section further discusses these aspects.

Information ow control

Contrary to access control policies, which enforce security policies by controlling access to objects containing information (which we call containers of information ), information ow control focuses on the information itself. Thus, rather than preventing illegal (direct) access to containers, it prevents illegal (direct or indirect) access to information, by specifying a policy regarding information ows between classes of information. This is a key dierence between access control policies and information ow policies. The term taint marking is often used to refer to models of information ow, where taint data is propagated in labels. Information ow tracking models do not enforce a policy, but rather observe information ows and report illegal actions.

Multi Level Security

The following presents the most common approaches of multi-level security. Though such models can be considered as MAC to some extent, these enforce information ow policies. Therefore, we qualify them as information ow control rather than access control.

In 1973, the Bell-LaPadula model was introduced [START_REF] Lapadula | Secure computer systems: A mathematical model[END_REF], with the primary goal of protecting condentiality. It is also known as Multilevel Security, and systems that implement it are called Multilevel secure or MLS systems [2]. In this model, subjects and objects are labeled with a security level, which represents their sensitivity or clearance. Any information ow from a high security classication to a lower security classication is illegal [4,[START_REF]Trusted network interpretation of the DoD TCSEC (red book)[END_REF][START_REF] Simon | Multilevel security and the quality of protection[END_REF]. Implementations of MLS try to accurately observe data manipulations in order to prevent illegal information ows. Operating systems with MLS implementation include SELinux, FreeBSD, Solaris and BAE XTS-400.

In 1976, Denning introduced a lattice model of secure information ow [START_REF] Denning | A lattice model of secure information ow[END_REF]. She dened it as a mathematical framework suitable for formulating the requirements of secure information ow among security classes. This formal model involves objects, processes and a set of security classes.

Objects each belong to a security class, subjects are objects, and processes are the active agents responsible for all information ows. The set of security classes encompasses the concepts of security classications. Denning also introduces a ow relation and the class combining operator, which together with a set of security classes forms a Lattice.

In 1977, the Biba model [7] was introduced, protecting integrity. It is often viewed as the Bell-LaPadula model upside down [2]. It denes the Biba integrity property as follows: a high integrity process cannot read lower-integrity data, execute lower-integrity programs or obtain lower-integrity data in any other manner.

In 1987, Clark and Wilson proposed the Clark-Wilson integrity model [START_REF] Clark | A comparison of commercial and military computer security policies[END_REF]. As opposed to Biba, it is not a direct derivative of the Bell-LaPadula model, and it does not use label based classication. It is derived from a concept of double entry bookkeeping an old practice used in accounting [2]. In this model, low integrity data can ow to high integrity data only if it goes through a Filter (an information ow channel). Clark and Wilson also claim that the security needs in the commercial area are as important as those of the Department of Defense.

The models of Bell-LaPadula, Biba and Clark-Wilson can be represented as Lattice models in Denning's framework. Furthermore, combining the Biba and Bell and LaPadula models results in a Lattice, as lattice-based information ow policies that combine several lattices can be cast within a single lattice [START_REF] Sandhu | Lattice-based access control models[END_REF].

The Chinese wall model introduced by Bewer and Nash in 1989 [6] is a hybrid security policy that addresses both condentiality and integrity. The motivation behind the Chinese wall policy is to group datasets into conict of interest classes. In such a model, the subjects can access at most one dataset belonging to the same conict of interest class. A common example to illustrate this model is the example of consultants dealing with condential company information for their clients. A consultant should not have access to the information of two concurrent banks, or two concurrent companies of the same sector because it would create a conict of interest and aect the way the consultant behaves. There is a dynamic aspect with the Chinese wall policy: before a consultant actually accesses condential information from a specic company, say a bank company, he is allowed to access the information of any bank company. As soon as he has accessed the information from one bank, he cannot access any information from any other bank.

Decentralized models

In 1997, Myers and Liskov proposed a decentralized model for information ow control [START_REF] Myers | A decentralized model for information ow control[END_REF]. This model applies to systems with mutual distrust and decentralized authority. It diers from multilevel security models by allowing users to declassify information in a decentralized way and improves support for ne-grained data sharing. This model allows users to associate condentiality and integrity labels with data and to restrict information ows based on these labels.

With MAC systems, an administrator sets a system-wide policy. When a server runs multiple third-party applications, it is dicult for a central administrator to understand in detail the security of all the applications. With Decentralized Information Flow Control (DIFC), the policy is partially delegated to the individual applications [START_REF] Krohn | Information ow control for standard os abstractions[END_REF]. Flume, Asbestos and Histar [START_REF] Krohn | Information ow control for standard os abstractions[END_REF][START_REF] Zeldovich | Making information ow explicit in histar[END_REF][START_REF] Efstathopoulos | Labels and event processes in the asbestos operating system[END_REF] are implementations of decentralized information ow control at the operating system level. Flume [START_REF] Krohn | Information ow control for standard os abstractions[END_REF] has been implemented in Linux and uses the standard operating system abstractions commonly found on UNIX systems (processes, pipes, etc.). In Flume, processes are conned according to a ow control policy. Histar [START_REF] Zeldovich | Making information ow explicit in histar[END_REF] is an operating system aiming to minimize the amount of code that must be trusted. It provides a secure operating system using mostly untrusted user-level libraries (the only fully trusted code being the kernel). It uses Asbestos [START_REF] Efstathopoulos | Labels and event processes in the asbestos operating system[END_REF] labels on six OS level object types (threads, address spaces, segments, gates, containers and devices).

Related work

In the previous sections, we have shown how information ow control addresses the problem of tracking indirect information ows within a system. Our work uses such mechanisms so as to track information ows at the operating system level. Recent work have been focussing on information ows control and information ow tracking at dierent levels for malware analysis, detect privacy violations or to enforce complex security policies. These include VTT et al.'s model, Panorama [START_REF] Heng Yin | Panorama: capturing system-wide information ow for malware detection and analysis[END_REF],

TaintCheck [START_REF] Newsome | Dynamic Taint Analysis for Automatic Detection, Analysis, and Signature Generation of Exploits on Commodity Software[END_REF], TaintDroid [START_REF] Enck | Taintdroid: an information-ow tracking system for realtime privacy monitoring on smartphones[END_REF], Laminar [START_REF] Gates | Challenging the anomaly detection paradigm: a provocative discussion[END_REF], Pedigree [START_REF] Bin | Practical data-leak prevention for legacy applications in enterprise networks[END_REF], Aeolus [START_REF] Cheng | Abstractions for usable information ow control in aeolus[END_REF] and DStar [START_REF] Zeldovich | Securing distributed systems with information ow control[END_REF]. This section rst presents each approach individually and then compares them together.

VTT model

In 2009, Valérie Viet Triem Tong (VTT) et al. [START_REF] Viet | Specifying and enforcing a negrained information ow policy: Model and experiments[END_REF] proposed a model for specifying and enforcing a ne-grained information ow policy. This model relies on tainting techniques in order to provide information ow tracking commodities. Content and containers are distinguished: content are pieces of information while containers are logical storage objects such as les or memory pages.

Information ows are observed using tainting techniques. Tainting is performed by propagating tags: containers are each labelled with two tags, an information tag describing the current content of the container and a policy tag dening the policy regarding the information that can ow towards this container. Content and policy are described in such tags at any stage and for any supervised 3 container in the system. The information ow policy can either be automatically constructed from a DAC policy or congured by an administrator. VTT et al.'s model is used as a basis in the work presented in this thesis. We will come back to it later in the next chapter for a comparison with classic multilevel security models as well as decentralized information ow control models.

The reminder of this section presents recent information ow models and how these dier from our approach.

Panorama

Panorama [START_REF] Heng Yin | Panorama: capturing system-wide information ow for malware detection and analysis[END_REF] is a system-wide information ow tracking model based on dynamic taint analysis, focussed on detection and analysis of malware for Microsoft Windows. It combines taint propagation information at the hardware level with operating system knowledge, so as to generate taint graphs. Such graphs represent information ows made by processes on tainted information, and help identify how information is propagated in the system. Using such taint graphs along with a policy allows for automatic detection of malicious code. Panorama provides a ne-grained information ow analysis, involving a small number of false positives. It suers from a signicant slowdown of 20 times in average. However, given the purposes of such an analysis, this performance overhead is not considered as a severe limitation. Automatic detection is done in three steps, test, taint and analyse. A test engine rst runs series of automated tests. Then, a taint engine monitors how sensitive information is propagated within the system. A malware detection engine along with a set of policies is able to detect malicious code. Finally, a malware analysis engine can be used to examine the taint graphs, and provides detailed analysis information. Panorama was implemented on top of QEMU, for processor emulation, along with a kernel module called module notier, loaded on the guest Microsoft Windows operating system. As compared to our current work (based on VTT et al.'s model), Panorama diers in the sense that it provides ner granularity when observing information ows, but it also involves a high performance penalty, and requires hardware emulation, which diers from our objectives, presented in Section 2.3.

Taintcheck

TaintCheck [START_REF] Newsome | Dynamic Taint Analysis for Automatic Detection, Analysis, and Signature Generation of Exploits on Commodity Software[END_REF] dynamically taints incoming data from untrusted sources (e.g. network) and detects when tainted data is used in any way that could be an attack. It uses full system emulation at the instruction level so as to provide a very ne-grained approach. However, as with Panorama, the main limitation of such instruction-level models is a very high penalty in terms of performances; a slowdown of 1.5 to 40 times is to be expected, according to its authors. For the same reasons, this approach is not in accordance with our objectives.

Argos

Argos [START_REF] Portokalidis | Argos: an emulator for ngerprinting zero-day attacks for advertised honeypots with automatic signature generation[END_REF] is an emulator, based on Qemu, for generating signatures of attacks automatically.

It observes information ows in the guest (emulated) system so as to track illegal use of unsafe information, such as information from the network. Information from unsafe sources is tainted with tags. Such tags are attached to the memory at the byte granularity, and to CPU registers using a single tag per register. Argos traces access to physical memory addresses, and generates logs when a violation is detected. Such logs contain registers and memory information (memory dumps), and are used for automatic generation of signatures (in Snort rules format) as well as manual analysis.

Argos is able to detect attacks in userspace as well as in kernelspace. When an attack occurs, Argos injects its own shellcode, using the address space of the attacked process, so as to gather additional information from this process. Such information may for instance be transmitted to the host (running the emulator) for forensics analysis. In order to generate signatures, Argos looks for patterns by comparing the memory dumps and the trac generated by the attack (after ltering out useless information, such as trac on untargeted ports). As for Taintcheck and Panorama, the objectives of our work, presented in Section 2.3, dier from these of Argos.

Taintdroid

TaintDroid [START_REF] Enck | Taintdroid: an information-ow tracking system for realtime privacy monitoring on smartphones[END_REF] is an information ow tracking system for realtime privacy monitoring on smartphones. It is based on taint marking at four dierent levels of granularity, respectively at the variable, message, method and le levels. TaintDroid has a performance overhead of 14% on the CPU. This approach is similar to the approach we have taken in this current work. However, TaintDroid is focussed on the Android platform using the Dalvick interpreter and therefore it does not apply to native applications, which represent most of the software present on standard desktop and server operating systems. Furthermore, it does not propose a ne-grained information ow policy, but rather focusses on some specic data with respect to privacy issues.

Laminar

Laminar [START_REF] Roy | Laminar: practical ne-grained decentralized information ow control[END_REF] is a hybrid solution combining language level and operating system level Decentralized Information Flow Control (DIFC). It requires light modications (less than 10%) in the code of the programs, where programmers can use secrecy and integrity labels so as to express security policies.

It uses the same abstractions for OS-level resources, and heap allocated objects. It implemented as a modied Java virtual machine along with a Linux security module. The performance overhead of this approach varies from 1% to 56%. While Laminar oers interesting results by combining several approaches, it requires modications in the code of applications, where our approach focusses on the use of unmodied applications on commodity hardware.

Pedigree

Pedigree [START_REF] Bin | Practical data-leak prevention for legacy applications in enterprise networks[END_REF] enforces information ow control across a network for legacy applications and operating systems. It implements two functions: a trusted labeller and a central controller. The trusted labeler propagates labels on each host, it runs as a trusted module at the operating system level, and tracks information ows at the level of les and processes. The central controller enforces the policy. Therefore, the so-called data plane (forwarding of labels) is separated from the control plane (enforcement of the policy). The security model of Pedigree is based on a lattice, and the policy is centralized. 64-bit labels are attached to each resource (i.e., les or processes) and contain taint.

On each host, a label store, implemented as an in-memory structure, attaches labels to resources.

A global label store is also maintained, and used by a network enforcer to enforce information ows between dierent hosts. Taint may be of two kinds: secrecy or integrity. Users are allowed to create new taint, modify a taint that they own, and modify labels on a resource that they own, based on their capabilities. A capability database manages the capabilities, and users can have the capability to set or unset the secrecy bit of a taint (s `and s ´), to set or unset the integrity bit of a taint (i `or i ´) and to add or remove users who may manage the capabilities of a taint (o `or o ´). The main dierence of our approach as compared to Pedigree is the information ow policy itself. We compare Pedigree with our approach in Section 6.6.

Aeolus

Aeolus [START_REF] Cheng | Abstractions for usable information ow control in aeolus[END_REF] is a platform for building secure distributed applications. It performs decentralized information ow tracking at the thread level. Similarly to other models of DIFC, it allows users to dene restrictions on the use of their own information. It is based on simple rules involving principals and tags, where tags are used to categorize information, and principals are the entities interested in such information. It provides ne-grained delegation of authority, and supports revocation. It makes use of a memory-safe language to isolate threads from each others. Support for distributed programs involve a RPC mechanism, and provides the concept of boxes, allowing condential information to be communicated between two ends without tainting intermediates which do not observe the information ow. Aeolus is OS-independent, and it is implemented as a set of runtime libraries. Its main implementation supports Java, but it has also been ported to C# and PHP. Contrary to language-based information ow tracking systems, Aeolus does not observe individual variables. It remains more ne-grained than OS approaches, as it observes individual threads. A comparison of our work with Aeolus is presented in Section 6.6.

DStar

In the eld of decentralized information ow control, Zeldovich et al extended their previous work [START_REF] Krohn | Information ow control for standard os abstractions[END_REF][START_REF] Efstathopoulos | Labels and event processes in the asbestos operating system[END_REF][START_REF] Zeldovich | Making information ow explicit in histar[END_REF] with DStar [START_REF] Zeldovich | Securing distributed systems with information ow control[END_REF], so as to control information ows in distributed systems. Dstar controls how information ows between processes on dierent machines. It provides DIFC mechanisms for use by applications, in order to dene legal interactions between mutually distrustful components. By opposition with MAC, where a central administrator controls the system, DIFC gives control to application programmers, leading to a ner granularity. In DStar, labels are attached to processes, and dene the legal behavior of processes. By using such labels, Dstar ensures that only processes allowed to communicate may do so. Each label contains a set of two categories: secrecy and integrity. Secrecy categories in a message determine who is allowed to receive it, and integrity constrains who may have sent it. It follows a no read-up, no write-down logic, with respect to a partial order between labels, dened by the can ow to (Ď) function. It ensures that untrusted code does not access inappropriate data. In DStar, each process also has a set of privileges, which allow it to bypass some permissions that are normally forbidden by the Ď relation between labels. Processes may also raise their own label given their clearance. When processes own a category, these can raise the labels of other processes in that category. In order to carry labels over the network, DStar uses so-called exporter daemons on each host, which are the only processes sending or receiving DStar messages over the network. Trust is decentralized between categories owners of each host, through local exporters. Trust between exporters relies on cryptographic certicates, and exporters may delegate trust in a category to other exporters. As for Pedigree and Aeolus, we propose a comparison of our work with DStar in Section 6.6.

Comparison of related work

Current information ow control and information ow tracking models can be categorized into three types: language level, operating system level and architecture level [START_REF] Roy | Laminar: practical ne-grained decentralized information ow control[END_REF]. Language level solutions [START_REF] Myers | A decentralized model for information ow control[END_REF][START_REF] Myers | Protecting privacy using the decentralized label model[END_REF] rely extensively on type system changes and modify the program structures. Such solutions are not able to track security violations at the level of system objects (such as les and sockets).

Operating system level solutions [START_REF] Krohn | Information ow control for standard os abstractions[END_REF][START_REF] Zeldovich | Making information ow explicit in histar[END_REF][START_REF] Efstathopoulos | Labels and event processes in the asbestos operating system[END_REF] rely on page mappings and OS-level abstractions, and cannot accurately monitor information ows into applications, as those do not have access to inner data structures [START_REF] Roy | Laminar: practical ne-grained decentralized information ow control[END_REF]. However, these are able to observe information ows over all the system. Our work follows this approach, as presented in more details in Section 2.3. Architecture level solutions [START_REF] Vachharajani | Rie: An architectural framework for user-centric information-ow security[END_REF][START_REF] Zeldovich | Hardware enforcement of application security policies using tagged memory[END_REF] are able to track data labels within applications but require trusted software to manage the labels and involve high performance penalties in the case of full system emulation.

In terms of performance overhead, Taintcheck and Laminar have high performance penalty due

to their low-level approach (full system emulation). Though this provides a ne-grained approach while observing information ows (which provides interesting results for malware analysis) this approach is not practical for runtime monitoring of a full operating system, as required by our intrusion detection approach (our requirements are explained in more details in Section 2.3).

Laminar, Pedigree, DStar, Aeolus and DIFC models enforce a security policy (i.e., these block illegal information ows) while Panorama, Taintcheck, VTT et al. and Taintdroid taint information and let illegal information ows occur. For a comparison of our approach with these related work, see Sections 3.9 and 6.6. • Implementation refers to the level (i.e., layer) of deployment of the approach. OS refers to operating system level approaches (userspace libraries wrappers or kernel), architecture refers to full system emulation, and language refers to the modication of virtual machines or interpreters, or instrumentation of the code of applications.

• Performance overhead is a rough estimation of the performance of each approach.

• History refers to the fact of keeping tracks of individual pieces of information throughout the system.

• Distributed refers to mechanisms providing information ow control or tracking across multiple hosts over a network.

We believe that strict policies are not practical in all situations, as these can potentially break functionalities by blocking legitimate information ows when the security policy is too strict, or, on the contrary, allow illegitimate access when the security policy is too permissive. This becomes particularly problematic when applying such mechanisms to complex distributed systems made of heterogeneous hosts, using multiple applications with various security requirements altogether.

Furthermore, most systems use o-the-shelf components and applications, and these do not come with predened policies designed by the developers. Instead, the security requirements are specied a-posteriori, which requires a lot of eort and leads to complex security policies. On the contrary, tainting information without blocking allows for information ow tracking.

Intrusion detection

Intrusion detection is the process of monitoring and analysing system and network events, looking for signs of intrusion. Intrusion detection systems (IDSes) are software layers which automate these monitoring and analysis processes [START_REF] Debar | Towards a taxonomy of intrusion-detection systems[END_REF]. IDSes are used to detect attacks such as viruses and malicious users or to monitor the security of a system to help in diagnosis and correction of aws [START_REF] Garcia-Teodoro | Anomaly-based network intrusion detection: Techniques, systems and challenges[END_REF]. Host-based Intrusion Detection Systems (HIDS) have access to the operating system information [START_REF] Debar | Towards a taxonomy of intrusion-detection systems[END_REF]3]. Such IDSes are able to detect the presence of malware and targeted attacks by analysing low level system objects and information. Furthermore, encrypted network attacks can also be detected by analysing low level network trac once it has been decrypted. HIDSes can generate alerts corresponding to each malicious system event.

Network Intrusion Detection Systems (NIDS) can monitor segments or sections of networks, depending on their placement [START_REF] Debar | Towards a taxonomy of intrusion-detection systems[END_REF]. Those typically work in so-called promiscuous mode (only capturing trac) and have very little impact on the network. Such IDSes can consume system resources when dealing with large or busy networks [START_REF] Herzog Joshua | Information ow in operating systems : Eager formal methods[END_REF].

Anomaly detection and misuse detection

Among existing intrusion detection systems, two major approaches are used in order to dierentiate normal behavior and misuse. [START_REF] Zimmermann | Experimenting with a policy-based hids based on an information ow control model[END_REF]. Anomaly detection denes a legal behavior that is known to be safe. Any unknown action is considered as illegal. Statistical models are often used in this case.

Misuse detection, also called knowledge based, denes what is illegal, based on signatures of misuse actions.

Misuse detection, is the most popular approach amongst commercial IDSes [START_REF] Hu Zhengbing | A novel network intrusion detection system (nids) based on signatures search of data mining[END_REF]. Misuse IDSes make use of knowledge about known attacks, exploits and vulnerabilities and analyse system events and network trac looking for matching patterns. Such knowledge is often called signatures. One of the drawbacks of this approach is that the signatures database has to be maintained up to date in order to be eective [START_REF] Debar | Towards a taxonomy of intrusion-detection systems[END_REF] . Another drawback is that it is possible to forge fake matching patterns in network trac and/or system events, leading to false positives and overloading of the IDS. Also, such IDSes can only detect known attacks that are already present in the signature database.

Debar et al. [START_REF] Debar | Towards a taxonomy of intrusion-detection systems[END_REF] have shown that misuse detection can be achieved using dierent methodologies. These include expert systems, signature analysis, petri nets and state-transition analysis. A common method amongst commercial IDSes is the use of signature analysis along with patterns of attacks reduced to a low level of semantics. Well-known misuse detection IDSes include Snort [START_REF] Roesch | Snort -lightweight intrusion detection for networks[END_REF] and Bro [START_REF] Paxson | Bro: A system for detecting network intruders in real-time[END_REF]. These are both open-source.

Anomaly detection IDSes aim to identify abnormal/unusual behaviour (anomalies) by comparing current behaviour to a known normal state. It was rst introduced by Denning in 1976 [START_REF] Denning | An Intrusion-Detection Model[END_REF]. Denning was assuming that trac generated by attackers is clearly dierent from normal trac, which is recorded into proles. One advantage of anomaly detection systems is their ability to detect previously unknown attacks (zero day) [START_REF] Patcha | An overview of anomaly detection techniques: Existing solutions and latest technological trends[END_REF], which attackers may seek to exploit before patches are released to x the targeted vulnerabilities. Another advantage is the ability to detect dierent forms of the same attack, where signature-based IDS do not always have all the possible matching signatures [START_REF] Patcha | An overview of anomaly detection techniques: Existing solutions and latest technological trends[END_REF][START_REF] Vigna | Testing network-based intrusion detection signatures using mutant exploits[END_REF].

Anomaly detection IDSes rely on several methodologies. Self learning systems (time series based, such as articial neural networks (ANN), or non time-series based such as descriptive statistics and rule modelling) learn by example what constitutes the normal behavior of a system [3].

Programmed systems are taught by an administrator to detect abnormal behavior. Those can be based on descriptive statistics algorithms, or on a default deny approach, stating only what is legal.

Statistical based anomaly detection models use statistics from dierent parameters [START_REF] Garcia-Teodoro | Anomaly-based network intrusion detection: Techniques, systems and challenges[END_REF]. As stated by Gates and Taylor [START_REF] Gates | Challenging the anomaly detection paradigm: a provocative discussion[END_REF], most modern anomaly detection systems are based on Denning's assumptions [START_REF] Denning | An Intrusion-Detection Model[END_REF]. Those assumptions consider that attacks are rare (as compared to normal events) and dier from the normal behavior of the system.

Hybrid systems [START_REF] Patcha | An overview of anomaly detection techniques: Existing solutions and latest technological trends[END_REF] are combining both misuse detection and anomaly detection approaches.

Policy-based IDSes

Policy-based IDSes are anomaly detection IDSes following a default-deny approach. A number of previous works exist in this domain, using sandboxing mechanisms at the language level [START_REF] Inoue | Anomaly intrusion detection in dynamic execution environments[END_REF] or via Kernel based reference monitors such as BlueBox, REMUS, LIDS and Ko et al. system wrappers [START_REF] Suresh | Bluebox: A policy-driven, host-based intrusion detection system[END_REF][START_REF] Habib | Getting started with the linux intrusion detection system[END_REF]5,[START_REF] Ko | Detecting and countering system intrusions using software wrappers[END_REF]. Similar sandboxing mechanisms also exist in user space, namely system introspection [START_REF] Wagner | Janus: an approach for connement of untrusted applications[END_REF][START_REF] Jain | User-level infrastructure for system call interposition: A platform for intrusion detection and connement[END_REF]. Blare [START_REF] Zimmermann | Introducing reference ow control for detecting intrusion symptoms at the os level[END_REF][START_REF] Zimmermann | Experimenting with a policy-based hids based on an information ow control model[END_REF][START_REF] Viet | Specifying and enforcing a negrained information ow policy: Model and experiments[END_REF][START_REF] Georges | Blare tools: A policy-based intrusion detection system automatically set by the security policy[END_REF] [START_REF] Roesch | Snort -lightweight intrusion detection for networks[END_REF] or Bro [START_REF] Paxson | Bro: A system for detecting network intruders in real-time[END_REF]. Examples of this are the following approaches. In [START_REF] Roschke | Intrusion detection in the cloud[END_REF], Roschke, Cheng and Meinel proposed and implemented an extensible IDS management architecture, providing central management of several sensors. It integrates several sensors through an event gatherer, with support for several implementations of well known ID-Ses. In [START_REF] Mazzariello | Integrating a network ids into an open source cloud computing environment[END_REF], Mazzariello, Bifulco and Canonico proposed an approach of misuse detection for an opensource cloud computing environment. It targets denial of service attacks, and it is based on Snort [START_REF] Roesch | Snort -lightweight intrusion detection for networks[END_REF] for analyzing network trac.

To our knowledge, the approach that is the most closely related to our current work is an approach of anomaly detection introduced by Zimmermann and Mohay in [START_REF] Zimmermann | Distributed intrusion detection in clusters based on non-interference[END_REF]. It focuses on detecting intrusions in clusters based on the principle of non-interference. Objects of the operating system are supervised by monitoring the invocation of their methods (i.e. actions such as read or write) and producing a trace. The policy species the legal behavior of the system, by associating domains to object methods. Violations of the policy are detected by evaluating a trace of the system using an unwinding theorem. Such a theorem makes it possible to identify the set of existing traces matching the desired non-interference properties. Reference monitors are deployed on each node of the system, and messages between nodes are instrumented.

4 Now CIDre. 5 JBlare is an implementation of Blare in the Java Virtual Machine (JVM) able to monitor information ows withing Java programs.

Chapter 2

Information Flow Models

Our research is the continuation of previous work in the ISSN (Information Systems Security and Networks) team at Supélec (now CIDre). Models for dynamic information ow tracking have been previously proposed, and have shown to be successful in detecting intrusions [START_REF] Viet | Specifying and enforcing a negrained information ow policy: Model and experiments[END_REF][START_REF] Zimmermann | Experimenting with a policy-based hids based on an information ow control model[END_REF]. Our model is an extension the VTT model, and we target intrusion detection in both isolated and distributed environments. In this chapter, we rst present the VTT model (introduced in Section 1.4.3). Then we compare it with existing models of information ow control and present a summary of the properties oered by each model. We nally present our requirements for intrusion detection.

VTT model

The following is a description of the model introduced by Valerie Viet Triem Tong et al. [START_REF] Viet | Specifying and enforcing a negrained information ow policy: Model and experiments[END_REF] in 2009. This model is an information ow model based on taint marking techniques along with an information ow policy, it protects both integrity and condentiality. Objects of the operating system potentially containing information, such as les, are called containers of information.

Denition 1. Labels called tags are attached to each container of information. Tags contain meta-information, that are used to describe real content. These tags include a policy tag, and an information tag :

• The information tag represents an over estimate of the information that the container may contain.

• The policy tag represents the information ow policy for the container (i.e. which information it can legally contain).

Any information ow towards a container, making changes to its content, requires an update of its information tag so as to match the new content. After this, a legality check is performed in order to ensure that its policy (as dened in its policy tag ) has not been violated. If a violation of the policy occurs, an alarm is raised.

Policy

The policy in the VTT model diers from other information ow models. It is decentralized at the container level in the policy tags of each specic container, and states which information is allowed to be contained in each container or in other words what can ow towards each container . The policy for a container is expressed as a set of sets. Any set (or any subset of it) of the policy tag, represents a legal combination of information for a given container, (i.e. a legal information tag ).

Therefore, an information ow towards a container is legal if and only if the updated information tag of the container after the information ow occurred is included in one of the sets of the policy tag.

• The integrity of containers is protected by controlling which subsets of information are allowed to mix together inside the containers (i.e. how information may be altered).

• The condentiality of information is controlled by determining which pieces of information containers may contain (i.e. where information may ow).

Denition 2. Let C be the set of all containers. For any container c P C, itagpcq lists the origin of content residing in the container, i.e. its information tag, ptagpcq lists the policy attached to the container, i.e. its policy tag.

Updates of the information tag

When an information ow occurs from a container C 1 to a container C 2 , the information tag of C 2 is updated with the information tag of C 1 . Its new information tag (after the ow occurred ) is the union of its old information tag with the old information tag of C 1 (before the ow occurred ).

itagpC 2 q new " itagpC 1 q old Y itagpC 2 q old
Legality of an information ow Denition 3. An information ow towards a container is legal if and only if its information tag is included in one of the sets of its policy tag :

LegalpitagpCq, ptagpCqq ô Dp P ptagpCq|itagpCq Ď p

Example 1. Consider an information ow from C 1 to C 2 with the following tags:

itagpC 1 q " t1, 2u itagpC 2 q " t2, 3u ptagpC 2 q " tt1, 2, 3, 4u, t5, 6uu
The following update on the information tag of C 2 would occur : itagpC 2 q new " itagpC 2 q old Y itagpC 1 q old " t1, 2, 3u This information ow is legal because itagpC 2 q is a subset of one of the sets of ptagpC 2 q : t1, 2, 3u Ď t1, 2, 3, 4u.

With such a policy, the condentiality and the integrity properties are independent. For instance, the policy attached to a process might have a low level of condentiality (i.e. it would only have access to a small subset of the information on the system), and a high level of integrity (i.e.

the data cannot mix with other data) at the same time. Empirically, condentiality and integrity can be expressed as follows, and are compared to the same notions of the Bell-LaPadula and Biba models later in Section 2.2.

• The condentiality level of a policy tag is determined by the set of dierent atomic information it allows in a container, regardless of how it allows them to mix together. The more dierent pieces of information are legal in the container, the higher the level of condentiality raises for this container. The less information is legal in the container, the lower the level of condentiality. For instance, a process with a high level of condentiality may have authorized access to a lot of dierent pieces of information, and thus have a policy tag allowing it to contain a high number of dierent pieces of information. The condentiality level of a container c can be measured by: |

ď pPptagpcq |
• The integrity level of a policy tag is determined by the combinations of information it allows in a container. The more the information is allowed to mix with other information, the lower the integrity. The less it is allowed to mix, the higher the integrity. For instance, a process with a high level of integrity may not mix its content with low integrity information and would thus have a policy tag forbidding it. The integrity level of a container c can be measured by:

|ptagpcq| | Ť pPptagpcq |

Dynamic aspect

In the VTT model, the set of authorized operations that processes can perform over objects (containers of information) is not constant. It may dynamically change over time: whether a process can access an object depends on the information that it previously accessed. For instance, a process might have the permission to write to a given container until it reads some data that is invalid in this container, either for integrity reasons (e.g., the new data does not have a sucient integrity level), or for condentiality reasons, (e.g., the new data cannot be mixed with less condential information). This notion of dynamic changes in the authorized behavior of processes could be qualied as a dynamic clearance 1 .

This dynamic aspect can be summarized as follows:

• A policy is expressed on what containers are allowed to contain.

• The content of containers keeps changing (after each information ow).

• The clearance of a process is dynamic in time.

Lattice

The VTT model can be formally represented in Denning's framework, Lattice model of secure information ow [START_REF] Denning | A lattice model of secure information ow[END_REF], and under certain assumptions, its components form a bounded lattice.

While the demonstration of this aspect is not covered here, we demonstrate this lattice property later in Section 3.7 for our extension of the VTT model.

Comparison with lattice based models

The following is a comparison of the VTT model with the most common implementations of multilevel security (MLS) systems and policies. We use the terms security class to refer to the policy of one or more containers (see Section 3.7).

Chinese walls

The Chinese walls model is centered on the concept of separation of conict of interest classes (see Section 1.2.1). Such a dynamic property can be dened in a VTT policy. Recall the previous example from Chapter 1 with a consultant working for a bank company. A Chinese wall policy could be dened such that once the consultant had access to information from any bank, his or her access to the information from any other bank would be denied.

In the following, we call I Bank k the class of all the information related to the bank Bank k . Therefore, in a context where N concurrent banks exist, if the consultant has accessed the information from Bank 1 (I Bank1 ), his or her access to I Bank k |2ďkďN is illegal. Such a policy can be dened in the VTT model by attaching a user policy to the consultant where each subset of the policy concerns the information from one specic bank. The following policy is an example of this:

P U Consultant " ttI Bank k u 1ďkďN u
The multiple subsets of this policy have a meaning of exclusion: the legal information for user U consultant is dened by at most one of the composing sets of the policy at one time. It can be seen as an exclusive or relation between the composing sets, allowing only one set at a time.

Bell-LaPadula

The Bell-LaPadula model labels data with levels of classication. It can be summarized as follows:

• The simple security property also known as no read up states that no processes can read data up from a higher level of classication.

1 The notion of clearance here is the same as in the Bell-Lapadula model, dening a level of authorization for a subject over an object. See Section 1.2.1.

• The *-property also known as no write down states that no processes may write data down to a lower level of classication.

While this model protects condentiality, it does not protect integrity. In the VTT model, a process may not read information that is illegal with respect to its policy tag (i.e., not contained in one of the sets of its policy tag). This means that this information is contained in a higher or incomparable security class in the policy's lattice. This is comparable to no read up in Bell-LaPadula.

Example 2. A process with policy {{1,2,3},{4,5,6}} may not read a le containing {1,2,3,4}.

It may not read a le containing {5,6,7} either. Both are forbidden with respect to the policy. However, {5,6,7} would be allowed if the policy was {{1,2,3},{4,5,6,7}}, which is considered as a higher security class than {{1,2,3},{4,5,6}}in the policy's lattice (presented in Section 3.7).

In the VTT model, a process may not write information to a le if such information is not legal with respect to the le's policy tag (i.e., not contained in one of the sets of its policy tag). The meaning of this in terms of security class is that the involved information is contained in a higher or incomparable security class in the policy's lattice. This notion is similar to no write down in Bell-LaPadula.

Example 3. A process may not write information {1,2,3,4} in a le with policy {{1,2,3},{4,5,6}}.

It may not write information {5,6,7} either. Both are forbidden with respect to the policy. However, {1,2,3,4} would be legal with the policy {{1,2,3,4,5,6}}, which would be a higher security class in the policy's lattice.

There are however two major dierences between the VTT model and Bell-LaPadula. With VTT, information ows are illegal between dierent security classes with incomparable levels of security. Also, the VTT policy makes it possible to dene which information is allowed in which containers, and is thus attached to containers themselves, it does not express any direct classication of the information.

Biba

The dierences between VTT and Biba are similar to those with Bell-LaPadula. Similarly to condentiality, data with the same level of integrity are isolated as those are considered as being dierent security classes.

Integrity with VTT is protected on a by container basis, and given two pieces of information i 1 and i 2 , some containers may be allowed to mix them together (tti 1 , i 2 uu) while some other containers may not (tti 1 u, ti 2 uu). The integrity which is protected is the integrity of the container, not the integrity of the information itself.

Clark-Wilson

The Clark-Wilson model protects integrity. As opposed to Biba, it is not based on Bell-LaPadula, and it does not make use of label-based classication. In this model, low-integrity data can ow towards high integrity if it goes through a lter (declassication). This model is not based on a lattice. It is not directly comparable to the VTT model in terms of policy.

DTE DTE stands for Domain and Type Enforcement and SELinux is based on it. (See Section 1.1.2).

With DTE, a domain attribute is attached to subjects, and a type attribute is attached to objects.

Restrictions apply from domain to type, and also from domain to domain.

In the VTT model, the tags attached to processes and containers can be compared to domains and types in DTE. Information ows between two containers are legal if their policy tags allow it.

The information tags state which information the containers contains, and the relation between policy tags and information tags can be seen as domain to type or domain to domain in DTE. In the VTT model, this relation is bilateral:

• The relation between the information tag of a process and the policy tag of a le denes if the process is allowed to access this le in write mode.

• The relation between the information tag of a le and the policy tag of a process denes if the process is allowed to access this le in read mode or in exec mode.

However, the changes of domains in DTE have no equivalent in the VTT model. In DTE, executing a binary program may cause a domain switch for the running process, and the new domain can either extend or restrict the rights of the process. In the VTT model, any information ow between a subject and an object may change the information tag of either the subject or the object, thus restricting the policy in one direction: from the subject to the object if the information tag of the subject has been modied, or the other way in the other case.

Myers and Liskov

As in the VTT model, the Myers and Liskov decentralised information ow control model (DIFC) is related to mandatory access control in the sense that the security policies are mandatory, and not enforced at the discretion of application writers [START_REF] Krohn | Information ow control for standard os abstractions[END_REF]. Where the M&L model allows decentralization of the policy with the applications being allowed to declassify information that they own, VTT policy specication is centralized (though future works are planned to provide declassication in the model). Both M&L and VTT are based on a lattice and protect both integrity and condentiality of data.

Summary of the comparison

The VTT model can be seen as a combination of Biba and Bell-LaPadula as it addresses both condentiality and integrity aspects at once. It has however a dynamic aspect in common with the Chinese walls. Furthermore, it allows data isolation when security classes of the same level are not directly comparable. This later aspect is comparable with models based on Multiple Independent Levels of Security (MILS).

VTT B&LP 1 there is no declassication mechanisms in DTE. However, domain transitions may provide comparable properties in some situations. extent. as it is most often the case, then it is characterized as centralized. Distributed refers to the network distributed systems such as web services with multiple hosts. Content based refers to the distinction between containers of information and content. Flow history refers to the ability to describe the origins of all the content that is residing in a container.

Objectives and requirements for intrusion detection

In this Ph.D., we aim to dynamically detect intrusions in isolated hosts as well as in distributed systems composed of multiple hosts. Our objectives are the following:

• Detecting violations of integrity and condentiality (which we consider as intrusions).

• Detecting successful attacks targeting all kinds of components (applications, OS-level services etc.).

• The ability to use o-the-shelf components: unmodied applications running on commodity hardware.

Our approach of intrusion detection follows the anomaly detection paradigm: we observe illegal information ows within the operating system, with respect to a security policy.

There exists a number of information ow control models in the literature. Some of these models can be used in permissive mode, where the security policy is not enforced, but alerts are raised instead. Such behavior allows the information ows to actually happen and modify the state of the system. This is a rst requirement for our approach of intrusion detection (we do not aim to prevent intrusions). Another requirement is the ability to track the origin of information residing within any of the objects of the operating system. Where most models of information ow control would let information spread once congured in permissive mode, they would not taint information : no tracking of the propagation of information within the operating system would be possible.

As shown in Figure 2.1, the VTT model ts both of these requirements :

• It is a permissive model: it does not enforce the policy, and it does not forbid information ows. Flows happen and modify the state of the system.

• The information ow history is kept, and allows to track the origin of information residing in any container of the system. This aspect relies on so-called taint marking techniques. It will be further described later in Chapter 3.

For these reasons, our approach of intrusion detection is based on VTT's model. The contributions of our work are presented in the next parts of this thesis. Our rst contribution is an extension of VTT's model and its implementation in the Linux kernel. This is presented in Part II.

Our second contribution is the extension of this rst work to t distributed systems, and it is presented in Part III.

Chapter 3

Extended Model

As presented in Chapter 2, a number of information ow models exist. These may be applicable to intrusion detection when used in a permissive mode, where the policy is not enforced and information ows actually occur even when these are illegal. Our choice of not enforcing the policy is motivated by the fact that we are interested in intrusion detection rather intrusion prevention. However, future research in this eld may also focus on the enforcement mode of information ow models. As shown in Figure 2.1 in Chapter 2, the VTT model oers properties that best t our requirements. Therefore, we use it as a basis in our intrusion detection approach. We have however identied some evasion issues when using the model as-is for designing a host kernel level monitor. Although the VTT model oers the properties that are needed for our approach of intrusion detection, it lacks consideration of some aspects of the operating system that are necessary for realistic intrusion detection. This chapter rst highlights the evasion issues we found, and then presents our extended model and how it allows to detect intrusions in isolated machines (distributed aspects are covered in the third part of this thesis).

A model based on VTT

The VTT model provides ne-grained information ow tracking between containers of information.

When applied to an operating system of the UNIX family, it allows to track information between objects of the operating system such as les, sockets and the like, and users. This notion of user diers from the traditional UNIX notion: users in VTT are considered as containers. Recall from Chapter 2 that for any container c, itagpcq lists the origin of content residing in the container, which we call its information tag. In VTT, this applies to users as well, as information tags are attached to their representing containers. For instance, users A and B would be represented as containers u A and u B , with itagpu A q " i A and itagpu B q " i B . If we now consider a container c with the following policy: ptagpcq " ti A , i B u, stating that c may only contain i A or i B , or both at the same time (that is, any subset of ti A , i B u), then only users A and B are allowed to write in c

(no matter if one of them already wrote information to this container before the other).

Evading VTT

When applied to a real operating system, this model can be evaded through code execution, as it does not conne executable code. Furthermore, the previous notion of users is only theoretical: no process connement mechanisms are dened in the model. Whereas information from an exclusive list of users is allowed in each container, the reverse is undened (i.e. how information is allowed to ow towards a user). As an illustration of the shortcomings of this model with respect to code execution, consider the following example:

Example 4. : A malicious user exploits a aw in a service running on a web server, and injects arbitrary code into the process running this service. The injected code is then interpreted and it writes a malicious script into a new le, before executing it as the current user.

In such a scenario, the VTT model would forbid the process to write into any le c (container) for which access is not allowed to the user u web running the web server (i.e. the policy attached to c does not allow u web ). On the contrary, writing to any le allowing u web in its policy is authorized, and the same goes with the creation of new les (as in the previous example). In such a situation, there is no way to detect the intrusion: this is one potential scenario of evasion.

Proposed extension

We have presented and published the following extension of the VTT model at ICC 2011 [START_REF] Geller | Information ow control for intrusion detection derived from mac policy[END_REF]. This new model improves the following aspects :

1. The execution of code and programs is supervised, based on the distinction between active code, that is executed by processes, and passive stored information.

2. Containers of information are considered separately, depending on whether these are stored in memory or on-disk. The former are called volatile containers, and the latter are called persistent containers. We also make the distinction between (passive) objects, storing information, and (active) subjects (i.e. processes running code on behalf of users).

3. The information ow policy can be expressed separately for users, executable code (which we also call programs 1 ) and containers.

4. The information ow policy can be derived from a mandatory access control policy. We have formally dened a method for deriving an AppArmor 2 policy into an information ow policy that is applicable to intrusion detection. It remains possible to derive an information ow policy from a discretionary access control policy, as it has been done in previous work with the VTT model.

We further detail these aspects in the reminder of this chapter.

Data and code distinction

Recall from Denition 1 in Chapter 2 that tags contain meta-information describing actual information (or data 3 ) of the system. In this new model, meta-information is represented by two sets I and X as follows:

• I is the set of all meta-information describing passive data (i.e., stored in a le). Note that executable code (e.g., shared libraries, binary programs, executable scripts ) is equally represented in I as long as it is not executed, i.e. as long as it is not running as the code of a process. Thus, stored data representing code is represented in I.

• X is a set describing active code being executed (i.e., being run as code in processes). Each element of X is an image of one passive information element of I, through the Run relation dened below.

This distinction of I and X was inspired by Denning's assumption: Processes are the active agents responsible for all information ow [START_REF] Denning | A lattice model of secure information ow[END_REF].

Denition 4. The execution of code is characterized by the following relation: 3 We both refer to information and data interchangeably.

Run : I Ñ X
X is a bijection of I through the relation Run. Each program is described by one or more elements of I when stored on disk, and by their image through Run when running as the code of a process. We do not have any a-priori knowledge concerning the executable aspect of information.

Therefore, each passive information of I has an image in X , that is used upon eventual execution. Denition 5. A program (or application) is dened as a set of executable information in ℘pIq4 .

We dene the set of all programs as Π: @π P Π, π P ℘pIq5 Usually, we would label each supervised program with a unique meta-information of I, however, in some cases, programs may be composed of multiple elements combined together, e.g. a C

program linked with shared libraries as in Example 5, or a virtual machine or interpreter loading a script le, as it is the case with most dynamic languages such as Ruby, Python, PHP and many others. In such cases, the nal program is the set of all of its composing elements, and it is tainted with multiple meta-information of I. This aspect allows us to dene the legal interactions amongst pieces of code or programs in the policy (which we introduce later in this chapter).

Example 5. Consider a C source le s, labelled with information i s . When compiling such source code and linking it with external libraries l 1 , . . . , l n , which les are respectively labelled with information i 1 , . . . , i n , the resulting binary program le f is tainted with S " ti s , i 1 , . . . , i n u P ℘pIq, i.e. itagpf q " S.

Types of containers

At the operating system level, containers of information do not all behave the same. We found that several kinds of containers have dierent properties. The rst distinction we make concerns subjects and objects. This notion is similar to the one used in access control models, where each subject is able to perform actions on a set of objects. We use the terms active containers to refer to subjects, and passive containers to refer to objects. We also make a distinction between containers regarding their storage locations. We consider containers stored in memory as volatile containers, as such containers would not survive power failure. Furthermore, even when no power failure occurs, the lifetime of such containers is limited: most of them are destroyed after a given time of execution, e.g. a socket is destroyed once a connection expires, a bunch of memory pages is freed once a process calls free6 etc.. Therefore, we dene:

• The set of volatile containers (objects) as C V .

• The set of persistent containers (objects) as C P .

• The set of processes (subjects) as C Π .

The set of all containers is dened as:

C " C V Y C P Y C Π
It should be emphasized that users are not considered as containers in our extended model.

Processes are the only active agents of the system and thus we consider those as the only active containers. Processes act as subjects, running code doing operations on behalf of users, towards objects being either volatile (e.g. sockets) or persistent (e.g. les) containers. Therefore, conning users as well as programs is done at the level of processes, and only the three previously introduced types of containers exist in our model: volatile, persistent and processes.

Supervision of processes

As mentioned previously, we follow Denning's assumption that processes are the active agents responsible for all information ows. Therefore, tainting rules apply to operations made by processes and involving potential 7 information ows. As we distinguish (passive) data from (active) code in the meta-information used in tags, dierent tainting rules are applied, depending on the access mode and the kind of meta-information involved. Denition 6. For any container c,

• the function itag : C Ñ ℘pI Y X q returns the information tag of c.

• the function ptag : C Ñ ℘p℘pI Y X qq returns the policy tag of c.

In the following, we represent the operating system as a state-transition system:

σ i Ñ τi σ i`1
We note σ 0 , σ 1 , . . . , σ n the states of the system, and τ 0 , τ 1 , . . . , τ n the transitions between these states. We consider the read, write, and exec operations made by processes to be transitions between states of the containers. Therefore, each information ow is represented as a transition between two states i and i `1, respectively referring to the state of information before and after the information ow occurred.

Keeping tracks of running code

Before going into the details of tainting rules, let us clarify how this distinction between code and data in meta-information aects the meaning of information tags. When describing the VTT model in Chapter 2, we stated that information tags indicate the origin of content in containers. This remains true when considering elements of I, describing passive information. However, elements of the new set X do not have the same meaning. Instead, such elements keep tracks of active code involved in information ows. In other words, the combination of elements of I and X in information tags has a dual meaning, stating which couples xinformation, codey are involved in information ows. It also depends on the kind of container:

• Any element a P X in the information tag of a processes denes that the process potentially runs this code.

• Any element a P X in the information tag of any passive container indicates a process running such code wrote information in the container. This allows us to express additional properties in the information ow policy. We will come back to this later in this chapter.

Write access

When a process p accesses a container c in write access, we distinguish two situations: either the process overwrites the existing content, or it appends new information to the container. In the rst case (overwrite), we propagate the information tag of the process as-is towards the container. itagpcq i`1 " itagppq i In the second case (append), the union of both the container and the process's information tags is used as the new tag for the container:

itagpcq i`1 " itagppq i Y itagpcq i
In any case, the new information tag of the container is tainted by both elements of I, i.e. information that the process was holding at the time of the access, and elements of X , i.e. which code the process was running at this time. This property allows to keep tracks of which processes write information to containers, and to express policy rules based on it, as presented later in this chapter.

7 Recall that our analysis takes a maximum estimation of the possible content of containers into consideration.

Execution

Recall the Run relation from previous Section 3.2 of this chapter. This relation characterizes the execution of code or programs. Denition 7. We extend the Run relation from Denition 4 as follows, so as to work with sets of elements rather than individual elements:

Run : ℘pIq Ñ ℘pX q RunpAq " tRunpaq|a P Au

When a new process is created as the result of the execution of some code, its information tag is initialized with the image of the information that was executed, through the relation Run. Therefore, for any process p running code stored in a persistent container c, the information tag of the new process is initialized as follows:

itagppq i`1 " Runpitagpcq i zX q
Elements of X in a running process give information related to the code that is currently running. These meta-information also taint the containers where processes write information, as described previously. Therefore, upon execution of content store in a container c, we discard elements of X from the information tag of c: we do not want taint the new process with previous writers of c (i.e., pieces of code being executed by previous processes which wrote information to c).

Read access

When a process p accesses a container c in read access, it is tainted by the information tag of c, as follows:

itagppq i`1 " itagppq i Y pitagpcq i zX q
We discard elements of X for the very same reasons described previously for the case of execution. As shown on Figure 3.1, we apply dierent tainting rules, depending on whether processes read, write or execute content. In this gure, taint means that the destination process or container gets tainted by the meta-information. Discard means the destination process or container does not get tainted by the meta-information. The latter only applies to elements of X , i.e. meta-data attached to active code being executed.

Summary of tainting rules

Extended information ow policy

Before going into further details about how the (information ow) policy is attached to containers, let us dene the policy itself. In our model, the policy can be expressed separately for users, programs and persistent containers. It should be emphasized that volatile containers do not have a policy because these directly depend on the processes creating them and acting on them. Checking their content against the policy is done every time the acting process performs an operation tainting its own information tag. For any given system, let U be the set of all users, C P the set of all persistent containers and Π the set of all programs (i.e. executable code).

The information ow policy is a triplet: P " pP C P , P U , P Π ) where: P C P is the policy attached to persistent containers, P U is the policy attached to users, and P Π is the policy attached to the executable code of programs.

• P C P Ď C P ˆ℘pI Y X q.
For any persistent container c protected by the policy, P C P denes one or several sets S " ta Y bu, a P ℘pIq and b P ℘pX q where:

1. Any subset of a may legally ow into c.

2. Applications or programs running any subset of b as their code are allowed to write information into c.

• P U Ď U ˆ℘pI Y X q.
For any user u that is supervised by the policy, P U denes one or several sets S " ta Y bu, a P ℘pIq and b P ℘pX q where:

1. Processes on behalf of u are allowed to access any subset of a.

2. Processes on behalf of u are allowed to execute any subset of b.

• P Π Ď Π ˆ℘pI Y X q.
For any executable information π that is supervised by the policy, P Π denes one or several sets S " ta Y bu, a P ℘pIq and b P ℘pX q where:

1. Processes running π as their code are allowed to read any subset of a.

2. Processes running π as code are allowed to execute any subset of b.

The (information ow) policy is attached permanently to persistent containers and to users, and dynamically to processes as these are created, in their policy tags.

Denition 8. We dene the relation maycontain as follows:

@x P tC P , U, Πu, pc, pq P P x ô c maycontain p where c P x and p Ď ℘pI Y X q

Therefore, for any container c P C

ptagpcq " tp|c maycontain pu

Constrained and unconstrained containers

Unconstrained containers have no policy attached to them, i.e., their policy tags are empty, whereas constrained containers have a policy tag dening their legal content. For any c P C,

• If c is unconstrained, then ptagpcq " H.

• If c is constrained, then ptagpcq ‰ H.
• If c is constrained, and must remain empty, then ptagpcq " tHu " K.

Persistent policy

Tags are permanently attached to persistent containers when the policy is dened and applied.

These are distributed in all persistent containers in the system. We qualify such a policy as permanent because it will remain until a new policy is dened and distributed over the system again, replacing the policy in place. Killing processes, rebooting the system or power failures will not alter such policy tags.

We attach two tags describing a policy to each persistent container: the rst one describes the legal content into the container, and corresponds to a set of rules included in P C P . (The set of all of the policy tags of persistent containers is equal to P C P ).

The second one denes the policy attached to the potential executable content of the container (program or code such as shared libraries). We call it execute policy tag, as it is used only when the content is executed. The set of all of the execute policy tags of persistent containers is equal to P CΠ . We call this tag the execute policy tag of the container.

Initialization

At the time when we set up the (information ow) policy, i.e. before we start to track information ows, we attach information tags, policy tags, and execute policy tags to the persistent containers we wish to track. Recall that processes do not exist at this stage, and are dynamically tagged as they are created when the system is running.

Initially, information tags are initialized to unique meta-information describing the initial content of the container. This initial information is considered as being atomic 8 . Therefore, the minimal policy tag of any container allows at least this initial information.

Denition 9. For any persistent container c, we note ptag 0 pcq its initial policy tag. It is dened as the set of elements of the policy regarding this container, that we note c.policy9 @c P C P , ptag 0 pcq " c.policy with:

c.policy " tS P ℘pI Y X q|pS, cq P P C P u Denition 10. For any persistent container c eventually containing executable information, we note xptag 0 pcq its initial execute policy tag. It is dened as the set of elements in the policy regarding the execution of its content π (executable code or program).

@c P C P , xptag 0 pcq " π.policy with:

π.policy " tS P ℘pI Y X q|pS, πq P P Π u

When no initial executable content exist in the container, we do not attach an execute policy tag to it.

User policy

As opposed to persistent containers, where the policy is distributed in each container, the policy attached to each user is globally dened in the system (e.g. in a hash table). The policy for each user is dened as a set of rules included in P U . Figure 3.2 illustrates the user's policy for a system with N users.

8 Atomic information are the smallest pieces of information that we are able to distinguish in the system. Because processes are dynamically created by the operating system upon execution of a program, tags cannot directly be attached to processes before these actually exist. Instead, this is done at runtime, at the time of execution. The policy for a process depends on the user on behalf of whom it performs actions, as well as the program or code being run.

uid 1 set 1 P ℘p℘pI Y X qq uid 2 set 2 P ℘p℘pI Y X qq uid N set N P ℘p℘pI Y X qq
The policy tag of a process determines which are the legal information ows the process can perform, given the context xuser, programy. The policy regarding the running program is stored in the execute policy tag of the persistent container storing its code on disk. This policy is used along with the policy attached to the current user, in order to determine the policy tag of the process.

Denition 11. The policy restraining a process p running a program π on behalf of user u is dynamically computed upon execution, as follows:

p.policy " u.policy [ π.policy where:

A [ B " ta X b|a P A, b P BuztHu

Formally, A [ B denotes the intersection of all the common sets of A and B. After this, the policy tag of the new process is initialized to p.policy.

Legality of information ows

The legality of information ows remains the same as in the VTT model. Recall Denition 3 from Chapter 2. Intuitively, an information ow is legal if and only if the information tag of the destination container, after the information ow occurred, is included in one of the sets of its policy tag.

The legality of information ows is veried each time an information tag is updated, i.e,. after each information ow towards a container.

Initialization of processes

In the case of the execution of programs, the state of the resulting new process must be veried, to check whether the execution is legal. Figure 3.3 summarizes the creation and initialization of the tags attached to processes upon execution of code (or binary programs in this gure, though this applies as well to any other form of execution, such as executable memory mappings, see Chapter 4 for more details). When a new process is created, its policy tag and information tag are initialized according to the rules dened in the previous sections of this chapter:

• The policy tag of the process is set according to the policy for the current user, as well as the policy for the program being executed.

• The information tag of the process is set at runtime, as the image of the meta-data of the executed code through the relation Run. Such code is stored in a persistent container, which execute policy tag contains the appropriate policy to restrict its execution.

After the execution of a process p, we ensure that Legalpitagppq, ptagppqq stands, i.e.,

DS P ptagppq|itagppq Ď S

In Figure 3.3, ptag, itag, and xptag refer to the policy tags, information tag and execute policy tag of the containers, respectively. From the previous denitions, we can establish that xSC, Ďy forms a partially ordered set:

• Ď is reexive: @C P SC, C Ď C • Ď is transitive: @C 1 , C 2 , C 3 P SC, C 1 Ď C 2 ^C2 Ď C 3 ñ C 1 Ď C 3 • Ď is antisymmetric: @C 1 , C 2 P SC, C 1 Ď C 2 ^C2 Ď C 1 ñ C 1 " C 2
Under the following assumptions, we can establish that xSC, Ď, J, Ky forms a universal bounded lattice:

• SC is nite.

• SC has a lower bound K" ttuu such that @C P SC, KĎ C.

• SC has a greatest bound J " ℘p℘pI Y X qq such that @C P SC, C Ď J.

This shows that the security classes of the policy in our model can be represented in a lattice.

Our model can be represented in Denning's mathematical framework suitable for formulating the requirements of secure information ow amongst security classes [7].

Derivation from a MAC policy

In this section, we present an algorithm to derive an information ow policy, usable in our IDS, from a MAC policy as used by AppArmor, a LSM module presented in Chapter 1. This work has been published along with our theoretical model in the proceedings of the IEEE International Conference on Communications in 2011 [START_REF] Geller | Information ow control for intrusion detection derived from mac policy[END_REF].

AppArmor [START_REF]Apparmor, application security for linux[END_REF], introduced in Chapter 1, is a Linux security module enforcing a Mandatory Access Control (MAC) policy. In the following paragraphs, we provide a solution for deriving an

AppArmor MAC policy into an information ow policy, usable in our model, and restricting the execution of code or programs (P Π ). Such a policy does not specify rules based on users, and thus the subset of the policy concerning users (P U ) remains empty. As we monitor information ows, we discard pure access control rules which are unrelated to any possible information ow 10 .

In AppArmor, the policy is composed of so-called proles, where each prole describes a set of rules specic to an application (program). In order to derive a policy from a set of AppArmor proles, and which we can use as an information ow policy for our IDS, we proceed as follows:

for each statement of each AppArmor prole, we check whether such a statement is related to a potential information ow, and transform it into a corresponding statement in our model if it does.

The ability to derive an information ow policy from such a wide spread format 11 leads to two major advantages. First, the specication of the policy for a given program or application can be a burden in some cases, as a lot of operations and information may be accessed by the application.

Secondly, it can be very useful to use a common policy specication when comparing dierent models together.

AppArmor proles

In an AppArmor prole, the permission granted to a program π over a object o can be one of the following: (r,w,l,m,ix,px,Px,ux,Ux). These permissions are listed in Figure 3.5.

AppArmor proles also constrain access to network resources and POSIX capabilities. However, these are pure access control rules and thus these are not taken into account in our model. Instead, possible information ows related to access to information are captured.

Denition 14. An AppArmor policy P is a set of proles. A prole p P P is a set of rules of the form po, αq where o is an object and α is a permission. All these rules conne a given program π P Π. We formally dene such a prole as follows:

p " pπ, tpo Px discrete prole execute mode/scrub the environment: same as px but scrubs the environment before execution. It will tell glibc to clean the environment before executing the resource, by clearing some environment variables which may be used to modify the behavior of programs. It helps protect against e.g. LD_PRELOAD abuse. This is done by using the kernel's unsafe exec routines (otherwise, the kernel only scrubs the kernel environment in specic situations, such as the execution of setuid/setgid binaries).

ux unconstrained execute mode: no prole is needed to execute the target.

Ux unconstrained/scrub the environment: same as ux but scrubs the environment (see above). In order to compute an information ow policy which we can use in our model, from an Ap-pArmor policy, we proceed as follows:

• For each AppArmor prole, we attach an information tag to each object (persistent containers) whose accesses are restricted by the prole, and we initialize it with a unique identier.

• For each rule of a prole, we infer legal information ows towards the involved objects, and set the policy tags to these objects using the algorithm described in Figure 3.6.

Algorithm

The algorithm presented in Figure 3.6 transforms an AppArmor policy (a set of proles) into an expression of an information ow policy (set of policy tags on containers). Let P be the set of all the AppArmor proles in the policy. For any prole p P P , p.container is the container associated to the binary program constrained by p, p.canreadpq is the list of les on which a read_like access is authorized, p.canexecpq is the list of executable les allowed to be executed, and p.canwritepq is the list of paths where it is allowed to write. T OP represents the set of all atomic information tags in the system (it corresponds to J), inheritppq : bool returns true if the prole p inherits from its parent's prole and false otherwise.

Examples

The following two examples respectively show how we can derive an information ow policy from a simple AppArmor prole, and how intrusions are detected by our model when using such a derived policy as well as how it compares to access control with respect to the detection of illegal information ows (we consider AppArmor being setup in permissive mode ). Here, the security is centered on programs, with no user-related policy rules. {/usr/bin/apache, {(/etc/apache2.conf, w), (/etc/apache2.conf, r), (/www/index.php,r), (/usr/bin/ftpd, px)} } {/usr/bin/ftpd, {(/etc/ftpd.conf,w), (/etc/ftpd.conf,r), (/home/ftpd/data,w)} } /usr/bin/apache ti 1 u ti 1 u tRunpi 1 q, Runpi 2 q, i 3 , i 6 u /usr/bin/ftpd ti 2 u ti 2 u tRunpi 2 q, i 4 u

/etc/apache2.conf ti 3 u tRunpi 1 q, i 3 , i 6 u J /etc/ftpd.conf ti 4 u tRunpi 2 q, i 4 u J

/home/ftpd/data ti 5 u tRunpi 2 q, i 4 , i 5 u J /www/index.php ti 6 u tRunpi 1 q, i 3 , i 6 u J Figure 3.8: Tags derived from the policy /www/index.php, containing a security aw. Arbitrary code is injected and executed through apache. It introduces a malware in the binary code of /usr/bin/ftpd. In this rst part of the execution, the process running apache is not expected to write into /usr/bin/ftpd : the policy tag of this container is not allowed to receive information by a process running apache. Furthermore, the information apache previously read (and guring in its information tag) does not belong to the policy tag of /usr/bin/ftpd. In such a situation, both AppArmor (congured in permissive mode) and our reference monitor would report an alert.

Then, apache runs the modied f tpd. The process running apache is allowed to execute f tpd in the security policy, hence AppArmor would allow this execution. But here, the information tag of f tpd has been modied when the arbitrary code was written into it, and meta-information have been added to it. Those new meta-information do not gure in the policy tag of the process running apache, thus it is not authorized to run f tpd anymore, and our reference monitor would trigger an alert for illegal code execution.

Conclusion

In this chapter, we have presented a model of intrusion detection based on an information ow policy, dynamically checking that it is respected. The policy species which pieces of information may be combined together and which ones the containers are allowed to contain. This model oers high expressiveness since we are able to assign meta-information to any data in the system and to constrain the behavior of programs when those data are involved. The policy expresses restrictions on access to information regardless of where it is located in the system by using a tag system associating meta-information to information containers. We explain how we maintain tags when information ows occur and how we can check whether the policy is respected. A central concept of this model is the execution of programs. This model performs dynamic checking at execution time, and is able to detect executions of illegal code or illegal ows of information. Today's MAC implementations in the Linux kernel come with extensive default security policies. It is possible to set up a policy for the model we propose from an existing MAC policy. We have shown how to derive a Blare information ow policy from an AppArmor MAC policy, and we gave an example of practical use. This model and its implementation (introduced in Chapter 4) represent our rst contribution. Our new model diers from existing information ow models in the literature, such as Flume [START_REF] Krohn | Information ow control for standard os abstractions[END_REF], Asbestos [START_REF] Efstathopoulos | Labels and event processes in the asbestos operating system[END_REF], Histar [START_REF] Zeldovich | Making information ow explicit in histar[END_REF] and other DIFC models, using integrity and secrecy labels for enforcing the information ow policy. Such models are similar to multi-level security and use security classes, but provide declassication mechanisms to application programmers, so as to decentralize the authority. However, in such models, code and data are similarly considered as information, and no distinction is made between the two. For instance, a process labeled with a given secrecy level may not access a piece of code that is stored in a le with a higher secrecy level. On the contrary, our model denes the legal interactions of users and applications' code with respect to each individual pieces of information, allowing to track access to information and the execution of code separately. Furthermore, existing DIFC models do not keep the history of state action itag(π 1 ) itag(π 2 ) itag(/usr/bin/ftpd) alert 0

π 1 " execp{usr{bin{apacheq Runpi 1 q i 2 1
(apache,/etc/apache2.conf,r)

Runpi 1 q, i 3 H i 2

2

(apache,/www/index.php,r)

Runpi 1 q, i 3 , i 6 H i 2

3

(apache,/usr/bin/ftpd,w)

Runpi 1 q, i 3 , i 6 H i 2 , i 3 , i 6 , Runpi 1 q
Both AppArmor and Blare

4

(apache,/usr/bin/ftpd,x)

Runpi 1 q, i 3 , i 6 Runpi 2 q, Runpi 3 q, Runpi 6 q i 2 , i 3 , i 6 , Runpi 1 q Blare only ^π2 " execpf tpdq i 2 , i 3 , i 6 , Runpi 1 q

5

(ftpd,/home/ftpd/data,w)

H

Runpi 2 q, Runpi 3 q, Runpi 6 q i 2 , i 3 , i 6 , Runpi 1 q Table 3.1: Execution sequence information ows. While this last aspect is not required when enforcing the security policy, it is a major advantage when tracking information ows as it provides useful information, e.g., for diagnosis of attacks or malware analysis.

TaintDroid [START_REF] Enck | Taintdroid: an information-ow tracking system for realtime privacy monitoring on smartphones[END_REF] is a related work using taint data in a similar manner, however it focusses on privacy issues by attaching taint information to specic pieces of information, so as to track their illegitimate use. TaintDroid does not allow for a ne-grained policy denition, and instead relies on basic non-interference mechanisms. It is specically designed for the Android platform, and does not allow to track o-the-shelf applications (such as binary applications) which is one of our requirements to provide system-wide supervision.

Chapter 4

Implementation

This chapter presents our implementation, which we built from the model described previously, in Chapter 3. This implementation is the basis for all the experiments which have been conducted during this Ph.D project. It integrates in the LSM framework, with slight modications, and makes use of kernel standard API and data structures. It was designed to provide a generic and versatile implementation ready for future improvements and changes in the underlying model, with manageable performance overhead.

We track information ows within the operating system by using a reference monitor (see Section 1.4.3), which we will call KBlare 1 in the reminder of this chapter. This approach is commonly used to enforce Mandatory Access Control policies in most modern operating systems, where subjects may (or may not) perform a set of operations on objects. We borrowed this principle from access control mechanisms in order to track information ows between such subjects and objects, however we do not enforce any policy, but rather make use of these mechanisms to observe all information ows in a dynamic fashion. We have implemented this reference monitor at the kernel level, as it has several advantages:

• We do not need to modify userspace programs.

• We can monitor a substantial amount of information ows.

• Only kernel exploits may possibly aect our IDS.

Though our model could have been implemented in other operating systems, we have chosen to implement it in the Linux kernel for several reasons: Linux is free and open-source, it has a great community of developers and is used by the industry as well as many individuals and researchers.

Furthermore, with the development of SELinux [START_REF] Vance | Implementing SELinux as a Linux Security Module[END_REF], the kernel developers and the NSA 2 have extended the Linux kernel with a new framework, the Linux Security Modules 3 (LSM), in order to allow dierent security models to be implemented (see Section 1.1.2). LSM is built on top of a set of hooks, initially suited for access control but those can be diverted to implement various security models and policies [START_REF] Wright | Linux security modules: General security support for the linux kernel[END_REF]. Our implementation makes use of these hooks because they provide the following advantages and guarantees:

• The code has been proven to be safe, and the hooks well placed, based on static analysis, avoiding race conditions and such aws [START_REF] Zhang | Using cqual for static analysis of authorization hook placement[END_REF].

• The LSM framework is part of the mainstream kernel and exports a (rather4 ) stable API, 1 KBlare is the name of this reference monitor in our open-source project.

2 National Security Agency of the United Sates of America.

which simplies the task of following the latest kernel versions.

The reminder of this chapter is organized as follows. First, we present an overview of general principles used in our implementation. Then, we present common data structures available in the kernel API, and discuss about some practical considerations regarding their use in our code. After this, we discuss about the operations involved in our analysis, and their complexity in terms of algorithms. Finally, we present all the hooks that we used in order to track information ows within the kernel, and show an exhaustive list of system calls that we track.

Overview

Our implementation builds on top of the LSM framework. Such access control hooks are used by kernel MAC mechanisms, and several modules can be chosen, one at a time, to enforce a dierent kind of security policy. As these hooks have been thought with access control in mind, they are not always practical for information ow control, and we have been obliged to introduced a few supplementary hooks for that matter. Also, we do not make use of all the hooks available in LSM, as a lot of these are specic to access control, and are unrelated to any potential information ow.

Examples of this include hooks related to the flock() system call, dened in fs/locks.c, which triggers security_file_lock(). Except eventual hidden channels making use of the state of le locks, no information ows are involved in such a situation. However, it is unpractical to observe hidden channels, and this is out of the scope of this work.

Kernel access control hooks

The Linux kernel provides mandatory access control mechanisms, but this is not the only access control implementation available. Traditionally, discretionary access control has been used for years, and it is still the case by default on many Linux distributions. Discretionary access control has precedence over mandatory access control, in such a way that if an access is denied by DAC mechanisms, the code will return without reaching MAC related hooks and functions, as shown on Recall that in our model, taint marking is performed at each object level by appending (taint) elements in sets called information tags, in ℘pI Y X q. Information tags are attached to objects, or containers and describe their content. Those tags are represented as ordered sets of integers in this implementation. Positive integers represent elements of I, whereas negative integers represent elements of X :

•

I " N • X " N Éxample 8
. This is a valid information tag : {1,2,3,4,5}

The policy, determining the legality of information ows, is dened at each object level by a set of sets in ℘p℘pI Y X qq called policy tag.

Example 9. The following is a valid policy tag : { {1,2,3},{-4,5,6},{7,8,9} } Tags are represented dierently in system memory and on the lesystem. When representing tags in system memory, operations such as checking the legality of an information ow, or appending taint data to an existing tag must be ecient in terms of CPU and memory space. When representing tags on the lesystem, we aim to minimize the impact on input/output operations.

The following section is a discussion about possible data structures to be used amongst those available in the Linux kernel.

Granularity

This implementation is based on Linux abstractions. The containers of information that we described in our model in Chapter 3 are operating system objects, including les, sockets, memory pages, pipes, network packets etc.. In order to track information ows, we attach meta-information to such OS objects. Thus, the level of granularity of our analysis is bound to the granularity of these objects. Because les are the only persistent objects of the operating system (i.e. stored on the lesystem, and available after reboot), we dene the initial content of les as atomic information, as this is the nest level of granularity that it is possible to observe at the operating system abstractions level (e.g. we cannot distinguish information from two distinct bytes nor two distinct lines of a le from the OS perspective). In a word, information tags are attached to each OS object, and describe which atomic information are contained in those objects, as well as the origin of their content.

File Meta-information Whenever an information ow occurs towards a le, its information tag is updated so as to match the new content.

le 1 i 1 le 2 i 2 . . . . . .

Data structures

The choice of data structures to be used is important, especially because our code runs in kernel space, where memory has a much higher cost than it has in userspace, because memory is mostly allocated in a physically contiguous manner, but also because there is a limited amount of memory available for the system kernel. It is also important to pay particular attention to evaluating the cost of all operations required by our analysis, as these occur for each information ow between subjects and objects of the operating system, and this may considerably aect overall system performances. Information tags are sets of elements which could be represented as bitmaps, arrays of integers, binary trees, linked lists and other data structures. Policy tags are each composed of multiple sets, and may also be represented by such data structures. The following outlines our choices and compares data structures suiting our requirements. We equally refer to tags as policy tags or information tags, i.e. ordered sets of meta-information.

Bitmaps

Bitmaps can be implemented with any contiguous zone in memory, such as C arrays. When representing a set with a bitmap, each bit represents a distinct element of the set, and its value in t0, 1u represents respectively the absence or presence of this element in the set. Therefore, we need as many bits in the bitmap as there are atomic information to represent.

• Advantages : this leads to very fast logical operations using masks (logical AND, OR, etc.) to test the presence of individual or multiple elements at once.

• Drawbacks : it is memory hungry in situations where many les are labeled (i.e. the bitmap must contain as many bits as there are labeled les in the lesystem initially). Bitmaps also have a xed size, which is not practical for our analysis, because the actual number of meta-information in information tags is dynamic.

Bitmaps provide good performances in the case of analyses supervising a reduced subset of the lesystem. It would be suitable if we enforced the policy instead of tracking information ows, as described in Chapter 7 (in this case, the upper bound of the size of information tags depends on policy tags ), but in the present case, these are impractical when the system grows larger due to memory limitations.

Bloom lters

Bloom lters [START_REF] Broder | Network applications of bloom lters: A survey[END_REF] are probabilistic and space-ecient data structures, and are used to represent sets of information. Testing the presence of an element in a set represented by a bloom lter can be subject to false positives, but not to false negatives. Elements can be added to the set, but not removed. Adding elements increases the probability of false positives. A bloom lter relies on a bitmap along with a variable number of hash functions. When the bloom lter is empty, all bits of the bitmap are set to 0. For any given element of the set, each hash function maps it to one positions in the bitmap, with a uniform random distribution. Adding an element to the bloom lter is done by rst passing it to each hash function, and then by setting the mapped bits to 1. Testing the presence of an element is done by checking that all the mapped bits (through all of the hash functions) for a given element are set to 1. If any of the bits is not set to 1, then it is guaranteed that the element is not present in the set. Otherwise, the element may be present. Examples of use of bloom lters include symbols resolution by the dynamic linker to load shared libraries on Linux [START_REF] Drepper | How to write shared libraries[END_REF], where a hash table is traditionally used for the resolution. Using bloom lters to test the presence of an element before the actual lookup in the hash table leads to a dramatic increase in lookup time by ltering 80% to 90% of the unnecessary lookups. Bloom lters may be used in the same manner to avoid unnecessary lookups in policy tags, but using such a structure to represent information tags would increase the number of false positives in our intrusion detection model (i.e.

increasing the number of intrusion alerts where no actual intrusion occurred). Policy tags may also directly be represented with bloom lters. Each policy tag being composed of several sets, it would require the same number of bloom lters to represent each set of the policy. However, this would lead to false negatives in our intrusion detection model, as information may be wrongly reported as present in the sets of the policy, thus allowing illegal information ows to occur.

Linked lists

The Linux kernel provides an implementation of doubly linked lists in include/linux/list.h. In the case of our implementation, doubly linked lists provide a scalable alternative to bitmaps, where the size can be dynamically adjusted by inserting or removing elements without signicant change in the underlying structure.

• Insertion and deletion time is in θp1q.

• Fusion sort is in Opnq time if the lists are preliminary sorted (which is the case here) or Opn.logpnqq otherwise.

Trees

The Linux kernel provides rbtree.h, an implementation of the so called Red Black Trees 5 . Inser- tion, deletion and iteration cost is Oplogpnqq. According to the Linux kernel documentation, in Documentation/rbtree:

Red-black trees are a type of self-balancing binary search tree, used for storing sortable key/value data pairs. This diers from radix trees (which are used to eciently store sparse arrays and thus use long integer indexes to insert/access/delete nodes) and hash tables (which are not kept sorted to be easily traversed in order, and must be tuned for a specic size and hash function where rbtrees scale gracefully storing arbitrary keys).

Red-black trees are similar to AVL trees, but provide faster real-time bounded worst case performance for insertion and deletion (at most two rotations and three rotations, respectively, to balance the tree), with slightly slower (but still O(log n)) lookup time.

Arrays

Arrays can also be used to represent sets. An array of int of size N for instance, noted int[N] in C, may be used to represent up to N distinct elements, with a memory load of N ˆsizeof(int), where sizeof(int) " 32 bit (or 4 bytes) on all architectures. Allocating such an array has a very bad impact on kernel memory, as the kernel memory allocator needs a contiguous slab of N ˆ32 bits of memory.

Practical considerations

The number of atomic information in a container at a given time can vary from zero to potentially (but unlikely) all the information of the lesystem (e.g. in the case where a single le, process or other object contains data from all the les of the lesystem). However, a lot of containers contain only one atomic information. Such containers include containers exclusively accessed read-only by all processes, and in this case their information tags are never tainted with any new metainformation. Usually, most containers have an asymptotic limit of possible content from various les of the lesystem. The memory overhead of tags depends on:

• The number σ of distinct meta-information in the system (i.e. how many les were initially labeled with distinct meta-information).

• The average size (length) l of tags, i.e. from how many sources does the content of containers come from.

Dynamic vs static

In the following, c 1 and c 2 are two constants respectively representing the memory space requirement per element in a static (xed-size) structure and in a dynamic structure (e.g. c 1 " 1 in the case of a bitmap). When using xed size data structures, such as bitmaps, the memory overhead m of tags is constant, and l " σ, thus: m " σ ˆc1

Conversely, using dynamic data structures, such as doubly linked lists, to represent each set of the tags, the memory overhead m depends on the average length l of tags :

m " l ˆc2

Example 10. Figure 4.3 is an example of a lesystem from a production server, running several services including a web server and a database. The lesystem of this server contains 66544 les. Figure 4.4 shows the maximum memory overhead per set of meta-information represented as bitmaps, arrays and doubly linked lists, considering that all the 66544 les have been labelled

initially. Using bitmaps requires a constant size of 66544 for each set, where using doubly linked lists requires pp32 `8q ˆlq 6 bits per element of the set, and arrays of integers require 32 ˆl bits per element of the set.

---# find / -print | wc -l 66544 --- The example on Figure 4.4 shows that, in the case of a lesystem containing 66544 les, it is preferable to use dynamic data structures when the average length of tags is below around a thousand of les. When containers contain information from a limited number of distinct sources, using dynamic data structures leads to a more ecient memory management. This can be generalized as follows, where l is the average length of tags.

pc 1 ˆσ " l ˆc2 q ô l " σ ˆc1 c 2

Memory allocation in the kernel

Another critical aspect to consider is the way the kernel handles memory. In order to minimize fragmentation due to allocation and deallocation of memory inside the kernel, the developers 6 Linked lists of integers require at least an integer and two pointers (4 bit each) per element, sizeof(int) = 32 and sizeof(struct list_head) = 8.

introduced a new mechanism called slab allocation [8]. This mechanism is based on the fact that initializing and destroying objects has a superior cost than allocating and freeing memory for the same objects. The so-called slab allocator maintains caches of the same objects types, so that the basic structure of frequently used objects is preserved between uses. When allocating memory for untypical object types, with uncommon sizes, the kernel does not directly make use of slab caches, but rather allocates chunks of contiguous memory to t the objects. This is handled by the buddy allocator, which maintains caches of multiples sizes ( 2k page frames each), and delivers a chunk of memory of the most appropriate size, from those available. This process involves some waste of memory: for any object o, there is a waste of 2 k ˚sizeof ppageq ´sizeof poq. The slab allocator itself is built on top of of the buddy allocator, so as to eciently maintains caches of 2 k pages.

In order to keep memory overhead small, it is preferable to work with small objects with common sizes, so that a slab cache is available, rather than big chunks of memory, which is more dicult for the kernel to handle, and is more likely to waste memory. In order to allocate and free contiguous chunks of memory, the kernel provides, the two functions kmalloc() and kfree(). These are implemented on top of the slab allocator, and the kernel maintains pools of various sizes for this purpose.

Tags in kernel memory

Operations such as checking the legality of information ows, updating information tags etc. are done in kernel memory, on behalf of processes, which are the active agents responsible for all information ows [7].

Information tags

In the previous section, we have shown in paragraph 4.2.1 that using dynamic data structures minimizes memory overhead in the cases where the average number of meta-information per tag does not exceed a certain limit. In paragraph 4.2.1, we also made some considerations about the average size of tags, being either limited to a single meta-information in some cases, or bound by an asymptotic limit in other cases. Finally, we have shown that allocating small data structures with common types is handled eciently by the kernel, by using slab caches. We therefore chose to represent information tags, being ordered sets of integers, in doubly linked lists, as represented on Figure 4.7. We may also have chosen to use red black trees, as both structures allow for dynamic expansion of data and make ecient use of slab caches. However, as it is shown later in this chapter, the operations we perform in our information ow analysis require iterating over all the elements of information tags, which makes doubly linked lists, as available in the kernel API, the most simple and ecient way to represent such ordered sets of integers. Information tags are represented by the following structure in the code of KBlare (dened in security/blare/blare.h): where node is a structure containing information related to the list layout (list_head being the type for list nodes in the kernel API, containing pointers to the next and previous nodes), and value is an integer representing one atomic information. We decided to encode information as follows: positive values represent data (i.e. elements of I), while negative values represent executed code (i.e. elements of X ).

i N i 3 i 2 i 1

Policy tags

Policy tags describe the legal content of containers. Contrary to information tags, such tags are statically dened, and thus are rarely modied, these may only be updated when changes happen in the policy. The policy attached to a container is a set of multiple ordered sets, each describing one possible combination of legal content. Each ordered set within the policy tag is represented as a balanced binary tree. It makes verifying the legality of information (against the policy) faster than it would be with a linear structure, as search operations in a binary tree are performed in Oplog 2 pnqq. Binary trees of the same policy tag are linked together inside a linked list, as the process of verifying the legality of information consists in iterating over all the sets of the policy until one makes it legal. In other words, policy tags are linked lists of binary trees.

a 2 a 1 b N r 1 r 2 c N c 1 c 2 r N a N b 1 b 2

Execute policy tags

Recall from Chapter 3 (Section 3.6.1) that the policy regarding programs and executable code is distributed in the execute policy tags of objects. We refer to this subset of the policy as the execute policy and it is stored:

• On disk, in the extended attributes of les containing executable code (e.g. binary les and shared libraries) which we want to conne, as described later in this chapter.

• In memory, in the execute policy tags of processes, shared memory mappings, pipes, queues and sockets, which we will further discuss here.

The semantics diers in each case. The execute policy tags of les are used at runtime (along with the policy of users) to determine the policy tags of processes (as presented in Chapter 3). When attached to processes, execute policy tags are stored in kernel memory, and are updated whenever processes either execute or read some code (e.g., a shared library) with an information ow policy attached to it (i.e. the le containing the code has an execute policy tag ). In such a case, the execute policy tag of the process is tainted by the execute policy tag of this executable content: we compute a new tag containing the common set of both execute policy tags, as described later in this chapter, in Section 4.6.2. The aim of tainting processes with execute policy tags is to make sure the execute policy of all executable content that has been accessed is kept when new information ows occur towards other containers. The following example shows a possible issue which happens if we do not taint objects with execute policy tags.

Example 11. File /home/alice/flash_plugin.bin has the following execute policy tag : {{1,2,5},{-1,2}} Now imagine that Alice (or any program on her behalf ) runs : alice@alicebox:"/ cat flash_plugin.bin > .firefox/plugins After running this command, the shell will fork and execute cat, which in turn will read flash_plugin.bin, and output its content to another le in .firefox/plugins. The new le will not have any execute policy tag attached to it unless we do make sure execute policy tags get tainted.

To overcome this issue, we need to ensure that :

• Whenever a process reads a le or other object containing executable code, we read the execute policy tag of this object, and append it to the execute policy tag of the process.

• Whenever a process writes to an object, it appends its execute policy tag to the execute policy tag of the object.

By doing so, we make sure that all objects have their execute policy tag updated when code gets copied to another object. Whenever a new subset of the execute policy (i.e. an element of ℘p℘pI Y X qq), bound to a piece of executable information, is read or executed, it is included 7 in the execute policy tag of the current process. When processes write information to les or shared memory mappings, the execute policy tags of these objects also get tainted the same way.

Tags on disk

The persistence of a system with everything running into memory is very limited. It would also be very inecient in terms of memory to maintain in-memory data structures for every object, especially for every le of the lesystem. In order to be able to restore the state of the system after rebooting, or to be able to free in-memory information tags of les no longer accessed by any running process, tags are stored on disk, in the extended attributes of the lesystem, in the form of name:value pairs, each containing up to 64 KB of binary data 8 . We store values in the security namespace (security.*), as used by the other LSM modules.

• Information tags use one eld of the extended attributes: security.blare.info

• Policy tags and execute policy tags use several elds (one key:value pair for each ordered set of the policy). For a policy tag with N subsets, elds names are: security.blare.policytku, with 0 ď k ă N

For an execute policy tag, elds names are: security.blare.xpolicytku, with 0 ď k ă N .

Example 12. The policy tag { {1,2,3},{-4,5,6},{7,8,9} } of a given le, would be represented in three distinct key:value pairs:

• security.blare.policy0

• security.blare.policy1

• security.blare.policy2

Serialization

Serialization is the process of converting data structures from an in-memory format, into a format that can be stored, or transmitted over a network connection, in such a way that it can later be restored back to its original live form, by an operation called unserialization. We need a serialization mechanism in our implementation, in order to be able to store live tags into the extended attributes of the lesystem, and to restore live tags back into memory when processes access information stored into les not currently in use. The extended attributes are represented on disk as at and contiguous sets of bytes. Such a representation requires an intermediate structure that is contiguous in memory, so that we can dump it into a key:value pair (i.e. we cannot write non contiguous data structures in the extended attributes). We chose to use ordered arrays of integers for this purpose. On access to les, meta-information into tags are converted from their disk representation to their memory representation, and vice-versa.

7

The result is the union of the two sets of sets. 8 According to the manpage of attr, extended attributes on XFS lesystem objects on Linux.

• On read accesses, meta-information is read from the extended attributes and converted into a live representation (tree or list).

• On write accesses, meta-information is written to the extended attribute and thus converted into a linear representation (continuous memory region).

Example 13. int array [6] allocates 6 * sizeof(int) in a contiguous region of memory.

In kernel code, operations that we can perform on inodes, such as operations on the extended attributes, are associated to each inode structure. The following two operations are used in our implementation, and are available after lesystem initialization (the kernel would return -EOPNOTSUP 9 before this stage, or when extended attributes are unavailable on the lesystem in use).

inode->i_op->getxattr(dentry, name, buffer, size) inode->i_op->setxattr(dentry, name, buffer, size)

Users policy

Recall from Chapter 3 that in our model, the information ow policy is composed of three distinct subsets, P Π , P U and P C P , respectively expressing the policy regarding executable code, the policy regarding users, and the policy regarding containers. The following gives implementation details about P U .

On disk

A user policy denes what a user (or uid) is allowed to do. In practice, it is used to determine which subsets of information a process on behalf of a given user is allowed to access. For each uid, a user policy can be dened, and is similar to the policy tag of containers in the sense that it is a set of ordered sets.

Example 14. The following is a valid user policy : { {1,2,3},{-4,5,6},{7,8,9} }.

Where the policy tags can be stored in the extended attributes of each le, user roles need to be centrally dened somewhere on the lesystem. The policy for each user (uid) can be dened and stored, from userspace, in the extended attributes of a le /etc/blare/uid. This ensures that the users policy is stored in a persistent fashion, and it allows us to restore it at boot time.

In memory

The policy for each user is stored in a linked list of binary trees, the same way policy tags and execute policy tags are represented in memory. It is used at runtime along with execute policy tags to compute the policy tags of processes (as presented in Chapter 3).

Communication between userspace and kernelspace

The kernel should not directly read the special le storing users policy in the lesystem (/etc/blare/uid) because the location of such le is a policy and thus should not be dened within kernel code. Instead, we use the securityfs interface (mounted as /sys/kernel/security), which exports a pseudo-lesystem available from userspace, to load users policy at boot time. For each user, a special le is created in the pseudo-lesystem, thus allowing the system administrator to load the policy (set of sets) of this user. Each set of the policy that is loaded this way is copied into kernel memory, into a policy tag attached to the appropriate user id. Each special le is named after the uid of the corresponding user, and is created in /sys/kernel/security/blare/users. When a running process on behalf of a user runs the exec system call, it checks whether a policy has previously been loaded in kernel memory for this user, and uses it along with the execute policy tag of the executable le.

9 Return code standing for operation not supported.

Operations and complexity 4.6.1 Updates on information tags

Information tags are updated when information ows occur (the destination container's information tag is updated). If both the source and destination containers are in memory (sockets, processes, IPC, . . . ), the involved operation is the fusion of two linked lists, which complexity is Opn `mq for two lists of respective sizes n and m. If one of the containers is a le, a conversion from/to a linear structure is needed (see Section 4.4.1).

• On read operations from les, the extended attributes are dumped in a memory buer ( of type int*). We iterate over the resulting array, and store each array value in the (inmemory) information tag (linked list) of the current process performing the read operation.

See itag_insert from security/blare/itag.c.

• On write operations, we overwrite the information tag of the le with the information tag of the current process. We iterate over the linked list, and create an array of integer from it, so as to write it into the extended attributes. See blare_write_info from security/blare/itag.c.

• On append operations, we rst read the information tag of the le, append it together with the information tag (linked list) of the current process into an array of int and write the new array to the extended attributes of the le.

A process P reading information from a container C has its information tag updated as follows:

itagpP q i`1 " itagpP q i Y itagpCq i where i `1 refers to the state of the tag after the information ow occurred, and i refers to the state of the tag before the information ow occurred.

Updates on execute policy tags

Execute policy tags of processes are also updated dynamically, whenever an information ow occurs, potentially involving executable code conned by the execute policy. This operation involves the restriction of two policy tags against each other, i.e. the intersection of all the sets of one execute policy tag with all the sets of the other one. If we consider the fusion of two execute policy tags

A " pa 1 , a 2 , . . . , a n q and B " pb 1 , b 2 , . . . , b m q, then the complexity of this operation is in Opn 2 .m 2 q.

We dene this operation as A [ B, as presented in Denition 11 previously in Chapter 3. It is implemented by the pseudo-code described in Figure 4.9.

Legality check

To verify the legality of an information ow between two containers, we check that the information tag of the destination container (C dest ) is legal with respect to its policy tag:

DS P ptagpC dest q|itagpC dest q Ď S
The legality check is performed by iterating over the information tag of C dest , checking that all of its elements belong to its policy tag. This is a linear operation with respect to the size of the information tag. Its complexity is in Opk ˆ ˆlog 2 pnqq, where k is the length of the involved information tag, l is the number of subsets of the policy and n is the maximum size of the sets of the policy.

System calls and hooks

System calls are the interface between applications and the kernel. A lot of operations such as opening les, creating shared memory mappings or executing programs involve system calls, most 10 rather than directly invoking the underlying system calls. It is necessary to track system calls in order to track information ows between processes. The LSM framework provides hooks for tracking system calls involving access to information. In Appendix A, we provide a detailed list of the system calls in the Linux kernel version 3.2, where system calls which may lead to information ows are identied. In this section, we show how our reference monitor uses LSM hooks and which system calls correspond to it. All the hooks that we use are dened in security/blare/lsm_hooks.c. The LSM framework made changes to the structures used in kernel space to represent kernel objects, including le descriptors, inodes and processes credentials, by adding an opaque security eld of type void*, that the LSM modules can use to store their own security attributes [START_REF] Wright | Linux security modules: General security support for the linux kernel[END_REF]. Furthermore, processes credentials 11 have been extended to support concurrent access, and now have a supplementary void* security eld to store opaque structures. The credentials (including the security eld) are protected by Read Copy Update (RCU) mechanisms [START_REF] Mckenney | Introducing technology into the Linux kernel: a case study[END_REF].

Special structures

As previously described in our theoretical model in Chapter 3, containers of information are separated into three classes: volatile objects, persistent objects (i.e. backed on the le system), and processes. The blare_tags structure is used for all volatile objects. It is dened as follows: Where info is a pointer to an information tag, policy is a pointer to a policy tag, and xpolicy is a pointer to an execute policy tag. Files and processes have their own data structures, respectively blare_file_struct and blare_task_struct and are described later in this chapter. [START_REF] Broder | Network applications of bloom lters: A survey[END_REF] The GNU C library is the most common C library on Linux, often called glibc. 11 Credentials are used to store various security information related to processes, and are attached to the task_struct structure in the cred eld. See documentation/credentials.txt in the kernel source tree.

Fork and clone

Fork When a process forks by calling the libc function fork (which in turn calls the clone system call with special ags), the resulting child process is an exact copy of the parent process in terms of memory, except for a couple of properties (listed in the manpage of fork ( 2)). A number of ags may aect the behavior of fork, by determining how the parent and the child may share system objects. Amongst those ags, MADV_DONTFORK, which can be set on memory mappings using the madvise system call, aects the semantics of possible information ows between the child and the parent. Memory mappings (described in the next subsection) are normally inherited during the fork process, unless those have been marked with this ag. Similarly, the set of open le descriptors is inherited by the child, however we track the actual access to les (through fread or fwrite system calls), so this does not aect our analysis. The same goes with open message queue descriptors, as we track actual calls to msgget. In all cases,

• The child's information tag is an exact copy of the parent's information tag.

• The child's policy tag is an exact copy of the parent's policy tag.

• The child's execute policy tag is an exact copy of the parent's execute policy tag.

Clone

The clone system call is mostly used to create threads. When the CLONE_VM ag is passed, the child process uses the same address space as the parent (and any call to mmap or munmap aects both processes). Otherwise, the child process has its own address space. In this later case, existing anonymous shared mappings of the parent are shared with the child. If the CLONE_NEWIPC ag is passed, then the child uses a new IPC namespace, and will not be able to see the objects created in the parent's namespace. If this ag is not set, the child shares the same IPC namespace, and is able to access shared memory segments through shmat and messages through msgget. In the case of shared memory segments, KBlare considers an over-estimate of the possible information ows from the time when the segment is attached with shmat until it is detached with shmdt. 12 We do not track individual threads in our current implementation, because all threads of a process share the same address space. Therefore, there is no way to dynamically track information ows between threads. In order to track threads individually, it would be necessary to ensure no information ow can possibly occur, by auditing the code, which is out of the scope of this work.

Related hooks

13 RCU stands for Read Copy Update, it is a low overhead synchronization mechanism widely used in the Linux Kernel. See McKenny and Walpole's work [START_REF] Mckenney | Introducing technology into the Linux kernel: a case study[END_REF] for more about RCU.

Memory mappings

In this section, we describe separately how KBlare deals with shared memory mappings (i.e. mmap) and shared memory segments (System V shared memory, i.e. shmat).

Mapping a le to memory

Processes have the ability to create memory mappings, by calling the mmap system call. Memory mappings are often used to map the content of les to memory, but they can also be used without any underlying le. In this case, it is similar to shared memory segments (as described in the next subsection).

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

Any mapped le can be unmapped by calling the munmap system call. Amongst the possible ags, MAP_PRIVATE, MAP_ANONYMOUS and MAP_SHARED change the behavior of memory mappings, and how other processes may access it.

• MAP_PRIVATE: the memory mapping is not visible by other processes, and changes made to the mapping are not backed to the underlying le. Conversely, changes to the underlying le may or may not aect the memory region, this behavior is unspecied by the POSIX specication. In order to keep a conservative approach, changes to mapped les should update memory mappings as well in our implementation. This particular aspect is not taken into consideration in our current implementation, and it will be xed in the future.

• MAP_SHARED: updates on the memory mapping are visible to other processes mapping the same le. Content is also updated on the lesystem, but it may not actually be updated until msync or munmap is called. Note: Calling mmap with MAP_SHARED before a fork will make those mappings available to the child.

• MAP_ANONYMOUS: the memory mapping is not backed to any le. The information is kept in memory.

Anonymous shared mapping are available to the child after a fork (MAP_ANONYMOUS|MAP_SHARED).

The protection ags also aect the way information may ow between processes and a mapping (these ags are enforced by the hardware, when possible):

• PROT_EXEC allows execution of the pages' content.

• PROT_READ allows reading the pages.

• PROT_WRITE allows writing to the pages.

In our implementation, information tags are attached to shared memory mappings, when those allow at least write access to the owner process 14 . Non shared memory mappings directly aect the process's information tag in a way that is similar to the other le system operations. Information ows between a process and a shared memory mapping are tracked until the process unmaps the le (or memory region in case no le descriptor exists).

Hooks

KBlare tracks calls to both mmap and munmap. The latter is not part of the LSM framework and had to be manually added in our kernel patch. The following hook ensures that we update the information tags of processes having access to mapped les or regions:

14 Non writeable mappings occur quite frequently, e.g. when loading shared libraries. Such mappings are equivalent to reading the le, in terms of information ows static int blare_file_mmap(struct file *file, unsigned long reqprot, unsigned long prot, unsigned long flags, unsigned long addr, unsigned long addr_only);

The semantics is the following, when pages are writeable:

• In the case of non anonymous shared mappings, a blare_tags structure is attached to the le descriptor of the mapping, in its file->_security eld, in order to store the information tag of the memory mapping (we do not set any policy on the mappings, the policy verication is left to the processes, as described in the model in Chapter 3).

• In the case of anonymous shared mappings, only the child process may have access to it, unless MADV_DONTFORK was set. No le descriptor is available for this kind of mappings, as it is not backed to any le. Information tags of the parent and the child have to be kept synchronized until one of them releases the mapping. This is not supported in our current implementation. A special ag should be added to blare_task_struct, and set to 1 for all parents having child processes sharing memory mappings with them (this can be done in security_task_create).

• In the case of non anonymous non shared mappings, information is backed to the le in case of changes to the mapping.

System V shared memory

From userspace, shared memory segments are allocated by processes invoking shmget. Once a shared memory segment is created, processes can attach it to their address space by calling shmat.

If the SHM_RDONLY ag is passed, then the calling process has read-only access to the memory segment, and otherwise it has read and write access to it. Processes detach memory segments from their address space by invoking shmdt.

Hooks

The LSM framework provides a hook for shmat, but a hook for shmdt had to be manually added in our patch set, in order to be able to stop tracking processes after a shared memory segment is released. A process attaches a shared memory segment to his address space by invoking the shmat() system call. KBlare tracks this system call with the security_shm_shmat hook, with a callback on the following function in our security module: static int blare_shm_shmat (struct shmid_kernel *shp, char __user *shmaddr, int shmflg);

KBlare maintains a list of currently attached shared memory segments for each process (in cred->security->shm). For each memory segment of the list, a pointer to the tags of the memory segment (of type struct blare_tags), as well as the ags determining the access mode (e.g., SHM_RDONLY) are stored in the following structure:

struct blare_shmptr{ struct list_head node; struct blare_tags *ptr; int shmflg; //shmat() flags, i.e. SHM_RDONLY etc. };

Processes detach a memory segment from their address space by invoking the shmdt system call. KBlare tracks this system call with the security_shm_shmdt hook, with a callback on the following function in our security module: static void blare_shm_shmdt(struct shmid_kernel *shp); On release of a memory segment, the following actions are performed:

• The information tag of the current process is updated with the information tag of the shared memory segment.

• The memory segment is removed from the list of attached memory segments for the current process (cred->security->shm).

Access to shared memory

As previously mentioned, access to attached shared memory segments is not subject to any system call and is not tracked by the operating system. Therefore, KBlare calculates an overestimation of the possible information ows between a process and its attached shared memory segments.

• When a process P reads new content and updates its information tag (e.g., by reading information in a le or socket), all the shared memory segments it has attached with write (read and write) access also have their information tag updated.

• Before any process writes or appends information to a container, the information tags of all the attached shared memory segments are merged into the process's information tag.

Files and pipes

The most common way for processes to access information is certainly through the lesystem.

Processes access les using system calls. Amongst available system calls, fopen and fclose are used to respectively open and close a le descriptor. When a le is opened, a ag called open mode is specied, and takes a value in {a,w,r}.

• r opens the le in read mode if it exists.

• w opens the le in write mode or create it if it does not exist. Any content in the le is overwritten (the le is truncated to zero length).

• a opens the le in append mode, content may be written at the end of the le, and existing content cannot be altered.

• Furthermore, r+, w+ and a+ are also valid modes. r+ is like r with write access allowed, w+ and a+ are like w and a with read access allowed After this, input/output access is performed by read and write or pread and pwrite. The p variants allow to read or write from a given oset. These system calls are responsible for information ows between processes and les, and are tracked in KBlare. Similarly, pipes can be created with the pipe system call, and accessed with the system calls read and write.

Hooks

In the LSM framework, access to les and inodes is veried by two distinct hooks: security_file_permission and security_inode_permission. In kernel space, le descriptors may describe regular les or pipes. Each le descriptors is linked to an underlying inode (except before lesystem initialization). When it describes a pipe, the inode has a special eld i_pipe, which we use to distinguish it from regular les. However, inodes are also used by sockets, and other objects. As the kernel relies on inodes in many cases, hooking inode accesses results in a lot of callbacks for each process. In our implementation, we rather verify access at other levels. In the case of les, the security_file_permission hook triggers the following callback: static int blare_file_permission (struct file *file, int mask);

where file is a pointer to the le descriptor, and mask is the access mask (which determines the access mode). KBlare stores its security attributes in the opaque security pointer eld of the file structure, as introduced by the LSM framework: file->f_security. Recall from Section 4.4 that tags associated to les are stored in the extended attributes of the lesystem. Such a representation is at, i.e. it is represented as a contiguous region of memory.

• When a process reads a le, KBlare reads the extended attributes and stores it in the info_array data structure, and sets info_size to the size (number of elements) of the array. This is later converted into a live representation, as previously described in this chapter in Section 4.3.

• In the case of pipes, no extended attributes are used, as pipes are residing in memory, and the live representation is used directly by using a blare_tags structure.

Message queues

Message queues are another inter process communication mechanisms allowing processes to exchange so called messages, stored in queues. Messages have a priority, and messages with the highest priority are delivered to the receiving process rst. Linux implements POSIX message queues, as well as SYSV message queues. Both use a distinct API.

SYSV message queues

As with les, and other data structures, SYSV message queues as well as their messages themselves have been modied by the LSM patches to add an opaque security eld. The security eld of this structure is used by KBlare to store its tags (in a blare_tags structure).

Related hooks

Two hooks are used by KBlare, and are triggered upon sending or receiving messages: security_msg_queue_msgrcv and security_msg_queue_msgsnd. One of the caveats with the reception of inline messages (i.e. fetching the rst message available in the queue) is that the target process is not equal to the current process 15 in this portion of the code (the kernel runs in a dierent context). Whenever the target diers from the current process, we are unable to alter the credentials of the receiving process, because of the RCU protection mechanisms, forbidding a task to alter other tasks' credentials (there are good reasons [START_REF] Debar | Towards a taxonomy of intrusion-detection systems[END_REF] for this, as it would make the credentials management much more complex). The best way we found to work around this was to force the scheduler to wake up the target process:

/* We cannot alter target's credentials unless it is the current process */ if (target != current) wake_up_process(target);

POSIX message queues

Posix message queues make use of inode structures to pass messages. This could be tracked by using the security_inode_permission hook, but it is not yet supported in our implementation. The socket structure has a pointer to a sock structure, containing the network layer representation of sockets. This is a quite complex structure, and we will not fully describe it here. The sock structure contains a eld called sk_family, and we use it to determine whether sockets are of type AF_UNIX or AF_INET. As other volatile objects, sockets are labeled by KBlare with a blare_tags structure, attached to their opaque security eld. This eld is dened in the sock structure as sk_security of type void*.

Related hooks

Communication over AF_UNIX sockets is monitored by two hooks. Sending messages is caught by security_unix_may_send, and receiving messages is caught by security_socket_recv_msg. This later hook is also triggered when receiving information through internet sockets, and KBlare treats both cases in the same place, by determining the kind of socket. Sending messages over AF_INET sockets is caught by security_socket_sendmsg.

Netlink messaging

Netlink is a communication mechanism between kernelspace and userspace. It uses BSD sockets of the AF_NETLINK family. It can also be used to communicate between userspace processes, even thought this is not its primary goal. Netlink messages are not supported yet in KBlare, this is left for future work. At the moment, the following stubs are dened:

Network Extension

In the previous chapters, we have introduced a model of intrusion detection based on taint marking techniques. It tracks information ows between objects of the operating system, and allows to detect abnormal behavior caused by intrusions on a local host. The next step towards detecting intrusions in distributed systems is to track information ows at the network level. This chapter presents a network extension to the previous model, adding further control over information with respect to outgoing trac (the more complex case of incoming trac is presented in Chapter 6). We have extended the previous information ow policy with a so-called network policy, stating how information may leave the system, restraining sockets given the current (user, code) context. Furthermore, we have developed a framework that allows users to trace how their private data is used by applications, and to monitor sensitive information that ows out over the network. This led to experiments presented in Chapter 8, and to a publication in the proceedings of the Australasian Information Security Conference (AISC) 2012 [START_REF] Tronel | A taint marking approach to condentiality violation detection[END_REF]. Details regarding the implementation of this network extension are presented in Chapter 7.

Overview

Most of today's personal computers rely on untrusted third party applications such as browser plugins or so called `apps'. Many of these are closed source, which makes static analysis extremely dicult (if not impossible) in the case of native code. And even in the case of opensource applications, there is always a risk of security aws or coding errors potentially leaking sensitive data.

Dynamically detecting the leak of sensitive information is challenging given that:

• One application can exchange information with another through IPC, shared memory, etc.

• It is impractical to modify o-the-shelf applications; instead, we prefer to implement a reference monitor in the operating system kernel as a more pragmatic solution.

• The performance overhead must be small to maintain a responsive system, i.e., not aecting the user's experience and causing them to disable the security mechanisms.

As presented in Part II, we use dynamic tracking of information ows between objects of the operating system. A dening aspect of our approach is that we distinguish data from containers : data is the actual information we track, whereas containers are storage entities such as les, memory pages, etc. Sensitive data is rst identied and their containers are labeled with meta-data called tags. As information ows between containers, tags are dynamically updated to reect the containers' content. When it comes to protecting sensitive data against leakage by untrusted applications or via malware that exploits security aws, existing approaches have several limitations. Individuals can use software rewalls on their internet-connected personal/portable computing devices to lter network connections without changing the security policy of the underlying operating system. However, while such mechanisms may successfully protect a host from outside threats, they typically do not prevent the leak of information by untrusted or miscongured applications.

Deep packet inspection rewalls are able to identify data patterns in network packets, however this approach is too coarse-grained to eciently track the presence of sensitive data in network exchanges and is thus not an eective solution to protect against sensitive data leaks. Mandatory access control tools such as AppArmor [START_REF]Apparmor, application security for linux[END_REF] and Tomoyo [START_REF] Harada | Access policy generation system based on process execution history[END_REF] are similarly not practical when it comes to protecting condentiality:

• When used in enforcement mode, information ows are blocked, which may break some functionalities. This eectively renders the approach unusable for most end users.

• When used in permissive mode, these tools are unable to track indirect information ows [START_REF] Geller | Information ow control for intrusion detection derived from mac policy[END_REF].

Figure 5.1 presents our approach to taint tracking for monitoring data leaks. A kernel reference monitor has been implemented in the Linux Kernel and allows for ecient dynamic information ow tracking at the level of system objects (processes, lesystem inodes, etc.).

Figure 5.1: Network information ow tracking

Sensitive data is labelled at the lesystem level, and the level of granularity of our approach is at the le level (i.e., les are considered as atomic pieces of information). Our implementation, presented in Chapter 4, takes advantage of the Linux Security Modules (LSM) framework available in the Linux kernel, and taint propagation is triggered by access control hooks. Our design goals are to provide a model that is easy to use, does not lock all the system by default by labelling only the sensitive information, and does not miss any information ow (no false negatives).

Network extension

We have extended our previous model so as to supervise network interactions. Network sockets are information channels, and we track information owing towards them. There are dierent families of sockets, including UNIX domain sockets and internet sockets. The latter are used to communicate with untrusted remote hosts through the internet, and we focus on their usage by userspace applications. Sockets by themselves are not labelled, as we consider those as part of the process memory. Instead, tracking is performed when processes actually send information through those information channels.

Network policy tag

The policy for communicating with internet sockets is dened globally through a unique shared network policy tag. The network policy tag is a set of sets dening which combinations of information may legally leave the local system through internet sockets, and optionally which applications may communicate, as well as which information each application may communicate (per-application proles).

A network policy tag is dened as follows:

P net P ℘p℘pI Y X qq
It is a set of sets that can contain any combination of elements from I (passive data) and X (running code).

The following semantics is associated with P net :

• Elements of I in the sets of P net represent mutually exclusive sets of data which can legally ow out of the system (i.e., only one of the sets is legal at one time).

• Elements of X in the sets of P net represent supervised 1 code which is allowed to communicate through internet sockets.

• Any combination A P ℘pI Y X q in the sets of P net denes a prole for applications, where elements of I dene which data can be sent over the network, and elements of X dene which running code may send that information.

Legality of network information ows

When a process sends information through a socket, a legality verication is performed on its current information tag against the global network policy tag. The information ow is legal if and only if the content of its information tag is contained in one of the subsets of the network policy tag.

Denition 15. For any information tag containing a set of data S P ℘pI YX q, the boolean relation Legal net is dened as follows:

Legal net pSq ô Dp P P net |S Ď p

Practical use cases

Our approach covers the following use cases. In the following, the term labelling refers to the action of attaching a unique information tag to a le.

All sensitive data must stay local

In this use case, the user of the system wants all of the sensitive data to stay local. Any network transfer of those data is a violation of the policy and our reference monitor, in its extended version, will report a privacy violation alert. This can be accomplished by only labelling sensitive data (les) that should never ow out of the system. By dening an empty network policy tag, no data can legally ow out through network sockets, and the user will be notied every time a socket sends such tainted data over the network.

P net " ttuu " K 1 The corresponding binary le is labelled with an information tag.

Sensitive data may be sent over the network only through trusted applications

In this use case, the system contains both trusted and untrusted applications, as well as some sensitive data which may ow over the network only through trusted applications. This can be accomplished by labelling all the binary applications on the system along with all the sensitive data. The network policy tag is set to match the union of all the information tags of the binaries and those of sensitive les on the lesystem. In this case, the network policy tag is a set with only one set.

P net " pS Y Cq

Here S is the set of all the sensitive data and C the set of all trusted code.

Per-application proles

In this use case, the system contains both trusted and untrusted applications, and each trusted application may send a dierent set of sensitive data over the network. This can be accomplished by labelling all the binary applications on the system along with all the sensitive data. Then, the network policy tag is a set of several sets, where each set represents one application prole, such as:

P net " t N ď i"1 ps i Y c i q|s i Ď S, c i Ď C, Legal net pc i Y s i qu
where Legal net paYbq states that the application a is allowed to send information b over the network, as presented in Denition 15.

Dynamic policy changes

Taint marking can sometimes lead to a growing number of false positives due to the fact that tainted data remains tainted until the system reboots, and information ows keep propagating tainted data between objects of the operating system. This may lead to repetitive alerts about the same data leaking. Furthermore, the user or administrator may decide to declassify some information that he or she previously considered as private, and allow it to ow over the network.

For this reason, users can decide to modify the policy on the y while the system is running.

New sets can be dynamically added to the network policy tag at runtime. Several situations may occur:

• Only sensitive data has been labelled, and may not ow over the network. There are no trusted applications. In this case, the user can permanently neutralize alerts concerning a set of sensitive data S by adding a new set S to the network policy tag.

• Both sensitive data and trusted application's code have been labelled, and the user wants to neutralize alerts concerning one set of sensitive data S leaked by processes running code C. This can be performed by adding a new set to the network policy tag containing pC Y Sq.

Conclusion

In this chapter, we presented a rst aspect of our network extension, focussed on tracking outgoing information. We dened a network policy, stating how information may leave the operating system through network sockets. The network policy can be set on its own, or on top of an information ow policy conning users, applications and persistent containers, as presented in Chapter 3. This extension led to a framework for detecting condentiality violations through applications leaking information towards the network, which we implemented and evaluated, see Chapter 8.

Chapter 6

Distributed Policy Over Multiple Hosts

This chapter presents our distributed model of intrusion detection. It relies on the host based model that we presented in the rst part of this thesis, along with new aspects to take into consideration with respect to the distribution of taint over the network, towards multiple hosts of a supervised network. In the previous part of this thesis, we have shown how using taint marking techniques along with an information ow policy allows us to detect intrusions at the host kernel level. In the previous Chapter, we have extended our host-level so as to track outgoing trac, and implemented a framework for condentiality violation detection. In this chapter, we introduce the distributed mechanisms and additions to our model that allow us for intrusion detection in groups of supervised hosts.

Context

In the reminder of this thesis, we propose a distributed model allowing for rich policy specication and ne-grained information ow tracking. We have extended our model in order to detect intrusions in distributed systems composed of multiple hosts gathered in groups. Hosts of the same group share a common information ow policy. It is distributed in each host at the container level.

In this chapter, we rst present the distribution of taint information across all the supervised hosts of a distributed system. After this, we dene a distributed information ow policy, allowing to specify the legal behavior of information ows amongst processes of multiple hosts with respect to the involved pieces of information and users on behalf of which processes are running.

Recall from Part II that objects of the operating system such as les, sockets, memory mappings etc. are considered as containers of information in our model, and that we attach labels to such containers: information tags, policy tags and execute policy tags. Labels are composed of metainformation represented by two sets I and X , representing respectively passive data and active code.

In the rst part of our work, labels were containing meta-information specic to the particular host running the IDS.

Host groups

Distributed systems are generally composed of multiple services running as processes across multiple hosts, involving variable amounts of information. Such information may involve public data, condential data, executable code etc., from multiple hosts. In order to dene an information ow policy for a distributed service, or for a whole distributed system involving multiple services, we gather hosts in groups and dene a distributed information ow policy per group. Let us consider a given network N . Let H be the set of all hosts on network N . Each host of a group is identied by a unique id h k P H.

The rst step towards dening a distributed policy amongst the hosts of a group is to identify the information to track on each host. Recall from Part II that information tags are sets of elements in I Y X , identifying passive data and active code residing in containers. For any given host h k , we dene I k as the set of all passive data managed by this host, and X k the image of I k through the Run function, i.e. the code originating from this host which may be executed by processes on any host. I k and X k are partitions of respectively I and X representing all the information of the group: We also dene a mapping allowing any host of the group to determine the origin of information:

I " ď h k PH I k ^X " ď h k PH X k
for any piece of tainted information we must be able to determine which host manages it, i.e. from which host does a specic tainted information come from.

Denition 16. The originating host of an element of pI Y X q, i.e. the host managing a given piece information, is determined by the following relation: 1 . When processes perform actions on objects (i.e. other containers), subsequent information ows occur (depending on the operation). The way taint data is carried in our distributed model follows the tainting rules presented in Part II, which apply to all the system objects, with the addition of two new rules, send and receive, targeting network trac (through sockets) from and towards other hosts of a group, as presented in Figure 6.2. In this gure, Taint means that the destination process or container gets tainted by the meta-information. Discard means the destination process or container does not get tainted by the meta-information. (For details about the legality of information ows, see Section 6.4).

Host : pI Y X q Ñ H
Hosts from the same group exchange information through network messages, which we consider as containers, as well as any other object of the operating system containing information. We therefore attach labels to messages, in order to carry information tags between multiple hosts, the same way as we do between containers of the same host. In order to carry taint information, we have considered two methods:

• Embedding information tags as security labels within network messages. This solution can be eective when a small amount of taint data is used. This aspect is further detailed in Chapter 7.

• Translating information tags into security tokens, which can then be resolved between hosts in a peer to peer fashion, using a distributed protocol. We present this method in the next subsection.

• Embedding so-called deltas relative to security tokens previously resolved, this is presented later in this chapter.

Distributed security tokens

Information tags can be composed of any amount of meta-information, and thus have dynamic sizes and require variable amounts of space. It may not always be possible to directly represent information tags within the labels of networking messages. Therefore, we have introduced a distributed security token protocol allowing hosts of a group to exchange security labels in a peer to peer fashion, as shown in Figure 6.3.

Denition 17. Security tokens are images of information tags through a cryptographic hash function H as follows, where Θ is the set of all possible tokens:

H : ℘pI Y X q Ñ Θ
We use such tokens, images of information tags, as security labels on network messages. Recall that information tags are dynamic: their content is updated after every information ow. Therefore, processes often need to update the labels they attach to network messages. Our distributed protocol involves so-called resolvers, one per host. Resolvers maintain caches of xkey : valuey pairs, storing mappings between information tags and security tokens. From the point of view of userspace processes, whenever a new token is needed, or an unknown token is received in a network message, a request is made to the local resolver.

After every information ow, if the information tag of the process has changed, a request is made to the local resolver to create a new token for this process, corresponding to its new information tag. We call this step token creation in the protocol dened below. Whenever a process receives an unknown token (i.e. a token which hasn't been seen before), it needs to query the local resolver, which in turn will query the originating host in order to receive a mapping, in the form of a xkey : valuey pair, associating the requested token with an information tag. We call this step token resolution. Such a mapping allows to translate the new token into an information tag, and to taint the process which received the network message accordingly. Local resolvers run on each machine, represented as R 1 and R 2 in Figure 6.3, and are the only processes communicating with no security labels, i.e. the code of resolvers is trusted and we do not track information ows 1 processes are the only active objects of the system: the execution of any pieces of code is necessarily performed through a process. 1. A message containing a security token is sent by a userpace process p 1 on host h 1 to another process p 2 on host h 2 .

2. Process p 2 asks the local resolver R 2 to look up in its local cache in order to resolve this token.

3. If it cannot nd it, R 2 asks R 1 for resolution using the protocol dened in the next section.

4. R 1 replies to R 2 with a mapping. R 2 is now able to resolve the new token for p 2 .

Protocol

Resolvers maintain a local cache of sent and received tokens for each remote host of the group, as shown in Figure 6.4. For any pair of hosts (h 1 , h 2 q, we name the caches as follows:

• sent h1 rh 2 s is the cache of tokens sent to host h 2 , on host h 1 .

• recv h1 rh 2 s is the cache of tokens received from host h 2 , on host h 1 .

The sizes of sent and received caches are equal and noted . Caches contain xkey : valuey pairs in (Θ ˆ℘pI Y X qq. Token resolution and token creation (described below) ensure that for each pair of hosts (h 1 , h 2 ), sent h2 rh 1 s is synchronized with recv h1 rh 2 s. Token resolution is performed over an alternate secure channel, using unlabeled messages (i.e. no security labels). Possible operations on both caches are:

• Creating a new entry pCq.

• Overwriting an existing entry pOq.

• Reading an existing entry pRq.

a. Token resolution: when a process receives a network message labeled with a security token, it needs to resolve it in order to be able to append the appropriate taint data to its information tag. Token resolution is dened by the following relation:

resolve : Θ Ñ ℘pI Y X q
Token resolution can be done directly by the local resolver if the token is in the local cache of received tokens. Otherwise, it is necessary to query the remote host using the protocol dened below.

b. Token creation: when a process on host h local updates its information tag, the following actions are necessary before sending data to any destination host h dest .

1. Create a new token tk new " Hpitagq where itag is the current information tag of the process, and H is a cryptographic hash function (see Denition 17). c. Token exchange protocol: hosts of a group exchange tokens using a protocol based on the two following operations:

host 1 host 2 tk 1 : {I 1 } tk 2 : {I 2 } . . . tk N : {I N } Ë ÒØ Ê Ú ÌÓ host 2 tk 1 : {I 1 } tk 2 : {I 2 } . . . tk N : {I N } ÌÓ host 3 tk 1 : {I 1 } tk 2 : {I 2 } . . . tk N : {I N } ÖÓÑ host 2 tk 1 : {I 1 } tk 2 : {I 2 } . . . tk N : {I N } ÖÓÑ host 3 tk 1 : {I 1 } tk 2 : {I 2 } . . . tk N : {I N } Ë ÒØ ÌÓ host 1 tk 1 : {I 1 } tk 2 : {I 2 } . . . tk N : {I N } ÌÓ host 3 Ê Ú tk 1 : {I 1 } tk 2 : {I 2 } . . . tk N : {I N } ÖÓÑ host 1 tk 1 : {I 1 } tk 2 : {I 2 } . . . tk N : {I N } ÖÓÑ host 3 ℓ ℓ
• Function token_queryptoken, hostq: query host about token. The remote host replies with token_send and sets a ag to either O_NEW or O_REPLACE. When O_REPLACE is set, a previous cache entry with the same key already exists and must be replaced. Otherwise, it is a new entry.

• Function token_sendptoken, f lag, hostq: send the pair ptoken, Hptokenqq to host with f lag in {O_NEW, O_REPLACE}.

Frequent updates

The overhead of the protocol that we dened depends on how often information tags of communicating processes require updates. Considering that our model does not yet have support for declassication 3 the behavior of information tags is such that, for a given process, it can only grow in size, and never diminish, until the process gets killed (or respawned). New elements may be added to the information tags, but no elements may be removed.

Denition 18. Whenever a process p receives a network message m, while in state i, we compute the update information tag of p as follows:

itagppq i`1 " itagppq i Y itagpmq i
As opposed with labeling a connection between two hosts, we label each network message individually, based on the state of processes at the moment when each message is sent. One possible drawback of this approach is when small updates are performed frequently on a process's information tag (e.g. because it accesses new tainted les before sending each message). In this case, the performance overhead of the resolution protocol would increase considerably. In order to avoid such a problem, we compute deltas.

Figure 6.5: Computing deltas

Deltas contain the dierence between two information tags (i.e. their union minus their intersection), or the dierence between two states of the same information tag, e.g. the information tag of the process p 1 in state i and in state i 4 " i `4. We embed deltas directly within network messages, in the security labels, when possible. It is not always possible due to size restrictions, therefore, deltas are used when small changes happen in information tags, i.e., when the memory space required to represent the new elements to append does not exceed the maximum size of security labels.

Denition 19. We dene the ∆ relation as follows, returning the delta between two information tags (sets of elements of ℘pI Y X q): ∆pa, bq " tx|x P a ^x R bu Denition 20. Let us dene the maximum available space in a network message security label as λ lbl , and the size (space) of individual elements of information tags as λ tag . Labelling network messages with lambdas rather than with security tokens is preferred whenever the available space in network messages is sucient, i.e. whenever:

|∆pitagppq t , itagppq t`k q| ˆλtag ă λ lbl Example 15. Figure 6.5 shows an example of two communicating processes p 1 and p 2 . For each process, bullet points represent the dierent states of their information tags. Process p 1 has states s 1 to s 5 and p 2 has states σ 1 to σ 5 . We consider the initial states s 1 and σ 1 synchronized with respect to the token caches: sent h1 rh 2 s is synchronized with recv h2 rh 1 s and sent h2 rh 1 s is synchronized with recv h1 rh 2 s.

1. Process p 1 sends a message M 1 to p 2 , labelled with the token tk 1 .

2. Due to network latency, p 2 is in a new state σ 2 when it receives the message. However it can directly resolve the token tk 1 , as this one is present in the local cache of received tokens.

3. Process p 2 now sends a message M 2 to p 1 . As the state of p 2 has changed from σ 1 to σ 2 , it is required to compute δ 1 " ∆pitagpp 2 q σ1 , itagpp 2 q σ2 q. As this is a minor change, between two consecutive states of process p 2 , δ 1 can t in M 2 .

4. Process p 1 receives M 2 . Its information tag has changed two times since it sent M 1 , and it is now in state s 3 . The delta since state s 1 is d 1 . It uses δ 1 to update its information tag with the information in M 2 , and jumps to state s 4 .

5.

Process p 1 sends message M 3 to p 2 . In the local cache sent h1 rh2s, the last sent token is tk 1 , p 1 changed of state 4 times since then. It now computes δ 2 " ∆pitagpp 1 q s1 , itagpp 1 q s4 q and check whether it ts in the message label (see Denition 20). As it ts, M 3 is labeled with δ 2 .

6. Upon reception of M 3 , p 2 reads delta δ 2 and update its information tag.

Information ow policy

In Chapter 3, we have introduced the information ow policy of our model at the host level.

Processes run code (or programs) on behalf of users. Recall from Chapter 3 that their policy tags are determined dynamically by • P C P is the set of all the policy tags restricting passive containers (mostly les).

• P U is the policy restricting local users.

• P Π is the policy restricting executable code.

• P N et is the policy restricting network communication (as presented in Chapter 5).

Denition 22. The information ow policy P group of a group of hosts ph 1 , ¨¨¨, h N q, identied at each host's level is dened as P group " pP h1 , ¨¨¨, P h N q

The following properties can be expressed (any number of each), and veried by the reference monitor of each host.

Users

Users in our model refer to the users on behalf of processes (in the UNIX sense). The following properties may be expressed in the information ow policy so as to restrict the behavior of processes towards information (data or code) from other hosts of the same group with respect to local users on each machine. • Only the specied pieces of code from hosts h 1 , . . . , h k may be executed by user u on the local host (execution w.r.t. users ). Properties 6.1 and 6.2 may be used together in the policy. In this case, the resulting policy contains sets of elements of I and X , i.e. P u Ď ℘p Ť k 1 pI k Y X k qq.

Programs

Programs refer to the active code being run by processes. Once (optional) rules have been dened

for user accounts (users, on behalf of which processes are being executed), the information ow policy may also contain the following properties, specifying rules attached to pieces of active code being run by processes (individual or multiple elements of X forming any program π P Π).

@π P Π, P π Ď ℘p k ď 1 pX k qq (6.3) (6.
3) species the following property:

• Local processes running π as code on the local host may only execute the specied sets of information from hosts h 1 , . . . , h k of the group (execution w.r.t. running code ). @π P Π, P π Ď ℘p k ď 1 I k q (6.4) (6.4) species the following properties:

• Local processes running π as code may only access the specied pieces of information from hosts h 1 , . . . , h k within the group (secrecy w.r.t. programs).

• Local processes running π as code may only mix the specied pieces of information from hosts h 1 , . . . , h k together (integrity w.r.t. programs). Properties 6.3 and 6.4 may be used together in the policy, leading to P π Ď ℘p Ť k 1 I k Y X k q.

Persistent containers

Persistent containers are individually protected by the following properties.

@c P P C , P c Ď ℘p k ď 1 I k q (6.5) (6.5) species the following properties:

• Persistent container c may only contain the specied pieces of information from hosts h 1 , . . . , h k within the group (secrecy w.r.t. persistent containers).

• Persistent container c may only mix the specied pieces of information from hosts h 1 , . . . , h k together (integrity w.r.t. persistent containers).

@c P P C , P c Ď ℘p k ď 1 X k q (6.6) (6.6) species the following properties:

• Write (or append) access to the persistent container c is only authorized to processes running the specied code, from hosts h 1 , . . . , h k within the group (integrity of containers w.r.t.

running code). Properties 6.5 and 6.6 may be dened together, leading to P c Ď ℘p

Ť k 1 I k Y X k q.

Network packets

Incoming and outgoing trac is tracked at the network packet level. The following properties may be expressed in P N et so as to restrict incoming or outgoing trac.

P N et Ď p℘p k ď 1 I k q (6.7)
• In the case of incoming trac, only the specied sets of information from hosts h 1 , . . . , h k are allowed in.

• In the case of outgoing trac, only the specied sets of information from hosts h 1 , . . . , h k are allowed out.

P N et Ď ℘p k ď 1 X k q (6.8)
• In the case of incoming trac, only accept trac from remote processes running the specied sets of code (programs).

• In the case of outgoing trac, only accept outgoing trac from local processes running the specied sets of code (programs).

Both properties 6.7 and 6.8 may be used together, resulting in:

P N et Ď ℘p k ď 1 I k Y X k q (6.9)

Legality of information ows

Recall denition 18 and Figure 6.2 from this Chapter, dening tainting rules with respect to the dierent objects of the operating system. Such rules apply after each operation responsible for information ows, made by processes running code on behalf of users. The legality of such information ows depends on the updated information tags with respect to the local information ow policy on the local host, on each host of the group. Therefore, information ows between several hosts involve the local information ow policies of each host (subsets of P group ). An information ow towards any container c is legal if and only if its new information tag itagpcq, after the information ow occurred, is included in at least one of the sets of its policy tag ptagpcq. This applies to all kinds of containers (i.e. processes as well as passive containers and sockets), based on the properties dened above. In a group involving k hosts, itagpcq P ℘p Ť k 1 I k Y X k q and ptagpcq Ď ℘p

Ť k 1 I k Y X k q.
This is veried by the relation Legal, dened in Part II (Denition 3), which can be generalized as follows:

LegalpA, Bq ô Da P A|a Ď B

Policy tags

In our model, policy tags are the link between the information ow policy with its dierent aspects, or subsets, and the objects of the operating system we actually supervise at runtime. Each policy tag contains rules, that are part of either P P C , P U , P Π or P N et . In Chapter 3, we introduced the notion of policy tags of persistent containers and processes, and how these two relate to dierent subsets of the information ow policy. Recall from previous chapters that the policy tags of processes are dynamically set up at runtime, upon process creation, from P U and P Π . The policy of persistent containers is initially attached to their respective policy tags, and expressed from rules of P P C . Similarly, the network policy tag, directly equal to P N et , is attached to network sockets so as to track incoming and outgoing network packets. However, it is common to all sockets, regardless of which process created them. The reason for this is that processes each have their own policy tag already. P N et is intended to track incoming and outgoing trac based on the properties dened above.

Conclusion

In this chapter, we have shown how we extended our information ow model to distributed systems made of multiple hosts gathered in groups. Security labels are carried over the network, and we are now able to dene the legal interactions between processes of dierent hosts, given their underlying tuser, codeu context. The information ow policy is distributed in a peer to peer fashion, and hosts exchange security labels through a distributed token protocol. As our model may involve frequent updates of security labels in some situations, we propose a solution to diminish the stress on the token protocol by computing deltas, containing the relative dierence between the states of the information tags of communicating processes. The information ow policy is dened at each host level, in the information tags of processes, persistent containers and sockets, as shown in Figure 6.6.

It is veried by each host kernel, the only trusted code in our model. This extended model and its implementation represent our second contribution. Related work include Aeolus [START_REF] Cheng | Abstractions for usable information ow control in aeolus[END_REF], DStar [START_REF] Zeldovich | Securing distributed systems with information ow control[END_REF] and Pedigree [START_REF] Bin | Practical data-leak prevention for legacy applications in enterprise networks[END_REF]. Our approach diers from these in multiple manners:

• Aeolus is a framework for building secure applications. It tracks information ows at the thread level and allows users to restrict the use of their information, which is categorized in tags. Such a framework oers ner-grained information ow tracking than our approach (we work at the system object level, e.g., processes instead). However, this framework does not provide system-wide supervision, and it is not applicable to native applications. Its policy denition is user-centric and oers limited expressiveness.

• DStar [START_REF] Zeldovich | Securing distributed systems with information ow control[END_REF] is an extension of decentralized information ow control models such as Flume [START_REF] Krohn | Information ow control for standard os abstractions[END_REF] and Histar [START_REF] Zeldovich | Making information ow explicit in histar[END_REF], to distributed systems. It uses integrity and secrecy labels so as to categorize information and restrict processes. It ensures that only processes allowed to communicate may actually do so, and follows a no read-up, no write-down logic. As other decentralized information ow control models, DStar requires applications to be modied in order to benet from the declassication mechanisms that it oers. DStar uses exporter daemons along with cryptographic certicates to exchange security labels between hosts. Our approach uses similar mechanisms (though it lacks mechanisms to enforce the integrity of security labels in its current state) to exchange security labels amongst hosts. However, both our labels and our security policy dier from DStar. On the one hand, our labels contain unlimited taint information elements, each describing one individual piece of information. On the other hand, the denition of the policy in our model does not rely on security classes but instead attaches individual sets of rules to each piece of information, in a ne-grained manner. This allows us to track illegal execution of code as well as integrity or condentiality violations by users or applications.

• In Pedigree, taint information is attached to resources such as les. Taint information may of two kinds: secrecy and integrity. As DStar, the policy is based on a lattice. However, as opposed to DStar, the policy is centralized. The particularity of Pedigree is that it provides capabilities mechanisms attached to taint information, so as to provide declassication. Our approach does not oer declassication mechanisms, but it keeps information ow histories and allows to dene ne-grained policies (as described in the previous paragraph).

To the best of our knowledge, the model that we have introduced is the only anomaly detection model combining OS-level taint analysis along with a ne-grained policy denition so as to detect intrusions in distributed systems. In the next chapters, we present the implementation of this model as well as our experiments along with a discussion of the strong and weak points of our approach (in Section 8.4).

Chapter 7

Network and Distributed Implementation

This chapter presents our distributed implementation. It presents the additions we added in the previous implementation in order to take the network and distributed aspects of the model into account. This implementation is an extension of the implementation presented in Chapter 4. It adds support for security labels on network sockets, along with a network policy, checking that only processes allowed to do so may leak the specied information, as presented in Chapter 5.2. Furthermore, it takes new distributed aspects into consideration, by labelling individual network packets with security information (information tags), so as to carry taint information between hosts of a group.

Network policy

The Network policy tag, that we introduced in Chapter 5.2, is used to track outgoing trac through internet sockets, by specifying which processes (more exactly, which pieces of executed code) are allowed to communicate information out of the system. A single network policy tag is centrally dened for all the system. As the other policy tags, attached to other types of containers, it is specied as a set of sets:

P net P ℘p℘pI Y X qq
It is implemented as a linked list of legal sets of information, where each set is stored in a red black tree for fast oplogpnqq lookups. A userspace interface is exported through the securityfs 1 lesystem, in order to load the network policy tag in kernel memory at boot time. This interface is accessible through sys/kernel/security/blare/network (once the securityfs lesystem has been mounted, e.g. by adding the correct line to /etc/fstab). Userspace tools have been written to set and update the network policy at runtime, and are available for download at http://blare-ids.org. These tools add new sets of information, one at a time, to the network policy. Each set is represented in userspace as an array of integers, contiguous in memory. The kernel code receipts the data and converts it into blare_policy_tree elements. content, describing so-called categories (in our case, categories refer to the meta-information of information tags ). The Domain of interpretation (DOI) eld gives the ability to dene separate domains where categories may have dierent meanings, e.g. for some systems, a value of 5 in the tags may be equal to the MLS level top secret, where in some other domains, it could be interpreted as public. • Tag type 1 denes a bitmap of categories, (i.e. values representing information in the packets) from category 0 to category 239.

• Tag type 3 denes a set of enumerated categories (i.e. representing sparse values).

• Tag type 5 denes categories ranges, where each range includes multiple categories.

Execution contexts

Before going into further details about how we have implemented network information ow tracking, let us introduce the notion of execution contexts. Kernel code may run in dierent contexts.

When executing code on behalf of a userspace process (e.g., executing a system call), it runs in process context, where it has access to all the data structures of the current userspace process.

The code running in process context can sleep (and be rescheduled later). Most aspects of this implementation run in process context. Networking code, however, is often related to low level data structures, involving time critical operations, e.g., copying data from the network card buers into memory on reception of packets. When a piece of hardware uses an interrupt to notify the CPU about some event, the CPU immediately schedules the appropriate interrupt handler (based on the interrupt number). When executing an interrupt handler, the kernel is in interrupt context.

This context is not attached to any process (though the address space of the interrupted process is left as-is), and the code cannot sleep. Interrupt handlers may interrupt important code, including other interrupt handlers, or may disable all other interrupts for the time of their execution. For these reasons, interrupt context code has to run for the shortest possible time. Therefore, the processing of interrupts is split in two parts: top half and bottom half. The interrupt handler is the top half, and it only processes immediate and time critical operations. All the remaining processing is left for the bottom half, generally deferred in a softirq or in a tasklet. We will not go into further details about these inner mechanisms, please refer to Robert Love's Linux Kernel Development book [START_REF] Love | Linux Kernel Development[END_REF], or Understanding the Linux Kernel by Daniel Bovet and Marco Cesati [START_REF] Bovet | Understanding The Linux Kernel[END_REF] for a more comprehensive description.

Socket operations

In Chapter 4, we showed how network trac between local processes is tracked, involving UNIX sockets (AF_UNIX) or internet sockets (AF_INET). We will now present mechanisms to track information between processes of dierent hosts of the same group by using CIPSO labels.

Sending messages

We attach labels to outgoing network packets by using the LSM hook security_socket_sendmsg, hooking the function __sock_sendmsg() in net/socket.c. This hook calls back functions in our LSM module, and the code runs in the context of the userspace process which called the sendmsg system call. Whenever the destination host is dierent from the local host, information tags are converted into bitmaps at this stage, and embedded into the network packet using the Netlabel LSM API. Otherwise, the information tag of the socket itself is labelled, as presented in Chapter 4.

The relevant code is dened in security/blare/lsm_hooks.c. In order to avoid concurrent access to to the underlying sock structure, attached to the socket, we need to take extra precaution when attaching a security label to it. security_sock_rcv_skb and security_socket_recvmsg. The former is called on frames reception, just after those get attached to the related socket. The code calling this rst hook does not run in the context of the userspace process which received the message. In other words, we do not have access to the data structures related to the process receiving the message. This is due to the fact that receiving messages is done in interrupt context. The interrupt handler copies the packet (or frame) in an sk_buff structure and initializes some other data structures before notifying the kernel about the new received frame, and deferring further processing to a softirq. The hook security_sock_rcv_skb is triggered by the function sk_filter() in net/core/filter.c, ltering socket buers. The caller of this hook holds spinlocks and runs in a softirq, therefore the code from our module that is called back at this very instant cannot sleep (otherwise resulting in a catastrophic behavior, most likely ending up as a kernel panic). Note that there are no mechanisms avoiding the same softirq to run concurrently on several CPUs, therefore specic precautions have to be taken so as to avoid concurrency issues. Furthermore, when allocating kernel memory in such a context, one needs to make sure that the GFP_ATOMIC ag is used, so as to avoid the underlying call to get_free_pages() to sleep. In this part of the code, we perform the following operations:

1. Dump the security attributes attached to the headers of the packet. This is done by calling netlbl_skbuff_getattr() from the netlabel API.

2. Acquire a spinlock on the socket's tags. blare_tags structures (see Figure 7.4 below) are attached to sockets in their sk->sk_security eld. This ensures that no concurrent softirq running the same code accesses the same data structure at the same time. Note that we do not disable local bottom halves here, on the rst hand because softirqs never preempt each other (only interrupt handlers may preempt softirqs), and on the second hand because the only possible concurrent code in this situation is the same softirq running on another processor, which is solved by the spinlock.

3. Extract the bitmaps from network packets and make the conversion into the information tag of the socket. At this point, the information tag of the socket, stored in the info eld of the socket's tags, is up to date. We now have to update the information tag of the process which received the message, with the socket's information tag. This is done by a second hook, security_socket_recvmsg. This part of the code does:

1. Get a copy (RCU) of the current process's information tag.

2. Merge the socket's information tag into this copy of the process's information tag.

3. Commit (RCU) the new information tag (which replaces the current process's information tag with the new one).

No specic precautions are required here, as this code run in process context: we can access the relevant data structures directly (which we could not in the previous hook), and we can safely sleep (no precautions regarding memory allocation or specic function calls). Furthermore, though the two hooks may run concurrently (i.e. a new frame may arrive in the network card buer, deferring work in a softirq, triggering the rst hook, while the code called by the second hook runs on another CPU), this code is perfectly safe without any locking. This is due to the fact that information tags of sockets are, like those of processes, implemented as doubly linked lists. Such data structures are safe in the case of concurrent readers and writers, as long as there is no more than one writer at the same time.

Bug and patch

During the development of our kernel monitor, we stumbled across an issue due to a bug in the code of the kernel, outside our module in the Netlabel subsystem. Our testing environment was composed of several virtual hosts running our modied kernel, connected over a virtual bridged network. The host kernel was the default Debian kernel. In our test case, all the packets containing a CIPSO label were dropped by the host kernel. After a period of testing and discussion with the author 4 of the code, we could gure that this was due to a bug in the code of Netlabel and identify possible ways to reproduce it. A patch has been released by Paul Moore to x this bug 5 , and it was accepted in the Linux kernel in version 3.5-rc1. Before this patch, it was required that the host kernel be congured to use netlabel with the same domain of interpretation as the guests.

Not doing so was resulting in a host kernel failing to route network packets in the case of bridged networks.

Future work

In the future, several optimizations and new features should be considered, so as to increase performance and stability to a higher level.

Distributed security token

We have not implemented the distributed security token protocol presented in Chapter 6, this is left for future work. Therefore, the current implementation has a limitation on the number of distinct meta-information that can be carried on network packets. The protocol we dened can be implemented using netlink messaging [START_REF] Neira-Ayuso | Communicating between the kernel and user-space in linux using netlink sockets[END_REF], so as to communicate with a user space daemon on each host. Labels resolution would then be performed by the local userspace daemon towards the remote daemon in a peer to peer fashion every time a new and unseen token arrives in a network packet.

Copy on write

Information tags of processes, sockets, shared memory segments, and every other objects represented in memory, should be implemented using copy on write so as to reduce the memory overhead of our reference monitor. Objects of the system tainted by the same information tag should hold a pointer to the same data structure rather than a copy of it, until it needs to modify it to add new taint data. A cache could be used to maintain all existing information tags in the system, using reference counts to free up memory when some elements are no longer in use.

Filesystem bottleneck

Our experiments (presented in Chapter 8) show that a bottleneck exists at the lesystem level, slowing down our reference monitor. This is due to the frequency of updates on the extended attributes of les, which are performed in a very synchronized way every time a read or write access occurs. Recall from Chapter 4 that the extended attributes are represented as contiguous at portions of memory. Therefore, accessing such information requires conversions to our inmemory representation of information tags on read access, and the other way round on write access. Furthermore, on write access, it is also required to load the policy tags of the les into memory before checking the legality of their new content. A solution to cope with this shortcoming would be to maintain a cache of open le descriptors, containing for each le:

• The current policy tag.

• The current information tag.

Enforcement mode

Our primary goal is intrusion detection, therefore we do not block any information ow in the present model and implementation (we run in so-called permissive mode). However, the ability to enforce a policy may be considered in some situations including the deployment of an IPS (Intrusion Prevention System) based on our model, or setting up information ow control 6 in a trusted computing environment. As our implementation uses the LSM framework, providing access control mechanisms to security modules, the choice of enforcing the policy instead of raising an alert requires minor code modications. Also, in terms of data structures, blocking illegal information ows reduces the amount of space required by the tainting: when running in permissive mode, we need to taint all the information present in all information ows. When enforcing a policy, some information ows are blocked, thus reducing the amount of tainting. Some simplications can be done in the information tags in such a situation. Consider a container c, with a policy tag ptagpcq and an information tag itagpcq. Recall the Legal relation from denition 3 in Chapter 2. When enforcing the policy, the state of the information tag of the container is always legal with respect to its policy tag: Legalpitagpcq, ptacpcqq always stands. In such a case, the information tag of any container is always a subset of its policy tag.

One possible optimization of our implementation, when used in enforcement mode, would be the use of xed-sized bitmaps to represent information tags, rather than doubly linked lists. The latter are very ecient in the case of dynamic allocation, when no size boundary exists. However, in the present case, the size of information tags is bound by the policy: each subset of the policy denes one possible legal state of the information tag of the container. For any policy tag P " ttp 1 u, tp 2 u, . . . , tp N uu, the corresponding legal information tag is bound by:

I " N ď 1 p i
We could represent such information tags in a xed-size bitmap for every supervised container of the operating system, thus reducing the memory overhead of our implementation when enforcing the policy.

Conclusion

In this chapter, we have presented the distributed aspects of our implementation, relying on the Netlabel subsystem to attach CIPSO labels to network packets leaving each host of a group.

The distributed token protocol (and the computation of deltas ) has not been implemented at the moment. Instead, we use xed-size bitmaps in the labels that we attach to network packets. In its current state, this implementation allowed us to perform the experiment presented in this thesis, and available for download from our website 7 , released under the GPLv2 license. At the time of this writing, researchers outside our team have contacted us and started using it for other purposes, as a framework for information tainting, claiming that this is the only freely available implementation of such a tainting framework today. In an eort to distribute and cooperate on this project even more, our research team 8 is currently pursuing this project with several Ph.D. students and a research engineer.

Chapter 8

Experiments

To conclude on the third part of this thesis, introducing network and distributed aspects to the intrusion detection model presented earlier in previous chapters, we will now detail our experiments based on the implementation explained in Chapter 7. We rst present a case of intrusion on the client side, by visiting a malicious service using a web browser and a awed plugin. The malicious service targets sensitive data on the client by using a remote exploit on the Java Virtual Machine. This rst experiment shows how we are able to detect condentiality violations and data leaks with our IDS along with a network policy, as introduced in Chapter 5.2. After this, we present a second experiment, involving a distributed web service composed of supervised hosts sharing a distributed information ow policy. We show how the reference monitor of each host is able to individually identify illegal information ows spawned by a successful attack. We nally present an assessment of the performances at the host level and discuss about the usability, advantages and shortcomings of our approach.

Data leaks through a web browser

This rst experiment makes use of the network policy, that we introduced in Chapter 5.2. The following scenario, as illustrated on Figure 8.1 shows how our new model and implementation can detect condentiality violations by untrusted code interpreted by a Web browser. Web browsers were initially simple applications displaying HTML content to the nal user, but those have evolved into complex applications running JavaScript and other interpreted languages on the client machine, inevitably exposing user data to a number of real threats. In this scenario, a client is running a modied Linux kernel with our reference monitor, including the network extension that we presented in Chapter 5.2. The client visits a malicious web page using Mozilla Firefox 3.5 and the Java runtime environment plugin (JRE) version 6 update 10. This version is subject to the Java calendar deserialization vulnerability (CVE 2008-5353) that may lead to the execution of arbitrary code by an attacker. The client executes malicious Java code exploiting this issue and embedding a payload that allows the attacker to get a remote shell on the machine. Assume the folder/home/alice/confidential/ contains 64 condential les. We labeled these les as being condential, and assigned an information tag containing a unique identier between 1 and 64 to each of them. The information tag of these les is a set containing one unique identier, e.g., {1}. This experiment is similar to the use case all sensitive data must stay local introduced in Chapter 5.3.1. We dened an empty network policy tag as follows :

P net " ttuu " K In this conguration, any application sending any of the labelled les to any remote host is a security policy violation and triggers an alert. Now we visited a crafted web page http://www.malicious-host/malicious-page.html embedding a malicious Java applet containing an attack against the previously mentioned vulnerability. This malicious page causes Mozilla Firefox to execute the Java virtual machine (JVM) in a separated process, which in turn interprets the Java code containing a remote shell allowing the attacker to connect to the local machine. As the attacker accesses labelled les of the local lesystem, the information tag of the process running Java is updated with information tags of the les it reads. At the moment when it sends information through a socket, our kernel reference monitor considers that the data being sent contains information from the les it previously read, and proceeds to a lookup throughout the network policy tag to ensure this behavior is allowed by the user. For every illegal attempt to illegally send information by the Java process, we were warned by the reference monitor with the following message:

[BLARE_POLICY_VIOLATION] Illegal information sent to socket by process [PID] running java 3 . This vulnerability allows for arbitrary le upload and remote code execution.

Scenario

As shown on Figure 8.3, we labeled all the les of www 1 and www 2 as well as the PHP5 dynamic library (used by apache to interpret PHP code) with distinct information tags on the web server.

On the database server, we labeled the PostgreSQL binary as well as two tables on each database.

We could label information at the table level by using the option default_with_oids = on in PostgreSQL's conguration le. Object identiers (OIDs) are used in PostgreSQL as primary keys for system tables, as well as user-created tables when using this option. Each table in PostgreSQL is mapped to a le named after its OID. Thus, we could label the les related to the supervised tables. When a process executes a binary le (or the content of a dynamic library) labeled with i k , its information tag is set to x k " Runpi k q. Therefore, both Apache and PostgreSQL processes always have their information tags initialized to respectively

Host

x a " Runpi a q and x pg " Runpi pg q. We used the following policy tag for both Apache and Post-greSQL processes: P " ttx a , x pg , x php , i 1 , i u1 , i p1 utx a , x pg , x php , i 2 , i u2 , i p2 uu. Such a policy makes it illegal for any process running Apache or PostgreSQL to hold information from both websites simultaneously, or to run any code other than Apache and PosgreSQL binaries and libphp5. When an external visitor visits www 1 , the web server creates a new process for this connection and reads les labeled with i 1 . It also maps libphp5.so in executable memory pages which taints the process with x php . It queries the database server. The database server forks a new process and reads information from db 1 . At this stage, the information tag of the PostgreSQL process is tainted with S 1 " tx a , x pg , x php , i 1 , i u1 , i p1 u. After the PostgreSQL process has responded to the Apache process, both processes have equal information tags 4 , as each process labels network packets with a CIPSO option containing its information tag (in a bitmap, as described in Chapter 7). When an internal host connects to the internal virtual host www 2 , similar interactions happen between the hosts, and the information tags of both processes handling the connection are tainted with S 2 " tx a , x pg , x php , i 2 , i u2 , i p2 u. In both cases, information ows are legal, and so no alert is raised, because information tags are subsets of the policy tags in both containers: S 1 Ď P ^S2 Ď P .

Attack

The following attack leaks information from the private web site www 2 located on the intranet. The attacker runs the upload exploit on the Foxypress plugin on www 1 and injects a malicious PHP le on the web server. We used Metasploit 5 to run the attack. After injecting the le, the running web server process's information tag was equal to S 1 " tx a , x pg , x php , i 1 , i u1 , i p1 u, and so was the information tag of the malicious PHP le. From there, any illegal action triggered an alert:

• Executing the malicious PHP le, which taints6 the process's information tag with RunpS 1 q " tx 1 , x u1 , x p1 u is illegal, as RunpS 1 q Ł P

• Querying the database server to access data from www 2 , which taints the process's information tag with S 3 " tx a , x pg , x php , i 1 , i u1 , i p1 , i u2 , i p2 u is illegal as well, as S 3 Ł P .

Information tags are carried over the network through CIPSO labels, therefore both the web server and the database server raise an alert in the case of illegal information ow, as both servers are aected by the attack: data from the database server leaks, and the web server runs arbitrary code.

Evaluation of performances

The following is an evaluation of our implementation in terms of performances. In order to assess the performance overhead of our LSM module, we uncompressed a Linux kernel source tree and used it as a dataset containing 39048 les, that we individually labeled with a unique information tag.

The machine we used is a Pentium 4 3.0 Ghz with 2.5 GB of RAM. We evaluated the performances of our kernel by transferring all the les of our dataset through a SSH tunnel, following the scenario all sensitive data must stay local as presented in Chapter 5.2.

Figure 8.4 compares the CPU idle time when using Linus Torvald's kernel (that we call Vanilla) and the Blare kernel. As expected, the Vanilla kernel gives lower CPU overhead during the transfer (higher CPU idle value). Our security framework adds 30% to 40% of extra overhead to the data transfer.

Figure 8.5 compares the memory overhead of our kernel and makes a comparison with a Vanilla kernel executing the same le transfer operation. As KBlare is attaching meta-information to every system object, the memory consumption remains higher by 30% on average when using our Kernel.

Overall completion time

The overall completion time was 300% longer with our kernel than with the Vanilla kernel. This limitation is due to a bottleneck at the lesystem level in our prototype (as described in Chapter 7).

The extended attributes of the lesystem are used extensively in our implementation with no optimization. We believe that the overall performances of our system can be improved dramatically by optimizing the current prototype as follows: rather than updating tags at each lesystem operation (i.e. fread and fwrite), we could instead maintain a cache for open le descriptors, and synchronize it with the actual lesystem whenever a call to fclose is performed. An ecient cache may be implemented with a binary tree indexed on the inode numbers of each le. When evaluating an intrusion detection system, a common measure is the rate of false negatives and false positives. By design, our conservative approach does not allow false negatives 7 . Our model of information ow tainting makes an overestimate of all possible content residing in containers, and maintains it updated after every information ow, both at the operating system level and on the network. Network trac, or other forms of datasets, are a common basis for evaluating misuse IDSes, or anomaly IDSes based on statistical models. As our approach does not rely on network trac analysis, nor on learned proles, no such dataset can be used to evaluate our model. In our case, the dataset is determined by the pool of attacks we run. These attacks are included in the Metasploit framework as well as in the Common Vulnerabilities and exposures (CVE) database 8 .

In our experiments, we have been able to successfully detect intrusions with no false positives as long as the system was following a legal behavior. Each time an event involving an illegal information ow occurred, all the subsequent information ows performed by the same process (or set of processes involved in the attack) in read access were considered illegal, as well as all the information ows towards supervised objects in write access (i.e. objects protected by a policy tag restraining their legal content).

Our model does not rely on a xed information ow policy. The policy is manually adjusted to t the dierent requirements of each supervised system. Therefore, the rate of false positives is highly variable. It depends on the following parameters:

1. The accuracy and consistency of the dened information ow policy.

2. The lifetime of tainted processes (these tend to accumulate more tags with time, leading to more false positives ).

3. The use of IPC (Inter Process Communication).

4. The number of processes or services accessing the same set of les (including temporary les) or common objects.

It is impractical to perform a comprehensive study of the false positive rate in our current work.

However, we can identify the following behavior from our experiments. Situation with low false positive rates Server-side services and applications often involve multiple processes, where each process handles one client connection, like in the experiment on a distributed web service previously presented in Section 8.2. Running the attack on the web server spawns illegal information aws that we are able to detect. As both Apache and PostgreSQL fork one process per connection, the number of alerts reported by our reference monitor after an illegal information ow occurs is limited by the lifetime of such processes. Once a connection ends, the related process is killed. When a new connection occurs, a new process is forked from a clean process: the so-called worker process, from which new processes are forked, does not get tainted by information ows of its child processes, and every new connection leads to an untainted process. Furthermore, such server-side applications handle isolated sets of les (e.g. Apache works with les in /var/www where PostgreSQL stores its database tables in les located in /var/lib/postgresql), which eases the task of dening suitable information ow policies.

Situations with high false positive rates

On the contrary, desktop applications often involve buses such as DBUS, graphical environments, and other long term processes, staying active until the current user closes his or her session. Dening a suitable information ow policy in such a situation is more complex. Furthermore, by computing an overestimate of possible information ows, our reference monitor lacks accuracy in this context.

Recall the experiment from Section 8.1. In this scenario, alerts are reported when sensitive data may have left the system through a network connection. When conducting this experiment, no false positives occurred until the web browser accessed sensitive information. From this point on, all subsequent information ows were considered illegal. This approach is valid for tracking access to sensitive information which should by no mean leave the system, and where access is performed by unwanted and/or malicious events.

In other situations, where a ner analysis inside applications' code is required, our approach involves a high number of false positives, and lacks accuracy.

Improving accuracy

In this Ph.D., we focused on OS-level mechanisms. Our model and implementation provide a basis for system-wide intrusion detection based on taint marking. The level of granularity of our approach in terms of tracking is limited, in our current implementation, by the abstraction of UNIX systems. Figure 8.6 illustrates our approach. It represents a process with inputs i 1 , i 2 , i 3 and outputs o 1 , o 2 , o 3 . From our level of abstraction, we cannot determine how information ows within processes (or applications). Therefore, we compute an overestimate of the possible ows: the outputs of the process are considered as function of all the previous inputs, at any time. This overestimate generates variable amounts of false positives depending on the context, as presented in the previous section.

Taking this current work as a basis, a solution to dramatically reduce the amount of false positives is to increase the accuracy of our data ow analysis. By combining application-level information ow tracking techniques with our OS-level reference monitor, it becomes feasible to nely observe information ows within processes, and to supervise multiple applications as well as their interactions through the operating system in a ne-grained manner. This aspect is out of the scope of this Ph.D., and is part of current research in the CIDre team. This model does not replace access control mechanisms, nor enforce any security policy but instead helps to ensure that no unwanted behaviour happens with respect to dened sets of information managed by users and applications of multiple hosts. The situation where a web-browser accesses some personal information is a good example of our goals: where access control mechanisms could have been used to block this particular access in the rst place, it would not prevent applications from indirectly accessing the same information by another channel (shared memory, IPC with another application etc.). Furthermore, in this example, we focus on the fact that this information should not leave the system through the network, therefore no alert would be raised when an application accesses such information but does not send it over.

The main limitation of our OS-level approach is its accuracy, as it computes an over-estimate of the actual content involved in information ows. This has a direct impact on the false positives rate. Work in progress in the CIDre team seeks to address this shortcoming by several means:

1. By ltering alerts in userspace. For instance any sequence of false positives triggered by the same event can safely be discarded after the event has been reported.

2. By using our framework in cooperation with language or architecture-level monitors.

3. By instrumenting native applications.

Conclusion

In this chapter, we presented our experiments, as well as an analysis of the performances and accuracy of our intrusion detection model. We have shown that it is suitable for detecting intrusions in both isolated and distributed systems. The maximum performance penalty that we have measured was close to 30% in terms of memory overhead, and 30-40% in terms of CPU overhead. Due to a bottleneck at the lesystem level in our current implementation, the overall completion time of our experiments was 300% longer when using our IDS. We believe that this could be dramatically improved by the mean of optimizations (e.g., using caches). We have identied situations where our model is suitable for realistic intrusion detection, as well as situations highlighting its shortcomings in terms of accuracy, leading to high rates of false positives. Solutions exist so as to address the identied shortcomings, and are considered in current research in the CIDre project team.

Conclusion

In response to the complexity of securing ever evolving information systems, often relying on distributed services across multiple hosts, we have designed and implemented an information ow model using taint marking techniques, in order to detect intrusions at the OS kernel level. Our approach of anomaly detection is based on the specication of an information ow policy. By tracking information ows between objects such as les, sockets, pipes, memory mappings etc., as well as in network packets owing between hosts, we are able to successfully detect intrusions, both in isolated hosts and in distributed services composed of multiple hosts (gathered in groups ).

We have presented our model of information ow tracking, specifying a ne-grained policy at four dierent levels: containers of information, users, applications and network. Our reference monitor was implemented in the Linux kernel, as a Linux Security Module. This model and its implementation represent our rst contribution. The validation of the implementation was experimental. For each experiment, the involved aspects in the theoretical model were identied, and the results were compared to the expected behavior of the system with respect to the theory. Our new intrusion detection principles have been validated through our experiments. In Chapter 8, we have practically set up and presented two realistic applications of this approach. A rst application followed a scenario involving an attack against condentiality, by exploiting a security aw in a plugin, inside a web browser. We demonstrated that our model was able to successfully detect the illegal information aws spawned by the attack. A second application focused on distributed services across several hosts. Our reference monitor was successful at detecting attacks against a frontal web server. Illegal information aws spawned by the attacked web server, communicating with remote processes, were also detected at the level of each host composing the distributed service, and alerts were reported by each reference monitor. The extension of our model and implementation to distributed systems represents the second contribution of this work.

The performance overhead of our reference monitor reaches 30% in memory consumption, and 30-40% in CPU, in extreme situations involving a high number of distinct taint information. Its main limitation is an overhead on the completion time of some operations in some cases, reaching up to 300% in extreme situations. Our current prototype may be further optimized so as to decrease the involved performance penalty, and we proposed possible tracks for improvement in Chapter 7.

Our model and its implementation are suitable for the following applications:

• Supervision of users and programs: our model can be used to track applications by attaching a policy (i.e., a set of policy rules) to their related code (binary programs, scripts, shared libraries etc.). A policy may also be attached to local users. When a process executes some code, such a policy is used along with the policy of the current user (if dened) to determine the legal information ows caused by the resulting processes. Any violation of the policy triggers an alert. This may be used to protect users' privacy, as well as the integrity of information.

• Supervision of network communications: a network policy can be used to dene the legal interactions between processes (i.e., applications executed by users) of dierent hosts involving sets of supervised information.

• Tracking the changes made by viruses: by keeping the origins of all data present in each container, we can retrieve all the information ows that were caused by a virus (or any given piece of executable information). This may be used e.g. to and track the modications that were made in order to perform a rollback of the system to a safe state.

• Detect the presence of an attacker by detecting abnormal behavior of programs, services or daemons.

• Detect the execution of modied applications and rootkits: as we do not trust code that has been illegally modied, we can detect malware and rootkits. When the code of an application or library is altered by a process, we keep tracks of such changes in the information tag of the modied application le(s). These meta-data give information about the running code as well as information hold by the process which altered the le. Whenever such changes are illegal, the execution of the new code is illegal too.

The framework that we presented provides a basis for system-wide intrusion detection in distributed systems and services. The overall accuracy of our model depends on the level of granularity oered by the underlying OS abstractions. Even though we were able to successfully detect intrusions with this model, it presents shortcomings in situations where accuracy is required, as shown in Chapter 8. It is impractical, at the OS level, to nely observe information ows within applications. Therefore, in its current state, our framework is usable in simple situations, but it generates high rates of false positives in environments where processes communicate with IPC mechanisms.

In order to address these shortcomings, current work in the CIDre team focuses on the cooperation of our OS-level reference monitor with application-level reference monitors.

Our model may also be further distributed in future work. We proposed a distributed protocol allowing hosts of a group to exchange security tokens in a peer to peer fashion. While the resolvers on each host manage information tainting in a fully distributed manner, the specication of the policy in our current work is done manually on each host of the groups, by a central system administrator. The specication of the policy could instead be determined independently on each host in a decentralized way. Such a policy could rely on a peer-to-peer protocol, allowing each pair of hosts to agree on a common set of rules, regarding legal interactions of their processes with respect to the data they manage.

Figure 1 Figure 1 . 1 :

 111 Figure 1.1: Access control matrix

Figure 1 . 2 :

 12 Figure 1.2: Example: Access control rights

Figure 1 . 3 :

 13 Figure 1.3: Example of illegal indirect ow.

1. 4 . INTRUSION DETECTION 1 . 4 . 1

 4141 Host-based and network-based IDS

Figure 2 . 1 :

 21 Figure 2.1: Comparison of information ow models.

Figure 2 .

 2 Figure 2.1 is a comparison of information ow models: B&LP stands for Bell-LaPadula, CW stands for Chinese walls, C&W stands for Clark-Wilson, M&L stands for Myers-Liskov. The declassication aspect of the VTT model is a work in progress in the CIDre team. The term decentralized refers to the way the policy is dened. If it is centrally dened by one single authority

Operation

  Figure 3.1: Tainting rules

Figure 3

 3 Figure 3.2: User policy

Figure 3 . 3 :

 33 Figure 3.3: Execution of a binary program

Figure 3 . 5 :

 35 Figure 3.5: AppArmor access modes

Figure 3 . 6 :

 36 Figure 3.6: Derivation algorithm.

Figure 3 . 7 :

 37 Figure 3.7: Example prole for derivation

Figure 4 . 1 .Figure 4 . 1 :

 4141 Figure 4.1. In other words, MAC is more restrictive than DAC, but it does not replace it.

Figure 4 . 2 :

 42 Figure 4.2: Atomic information in les at initialization time

Figure 4 .

 4 Figure 4.2 is an example of how atomic meta-information can be attached to les at initialization time. Files content is described by a unique meta-information as long as their content is not altered.

Figure 4 . 3 :

 43 Figure 4.3: Number of les on a Linux server.

  a tag (ordered set) in KB Lenght of a tag (ordered set) (l) Arrays Bitmaps Linked lists

Figure 4 . 4 :

 44 Figure 4.4: Data structures memory overhead

Figure 4 .Figure 4 . 5 :

 445 Figure 4.5: Memory allocation layers in the kernel

Figure 4 . 6 :

 46 Figure 4.6: Output of the slabtop command.

Figure 4 . 7 :

 47 Figure 4.7: Information tags are represented as doubly linked lists

Figure 4 . 8 shows

 48 an example of policy tag, composed of three sets, with roots r 1 , r 2 , . . . , r N linked together in a doubly linked list. The following data structures are used to represent policy tags (dened in security/blare/blare.h):

Figure 4 . 8 :

 48 Figure 4.8: Policy tags are linked lists of binary trees

  ( i := 1 t o n ) do f o r ( j := 1 t o m) do c := a i X b j f o r ( k := 1 t o s i z e ) do i f ( c Ď new [ k ] ) t h e

Figure 4 . 9 :

 49 Figure 4.9: Execute policy tags intersection algorithm

  Both clone and fork are hooked in the LSM framework (security_task_create) and trigger two functions in KBlare. The rst one is dened as follows: static int blare_task_create(unsigned long clone_flags); It is not yet used in our implementation, but it gives useful information about the clone ags, which may be used in the future to track individual threads of the same process 12 . The second one is dened as follows: static int blare_prepare_creds(struct cred *new, const struct cred *old, gfp_t gfp); This function is part of the RCU 13 mechanisms protecting access to the credentials of processes, and returns an exact copy of the protected structures (blare_tags in this case).

  static int blare_netlink_send (struct sock *sk, struct sk_buff *skb); static int blare_netlink_recv (struct sk_buff *skb, int cap); Part III Distributed Intrusion Detection Chapter 5

Figure 6 . 1 :

 61 Figure 6.1: Host group

Figure 6 . 2 :

 62 Figure 6.2: Tainting rules

Figure 6 . 3 :

 63 Figure 6.3: P2P token exchange

Figure 6 .

 6 Figure 6.3 summarizes the steps involved in the protocol:

Figure 6 . 4 :

 64 Figure 6.4: Distributed token protocol

3 .

 3 In case of collision, overwrite (O) existing values and set f lag to O_REPLACE.

4 .

 4 Otherwise, create (C) tk new in sent h local rh dest s and set ag to O_NEW.

5 .

 5 Send token to remote host (using the protocol dened below and the appropriate ag).

1 )

 1 species the following properties:

PFigure 6 . 6 :

 66 Figure 6.6: Deriving policy tags from the policy

Figure 8 . 1 :

 81 Figure 8.1: Monitoring outgoing information

Figure 8 . 4 :

 84 Figure 8.4: CPU overhead on SSH transfer

Figure 8 . 5 :

 85 Figure 8.5: Memory overhead on SSH transfer

Figure 8 . 6 :

 86 Figure 8.6: Information ows within applications

  Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Network extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Network policy tag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Practical use cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.1 All sensitive data must stay local . . . . . . . . . . . . . . . . . . . . . . . . Per-application proles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Dynamic policy changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Filesystem bottleneck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.8.4 Enforcement mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 8.4.1 Detection rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 8.4.2 Improving accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 8.4.3 Usability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 8.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Information ows within applications . . . . . . . . . . . . . . . . . . . . . . . . . .

	Introduction I Research Context 1 Background and Related Work 5 Network Extension 5.1 5.2.2 Legality of network information ows 5.3 5.3.2 Sensitive data may be sent over the network only through trusted applications . . . . . . . . . . . . . . . . . . . . . 5.3.3 6 Distributed Policy Over Multiple Hosts 113 Conclusion 114 Bibliography 116 Appendix A System Calls 123 1.1.2 III Distributed Intrusion Detection 8.6
	7.8.2	Copy on write	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	7.8.3
	8 Experiments

1.1 Traditional security mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Firewalls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Host groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Network tainting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.1 Distributed security tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.2 Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.3 Frequent updates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Information ow policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.1 Users . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.2 Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.3 Persistent containers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.4 Network packets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Legality of information ows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5.1 Policy tags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Network and Distributed Implementation 7.1 Network policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Distributed policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 CIPSO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Netlabel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4.1 Internal representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4.2 Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5 Execution contexts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.6 Socket operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.6.1 Sending messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.6.2 Receiving messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.7 Bug and patch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.8 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.8.1 Distributed security token . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1 Data leaks through a web browser . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Attack on a distributed web service . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.1 Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.2 Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Evaluation of performances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.1 Overall completion time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CONTENTS 8.4

  list) which can be represented as a row in Lampson's matrix. However, Miller et al.[START_REF] Miller | Capability myths demolished[END_REF] claim that capabilities based models have dynamic aspects that cannot be represented in Lampson's matrix, as it is only a static representation of access rights. Miller et al. show that capabilities systems are actually more sophisticated than access rights, and that a direct comparison using Lampson's matrix is not accurate. It should be emphasized that "Portable Operating System

1 Such a reference does not give any information about who holds it and which access rights are associated with it.

1.1. TRADITIONAL SECURITY MECHANISMS (also called C-

  emerged from research led by the National Security Agency of the USA. It is the rst security module available in Linux, and it has been designed to implement a exible MAC mechanism called domain and type enforcement (DTE). Domain and Type Enforcement (DTE) has been presented [DTE95,DTE96] as a model that improves access control. DTE groups processes into domains and les into types. It restricts access from domains to types as well as from domains to other domains. The kinds of access modes that are considered by SELinux can be any of read,

write, execute, create, and directory descend. Domain access refers to the right to send signals as well as to transition to a new domain. At any given time, a process belongs to exactly one domain.

Transition to a new domain is done by executing a le which has been dened in the policy as an entry point to the new domain. There are three types of domain transitions: auto, exec, or none. For instance, if a domain D A has auto access to another domain D B , and a process in D A executes an entry point for D B , it will automatically switch to D B . The exec property is similar, except that the process can choose whether to switch to a new domain or not, by executing one of its entry points.

  is an IDS deployed at the host level, and at the

	Java Virtual Machine level. It relies on information ow models developped in the ISSN 4 team
	at Supélec. Its rst model is host-based and was developed by Jacob Zimmermann [81, 82]. It
	relies on the principle of non-interference. This principle was introduced in 1982 by Goguen and
	Meseguer, and extended in 1984 by the same authors [27]. It is a strict multilevel security policy
	model, where information is gathered in isolated security classes. Information cannot ow from
	one security class to another. Hiet, Viet Triem Tong, Morin and Mé have used the rst version of
	the Blare model along with JBlare 5 to control the legality of information ows in Java programs
	using a non interference policy. This hybrid intrusion detection (OS/Language levels) allows to
	rene information ow tracking, thus reducing the number of false positives [34].
	1.4.4 Distributed IDSes
	Even though distributed systems have become very popular, particularly since the explosion of
	cloud infrastructures, little research focussed on new models of intrusion detection suitable for
	such environments. Existing approaches are based on aggregation or centralization of events re-

ported by individual misuse IDSes, such as Snort

  unconstrainedppq : bool returns true if the associated program (subject) is unconstrained and false if not. RunpIq is dened in Section 3.2.

	function tag(P)
	for each p in P ; do
	class = Run(itag(p.container))
	if unconstrained(p)
	data = TOP
	code = TOP
	else
	for r in p.canread() ; do
	data += itag(r)
	end
	for x in p.canexec() ; do
	code += Run(x)
	end
	end
	xptag(p.container) = data + code
	for w in p.canwrite() ; do
	w.ptag += data + class
	end
	end
	end

  security eld of struct kern_ipc_perm is used by KBlare to store meta-information concerning the shared memory segment. Such meta-information is stored in a struct blare_tags, as with other volatile objects.

	struct kern_ipc_perm{
	spinlock_t	lock;
	int	deleted;
	int	id;
	key_t	key;
	uid_t	uid;
	gid_t	gid;
	uid_t	cuid;
	gid_t	cgid;
	mode_t	mode;
	unsigned long	seq;
	void	*security;
	};
	struct blare_tags{
	struct list_head *info;
	/* Used by softirqs invoking rcv_skb*/
	spinlock_t info_lock;
	atomic_t refcount;
	int info_rev; //unused
	struct list_head *policy;
	struct list_head *xpolicy;
	};
		Processes attached to a memory segments can access it
	directly, and this is not caught by the operating system. In kernelspace, shared memory segments
	are represented by struct shmid_kernel *shp:
	struct shmid_kernel /* private to the kernel */
	{
	struct kern_ipc_perm	shm_perm;
	struct file *	shm_file;
	unsigned long	shm_nattch;
	unsigned long	shm_segsz;
	time_t	shm_atim;
	time_t	shm_dtim;
	time_t	shm_ctim;
	pid_t	shm_cprid;
	pid_t	shm_lprid;
	struct user_struct	*mlock_user;
	};
	Each struct shmid_kernel embeds a struct kern_ipc_perm:

The

  The structure struct msg_queue is dened in include/linux/msg.h as follows:As for shared memory structures (see Section 4.7.2), the structure for message queues embeds a kern_ipc_perm structure, itself having an opaque security eld. However, rather than labelling the message queues, KBlare labels individual messages. Messages are dened as follows:

	struct msg_msg {
	struct list_head m_list;
	long m_type;
	int m_ts;	/* message text size */
	struct msg_msgseg* next;
	void *security;
	/* the actual message follows immediately */
	};
	struct msg_queue {
	struct kern_ipc_perm q_perm;
	time_t q_stime;	/* last msgsnd time */
	time_t q_rtime;	/* last msgrcv time */
	time_t q_ctime;	/* last change time */
	unsigned long q_cbytes;	/* current number of bytes on queue */
	unsigned long q_qnum;	/* number of messages in queue */
	unsigned long q_qbytes;	/* max number of bytes on queue */
	pid_t q_lspid;		/* pid of last msgsnd */
	pid_t q_lrpid;		/* last receive pid */
	struct list_head q_messages;
	struct list_head q_receivers;
	struct list_head q_senders;
	};

  KBlare tracks communication over UNIX domain sockets of type AF_UNIX, and network sockets of type AF_INET. After receiving messages through a socket (at state i), the new information tag of the process (at state i `1) is updated by appending the new content from the information tag of the socket to it.

	4.7.5 Networking
	UNIX domain sockets, or IPC sockets, allow processes of the same host to communicate through
	network packets. Furthermore, network sockets allow processes of dierent 17 hosts to communicate
	over a network.

  Similarly, when sending information through a socket, the information tag of the socket is updated with the information tag of the process in the same manner:itagpsocketq i`1 " itagpsocketq i Y itagpprocessq i

	Kernel structures
	Sockets are described in kernel space by the socket structure, dened as follows in
	include/linux/net.h:
	struct socket {
	socket_state	state;
	kmemcheck_bitfield_begin(type);
	short	type;
	kmemcheck_bitfield_end(type);
	unsigned long	flags;
	struct socket_wq __rcu *wq;
	struct file	*file;
	struct sock	*sk;
	const struct proto_ops *ops;
	};

15

See include/linux/security.h.

16

From Documentation/security/credentials.txt:[. . . ]As previously mentioned, a task may only alter its own credentials, and may not alter those of another task. This means that it doesn't need to use any locking to alter its own credentials.[. . . ] itagpprocessq i`1 " itagpsocketq i Y itagpprocessq i

  P U and P Π , at execution time, as the intersection of the policy attached to the user on behalf of which the program is being executed, and the policy attached to the executed program (i.e. P u [ P π , u P U, π P Π). When dealing with multiple hosts gathered in groups, we need to take new aspects into consideration. With a distributed information ow policy, each local information ow may involve tainted information from any host of the group. The local information ow policy on each host therefore refers to such disperse information, as well as how it may ow from one host to another. It involves users, active code (programs), persistent containers (e.g. les) and network sockets.Denition 21. The local information ow policy on any host h i of a group, is expressed independently for users, active code (programs), persistent containers (e.g. les), and network packets, and is specied in the policy tags of containers, in a decentralized manner. It is dened by the quadruplet P hi " pP C P , P U , P Π , P N et q where:

•

  Local user u may only access the specied pieces of information from hosts h 1 , . . . , h k within the group 4 , (secrecy w.r.t. users).• Local user u may only mix together the specied piece of information from host h 1 , . . . , h k within the group (integrity w.r.t. users).4 Including the local host, this goes for all the other properties as well.

	k
	ď 1 @u P U, P u Ď ℘p	pX k qq	(6.2)
	(6.2) species the following property:

  In our implementation, information tags are sets of 32 bit integers, thus we cannot have more than 10 information tag elements per IP option if we directly taint network packets with information tags. In order to overcome this limitation, we have designed a distributed security token management protocol, allowing any host of a group to securely exchange security labels, as presented in Chapter 6. However, for the sake of simplicity, our current implementation labels network packets directly by using the tag type 1 as dened in CIPSO, as shown on Figure7.3. By using a bitmap, we are able to represent up to 240 distinct information tags, and thus track up to 240 distinct information elements (including data and code) per group of supervised hosts, which lets us track a sucient amount of taint information for realistic experiments. Therefore, each host h 1 , . . . , h N of the group has reserved space in the bitmap to represent its local information I N and code X N . This structure contains the necessary elds to represent a CIPSO option. It embeds a so-called category mapping in struct netlbl_lsm_secattr_catmap *cat;. This latter structure is used to represent the tags. Labels can be attached and removed from sockets. When a label is attached to a socket, all the packets leaving the system through this socket are labelled with it. The following functions are used to set or remove a label on a socket:

	struct netlbl_lsm_secattr {
	u32 flags;
	[...]
	u32 type;
	char *domain;
	struct netlbl_lsm_cache *cache;
	struct {
	struct {
	struct netlbl_lsm_secattr_catmap *cat;
	u32 lvl;
	} mls;
	u32 secid;
	} attr;
	};
	static inline int netlbl_sock_setattr(struct sock *sk, u16 family, const struct
	netlbl_lsm_secattr *secattr);
	Tag type static inline void netlbl_sock_delattr(struct sock *sk); Tag length Alignment Octet Sensitivity Level	Bitmap of Categories
	8 bit It is also possible to directly label network packets, by using the following function: 8 bit 8 bit 8 bit 240 bit
	static inline int netlbl_skbuff_setattr(struct sk_buff *skb, Figure 7.3: Tag type 1 u16 family,
	const struct netlbl_lsm_secattr *secattr);
	7.4.2 Conversion
	In order to convert from and to NetLabel CIPSO bitmap representation into information tags (i.e.
	doubly linked lists of integers, see Chapter 4) as used in our model, we dened two functions in
	security/blare/netlabel.c:
	struct list_head *blare_catmap2itag(struct netlbl_lsm_secattr_catmap *catmap);
	int blare_itag2catmap(struct list_head* itag, struct netlbl_lsm_secattr_catmap
	*catmap);
	These two functions respectively convert a category mapping in the form of a 240 bit bitmap into a
	linked list of 32 bit integers, and the other way round. It allows us to embed bitmaps into outgoing 7.4 Netlabel packet headers using CIPSO option type 1, and to retrieve them from incoming packets. The LSM
	hooks that we use for this purpose are presented later in this chapter.
	CIPSO labels are supported in the Linux Kernel, through the NetLabel subsystem. NetLabel
	provides an API for LSM modules to attach CIPSO labels to outgoing or incoming network trac
	generated by userspace applications. The API provides functionalities exported to LSM modules,
	translating operations on packets into low level protocol operations. This is dened in the kernel
	source, in the header le include/net/netlabel.h.
	7.4.1 Internal representation
	The main structure that is used by NetLabel to represent security information is the following:

  local_bh_disable() macro disables bottom halves on the local CPU. This ensures that we are not interrupted by a softitq, like those triggered by the reception of network packets (see next Section). However, bottom halves may still execute on other CPUs, therefore we also need locking on the sock structure, and this is what the macro bh_lock_sock_nested() does by disabling the preemption (by calling preempt_disable()) and holding a spinlock.

		local_bh_disable();
		bh_lock_sock_nested(sk);
		rc = netlbl_sock_setattr(sk, sk->sk_family, &secattr);
		bh_unlock_sock(sk);
		local_bh_enable();
	7.6.2 Receiving messages
	Incoming	trac	is	tracked	with	the	LSM	hooks

The

  and www 2 (Apache vhosts1 .) The database server (PostgreSQL) hosts two databases, storing data of the two virtual hosts: db 1 stores information related to www 1 , and db 2 stores information related to www 2 . Connections to www 1 are allowed from the outside. Connections to the other hosts of the VPN and to www 2 are forbidden from the outside. This policy is enforced by classical rewall rules. The following shows how it is possible with our intrusion detection model to detect illegal information ows between hosts caused by an intrusion. We used Debian Squeeze virtual guests running as KVM[START_REF] Habib | Virtualization with kvm[END_REF] instances. The two websites run Wordpress. The website www 1 runs

	the e-commerce plugin Foxypress 2 . We used the version 0.4.2.2 of this plugin, which is vulnerable
	to an upload exploit (EDB-ID: 18991)
	8.2 Attack on a distributed web service
	WEB SERVER	DATABASE
		TRUSTED
		UNTRUSTED
	TRUSTED CLIENT	UNTRUSTED HOST
	Figure 8.2: group of trusted hosts

The following describes an experiment in a distributed system. We have set up an attack scenario targeting a group of trusted hosts running our modied kernel. This group is composed of three hosts: a web server, a database server and a client, all three connected to the same Virtual Private Network (VPN). The web server (Apache) hosts two websites, isolated in two virtual hosts www 1

, et vise à valider notre approche quant à la détection de fuites d'informations impliquant des données condentielles, via l'exploitation d'une vulnérabilité (CVE 2008-5353) au sein d'une page web malveillante. An de détecter de telles fuites d'informations, nous avons tout d'abord marqué chaque information condentielle avec un tag unique, puis nous avons conguré le système avec une politique de sécurité interdisant l'émission d'informations marquées. La propagation de marques entre les objets du système permet ainsi de suivre les informations de bout en bout, et de lever une alerte lorsque des informations marquées arrivent au niveau des sockets réseau. Le second scénario mis en ouvre s'applique aux systèmes distribués. Nous avons considéré un ensemble de plusieurs machines supervisées, fournissant un service web distribué, composé d'un serveur web (Apache), d'un serveur de bases de données (PostgreSQL) et du moteur de blog Word-

press 3 . Le moteur de blog utilise le plugin de e-commerce Foxypress, qui présente une vulnérabilité (EDB-ID 18991). Cette vulnérabilité permet l'upload de chiers arbitraires et l'exécution de code à distance sur la machine qui héberge le service vulnérable. Le serveur web et la base de données hébergent deux sites web, l'un étant public et accessible depuis l'internet, et l'autre privé et accessible uniquement depuis le réseau local. Notre objectif ici était de démontrer la capacité de notre système de détection d'intrusion à détecter les attaques réussies, non seulement au niveau de la machine directement visée, mais également au niveau de chaque machine qui compose le système distribué, an de pouvoir émettre un diagnostic plus riche de l'attaque a-posteriori. L'attaque que nous avons mis en ÷uvre implique un attaquant extérieur qui souhaite accéder aux informations condentielles du site web privé.1 http://www.mozilla.org/firefox/ 2 http://www.oracle.com/technetwork/java/ 3 http://www.wordpress.org

A.1 Special cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3. RELATED WORK

Supervised containers have a policy tag, non supervised containers eventually obtain an information tag as these get tainted.

℘pAq (powerset) denotes the set of all the subsets of A.

Empirically, processes are containers running the code of programs. The set of all programs is Π, therefore the set of all processes is noted C Π .

In C programming, memory is allocated by calling the C library function malloc and released by calling the function free.

The theoretical notation c.policy refers to the set of rules of the policy restraining the container c. It diers from the notation ptagpcq, which denotes the policy tag attached to c, i.e. ptagpcq contains p.policy.

Creating a le does not cause any direct information ow as long as nothing is written in it. However, reading or writing information from/to a le does. We do only rely on such rules possibly responsible for information ows.

3.8. DERIVATION FROM A MAC POLICY

When the NSA introduced SELinux in 1998[START_REF] Vance | Implementing SELinux as a Linux Security Module[END_REF], the Linux kernel security was based on DAC, and did not oer any generic framework for implementing other security models and policies. Such a framework was required in order to implement SELinux.

At the beginnings, the API was not quite stable, which has been widely criticized by the community. The current API, however, is much more stable and it is now an easy task to back/forward port a set of patches using LSM on any kernel version since around kernel version 2.6.26.

4.2. DATA STRUCTURES

see http://lwn.net/Articles/184495/ for more information about their implementation in the Linux kernel.

4.7. SYSTEM CALLS AND HOOKS

Even though collision probability is extremely low, it may occur, as in practice, H is a hash function.

In our model, the support for declassication would refer to the ability for users, programs or containers to declassify information based on rules dened in the information ow policy. This could be done, for instance, by untainting some information given such rules, or by tainting it with new identiers.

Securityfs is a pseudo lesystem based on sysfs and is used by the LSM modules, generally mounted as /sys/k- ernel/security.

Many thanks to Paul Moore for his kind help and cooperation.

This patch was released on the mailing lists of the kernel, with the following subject: cipso: handle CIPSO options correctly when NetLabel is disabled.

As opposed to information ow tracking, information ow control systems block illegal trac.

http://www.blare-ids.org

The CIDre team, at Supélec, www.supelec.fr.

From http://www.apache.org: the term Virtual Host refers to the practice of running more than one web site on a single machine.

www.foxy-press.com

http://www.exploit-db.com/exploits/19100/

At the time of this experiment, we did not discard elements of X when receiving network packets, and the network policy and the policy of the process were combined into the policy tag of the process. This experiment is still valid in the current model, with minor changes in the way tags propagate.

http://www.metasploit.com

Apache maps PHP les in executable memory pages (PROT_EXEC), like it does with dynamic libraries.

Except in the case of eventual covert channels, which by nature are very dicult if not impossible to track. Furthermore, attacks relying on such methods are very uncommon.

http://cve.mitre.org/

Acknowledgements

The completion of this thesis marks the end of an amazing period, in which I met great people and had the opportunity to work on so many interesting things. Spending a year at QUT gave me the ability to discover a new culture, and to gather dierent points of view and approaches on the research side. This was a most exciting experience.

First of all, I would like to express my gratitude to my advisors, Frédéric Tronel and Ludovic Mé for their encouragements, criticisms and support. Their tremendous knowledge of the eld and all their advices have been very helpful to complete this thesis.

I am also very grateful to Colin Fidge, Jason Reid and Andrew Clark for their welcoming and their support during my stay in Australia. Their guidance and their broad skills were very appreciable. In particular, many thanks to Andrew Clark, without whom this cooperation between Supélec and QUT would probably not have been possible. I would like to thank all the members of the CIDre team for all the interesting discussions we had during the last few years, and all the members of the Information Security Institute for welcoming me in Australia. Special thanks to Sajal, Gleb, Mr Kush, Ken and Mark for all the enjoyable moments we spent together.

Finally, thanks to my family and Sarah for supporting me throughout this long road.

Part II Intrusion Detection at the Host Kernel Level

This research is part of a joint research project between Supélec (École supérieure d'éléctricité) and QUT (Queensland

Part I Research Context

/* A policy tag is a list of binary trees (a set of sets) * Each binary tree has the following type: * */ struct policy_tree{ struct list_head list; struct rb_root *root; int cardinal; };

Such elements make use of the SLAB for ecient memory allocation (see Chapter 4). The relevant code is dened in security/blare/network.h.

The network policy applies to both socket families AF_INET and AF_INET6, respectively related to IPv4 and IPv6. A userspace daemon reports alerts to the user via the libnotify library (by checking the output of the system logs for entries written by our reference monitor).

Distributed policy

The distributed version of this implementation carries security labels on network packets, so as to transfer taint information between hosts of the same group. The information ow policy for the group is distributed in each host, at the container level. Hosts are able to determine the origin (i.e. which host it came from) of each piece of information, and the local policy tags of container determine their legality. The network policy, as dened in the previous section, can be used to track incoming and outgoing information on each host of the group. Therefore, the legality of information ows towards processes is veried in a two way run:

• First, on packet reception, the reference monitor checks the content of the security label, and veries that it is legal with respect to P N et .

• Then, the data content of the label (elements of I only 2 ) is merged with the information tag of the process, and the updated information tag's legality is veried. This process is the same as when reading les: elements of X are discarded, see Chapter 3.

CIPSO

To achieve the transportation of security labels over the network, we use CIPSO labels: CIPSO shown on Figure 7.1, CIPSO option size is limited to 40 bytes (320 bits), the current limit for IPv4 options. The tags eld is used to pass the actual security information related to the packets 2 Recall that elements of X in a process's information tag refer to the code currently being run. Similarly, elements of X on a network packet security label refer to the code being run by the process which sent the message. Therefore, merging such elements in the information tag of processes on packet reception would make the new tag inconsistent.

3 https://tools.ietf.org/html/draft-ietf-cipso-ipsecurity-01

System Calls

The following is the list of all system calls on Linux-3.2/x86_64. We analyzed the semantics of all system calls in order to determine in which cases information ows may occur between two or more objects of the operating system. In our implementation, we track information ows resulting in a communication between userspace processes. We consider the kernel as trusted (if the attacker can modify the kernel, he already has full access over the system). Special cases, where information ows may occur, potential hidden channels may exist, particular aspects are highlighted, are numbered in the information ow column of the table below, and are described at the end of this section. 2. mprotect: even though mprotect does not directly cause information ows, it changes the protection mode of memory pages. In cases where shared memory mappings exist with other processes (attached via mmap 1 with the MAP_SHARED ag), it may aect the way information ows occur. As stated in the manpage of mprotect: On Linux it is always permissible to call mprotect() on any address in a process's address space (except for the kernel vsyscall area). In particular it can be used to change existing code mappings to be writable. For this reason, we need to hook calls to mprotect as well.

3. munmap: as stated in the system calls table, this system call does not cause any information ow, however it helps us rene our analysis. When a process shares a memory mapping with another process, there is no way to know which information is swapped between the two, therefore we compute an overestimate of the possible information ows: all information read by one process having write access to the memory region is assumed to be read by the other processes having read access to it. A call to munmap tells us when to stop tracking the caller process (w.r.t a given memory mapping). Tracking munmap is done by a custom added hook, it is not part of LSM.

4. rt_ioctl: this system call manipulates the underlying device parameters of special les. This is commonly used in drivers, for instance, and information may usually be transfered towards a particular device. The last argument of this system call is an untyped pointer to memory, and in some situations, this may possibly lead to information ows between objects of the operating system that we track. However, this case is not handled in our implementation at the moment due to the underlying complexity of hardware drivers. We think reasonable to consider such a case as a hidden channel.

5. mremap, move_pages: the pages remain accessible by the same process through its own address space, therefore there is no communication with other processes.

6. msync: an information ow occurs, as the corresponding memory mapping is synchronized with its underlying le. However, we track information ows at the level of shmat and shmdt, and we consider that the mappings are always synchronized (this is an overestimate).

7. shmat,shmget: we do not directly track the creation of memory segments by processes with shmget, but rather when processes actually attach or detach them to and from their address space, with shmat and shmdt.

8. socket, connect, accept, sendto, recvfrom, sendmsg, recvmsg, bind, listen, socketpair: we do not directly track all these calls, but instead, we track calls to sendmsg and recvmsg, were actual information ows occur. 9. clone, fork:

1 POSIX says that the behavior of mprotect() is unspecied if it is applied to a region of memory that was not obtained via mmap(2)

• clone is mostly used to create threads within one process's address space. If called with CLONE_VM or CLONE_THREAD ags, the memory space of the parent is shared with the child.

• fork is a glibc wrapper, it invokes clone with the corresponding ags.

10. execve: execute a program. This is tracked in our implementation.

11. shmdt: this system call does not cause any information ow. However, as with munmap, we need to keep tracks of processes detaching memory segments, in order to stop tracking information ows from and towards to the detached memory segment.

12. msgsnd, msgrcv, mq_timedsend, mq_timedreceive: send/receive a message from message queue. This is tracked by our implementation.

13. ptrace: information ows are involved when a process is traced: the caller may access information from the child, and communicate information towards the child. Tracing processes as well as accessing sensitive information in /proc is tracked by LSM (hooks security_ptrace_access_check and security_ptrace_traceme). We do not track calls to ptrace in our current implementation.

14. rt_sigqueueinfo: this system call provides the low-level interface to send a signal plus data to a process or thread. We consider it as a hidden channel, as the main purpose of this interface is signal handling. The receiver of the signal can obtain the accompanying data by establishing a signal handler with the sigaction(2) SA_SIGINFO ag. We do not track this in our current implementation. This could be tracked by adding a hook on calls to sigaction.

15. mknod: le is created empty, therefore there is no information ow.

16. uselib: we do not directly track these calls, but we track the underlying calls to mmap when mapping the shared library into memory. 17. swapon: starts swapping to le/device. Even though swapping involve information ows, we do not track access to the swap area, as is impractical to do so (because swapping is managed by the kernel, and we do not hook kernel code, that we consider as trusted). Accessing the swap area from userspace is only allowed to the system administrator. Future versions of our implementation may restrict access to the swap area from userspace (even to the system administrator).

18. init_module: loads an ELF binary into kernel space. This system call requires privileges, and is not tracked by our implementation as it modies the kernel.

19. setxattr, lsetxattr, fsetxattr, getxattr, lgetxattr, fsetxattr: get/set le extended attributes.

An information ow occurs and may be used to exchange information between userspace processes. We do not track it in our current implementation, however this is achievable by using LSM hooks (security_inode_setxattr and security_inode_getxattr). It will be implemented in future releases.

20. kexec_load: this is used to load a new kernel at runtime (live booting of a new kernel over the currently running kernel). We do not track such a low-level mechanism: it would be required to ag portions of the memory that are not overwritten by the new kernel.

21. add_key, request_key: access kernel's key management facility. This is used e.g. to mount remote lesystem which require authentication or a key to enable access. It is possible to use it in a diverted way to establish communication between userspace processes. It is untracked in our current implementation.

22. splice, tee, vmsplice: move data between le descriptors without copying between userspace and kernelspace copy standard output to les and standard output move user pages into a pipe. Information ows occur between userspace and kernelspace.