Claude Universite

Bernard -Lyon

M François-Noël

Gilly M Le Professeur

Hamda Ben

Hadid M Le Professeur

Philippe Lalle

M Le Professeur

Germain Gillet

M Alain Helleu

Composantes Sante

J Etienne

La Mme

C Professeure

Burillon

D Bourgeois

Vinciguerra

Y Matillon

Mme La Professeure

A-M Schott

François Goasdoué

Benjamin Nguyen

Je Tiens À Remercier Également

Ludovic Mé

Vincent Roca

Eric Simon D'

Nadhir, Sayd, Lazhar Ahmed Kamel

Olia Opencyc

Gem

Espania Museos

Gnoss

Freebase Linklion

Ariadne Organic

Edunet Bio2rdf

Portsmouth Zaragoza

Statusnet Gegeweb

lobid Organizations

Keywords: RDF, Authorization, Semantic Reasoning, Inference Leakage, Enforcement, Linked Data RDF, Autorisation, Raisonnement sémantique, Fuite d'inférence, Application, Linked Data . | = . | . . k 0 | . . . | k n Value :=

La réalisation de ce mémoire a été possible grâce au concours de plusieurs personnes à qui je voudrais témoigner toute ma reconnaissance.

Avant tout, j'adresse mes sincères remerciements à mon directeur de thèse Mohand-Saïd Hacid et à mes co-encadrants Romuald Thion et Emmanuel Coquery, pour leur soutien tout

[Sayah 2016] Tarek Sayah, Emmanuel Coquery, Romuald Thion and Mohand-Saïd Hacid. Access Control Enforcement for Selective Disclosure of Linked Data. In STM, Greece 2016 (Acceptance rate : 35%).

Résumé étendu en français 1 Contexte

Le Web est devenu l'outil principal de diffusion de l'information pour les organismes privés et publics, à travers lequel d'énormes quantités d'informations sont échangées chaque jour. Le web traditionnel est utilisé pour transmettre, recevoir et afficher des contenus encapsulés sous forme de documents. Ces documents étaient destinés à la consommation humaine et ne pouvait pas être compris par des machines. Le Web sémantique également appelé Web de données peut être conceptualisé comme une extension du Web actuel afin de permettre la création, le partage et la réutilisation intelligente des contenus web pour qu'ils soient lisibles par la machine.

Le Linked Data concerne tout simplement l'utilisation du Web pour créer des liens typés entre les données provenant de sources différentes. Techniquement, Linked Data réfère à un ensemble de bonnes pratiques pour l'édition et la connexion des données structurées sur le Web de sorte que ces données soient lisibles par la machine, leur sens est explicitement definie, elles sont liées à d'autres données externes, et être reliées à partir de données externes. Berners-Lee discute les quatre principes de base pour le Linked Data comme [BL06]:

1. Utiliser les URIs pour nommer les choses 2. Utiliser les URIs HTTP de telle sorte que les gens puissent chercher ces noms 3. Quand quelqu'un regarde une URI, fournir des informations utiles, en utilisant les normes (RDF, SPARQL)

4. Inclure des liens vers d'autres URIs, afin qu'ils puissent découvrir plus de choses Un mouvement général "d'ouverture des données" (Linked Open Data) 1 est suivi par les institutions (ex., Enseignement Supérieur et Recherche en France 2 ), les collectivités locales (ex., Villes de Lyon et de Grenoble 3 ), les bases de données thématiques (ex., Dbtune, MusicBrainz 4 ), les organizations (BBC dans ses systèmes internes de production de contenus [KSR + 09]), géographiques et bien sûr généralistes (ex., GeoNames, Wikipedia 5 )).

Lier des données distribuées à travers le Web nécessite un mécanisme standard pour spécifier l'existence et la signification des liens entre les éléments décrits dans ces données. Ce mécanisme est fourni par le format Resource Description Framework (RDF). La Figure 1 montre des ensembles de 1. http://www.mckinsey.com/business-functions/business-technology/ our-insights/open-data-unlocking-innovation-and-performance-withliquid-information 2. http://data.enseignementsup-recherche.gouv.fr 3. http://data.grandlyon.com et http://data.beta.metropolegrenoble.fr 4. http://dbtune.org and http://linkedbrainz.org 5. http://www.geonames.org/ontology and http://wiki.dbpedia.org données qui ont été publiés dans le format Linked Data 6 . La figure montre des datastores qui appartiennent à différents domaines de thématiques (gouvernement, publications, sciences de la vie, etc.). La taille du Web de données est estimé à plus de 3400 sources ouvertes pour un volume total de plus de 85 milliards de triplets(statements) 7 , et plus de 8500 sources sur le portail de données ouvertes de l'Union Européenne 8 . RDF a gagné beaucoup d'attention ces dernières années, et par conséquent un nombre croissant d'ensembles de données sont maintenant représentés avec ce langage. Cette popularité a évidemment motivé certains travaux de recherche sur la conception de systèmes de bases de données adaptés et efficaces pour stocker efficacement, interroger et raisonner sur de grandes quantités de données RDF. Ces systèmes sont souvent appelés Entrepôts RDF (RDF store) ou triplestore. Plusieurs entrepôts RDF ont été développés pour traiter les données RDF, dont certains sont natifs alors que d'autres utilisent des backend SGBDR. Les entrepôt RDF natifs sont ceux qui sont mis en oeuvre à partir de zéro et qui exploitent le modèle RDF pour stocker efficacement et accéder aux données RDF, tels que 4Store 9 , Allegro-Graph 10 , Stardog 11 , Jena TDB 12 et Sesame 13 . Les entrepôts qui ne sont pas natif RDF tels que Virtuoso 14 et Jena SDB 15 , utilisent une base de données relationnelle pour stocker les triplets. L'un des concepts clés de l'architecture du Web sémantique sont les graphes nommés (named graphs) qui est une simple extension du modèle de données RDF qui transforme les triplets RDF en quads. Les graphes nommés sont des ensembles de triplets identifiés par IRIs, permettant des descriptions sur ces ensembles comme des informations sur la provenance, le contexte et d'autres métadonnées.

Comme la demande pour les données et la gestion de l'information augmentent, il y a aussi un besoin crucial pour le maintien de la sécurité des sources de données, les applications, et systèmes d'information. Différents domaines d'études ont été introduits pour concevoir des approches appropriées capable de fournir des garanties de sécurité. Ces domaines d'études concernent l'authentification [START_REF] Lamport | Password authentication with insecure communication[END_REF], le contrôle d'accès [START_REF] Griffiths | An authorization mechanism for a relational database system[END_REF], la cryptographie [DH76, RSA78] et l'audit [ABF + 04]. Suite à l'évolution de ces domaines, les systèmes de bases de données offrent de nouveaux paradigmes de sécurité pour faire face aux vulnérabilités induites par de nouvelles fonc- La protection des ressources contre les accès non autorisés est l'une des principales caractéristiques des systèmes d'aujourd'hui. L'un des principaux services de sécurité nécessaires pour assurer la protection des données est le contrôle d'accès. Ce dernier garantit qu'un utilisateur ne peut accéder qu'aux ressources auxquelles elle/il est autorisé.

Dans cette thèse, nous nous sommes concentré sur les problèmes de sécurité qui se posent principalement dans le contexte du Linked Data, en particulier l'exposition sélective des données RDF.

Notre objectif principal est d'encourager les entreprises et les organisations à publier leurs données RDF dans l'espace global de données liées. En effet, les données publiées peuvent être sensibles, et par conséquent, les fournisseurs de données peuvent être réticent à publier leurs informations, à moins qu'ils ne soient certains que les droits d'accès souhaités des différentes entités sont appliquées correctement à leurs données, et qu'aucune donnée sensible n'est révélée (par erreur). Donc la question de la sécurisation du contenu RDF et la garantie de l'exposition sélective de l'information à différentes catégories d'utilisateurs devient d'autant plus importante.

Paul Terry a écrit dans CTO Vision16 : To realize value from your data, you need to be able to share it among many stakeholders-internal lines of business, partners, researchers, and many others. But you also have a moral, ethical, and often legal, obligation to make sure that data is used responsibly. That means protecting individuals? privacy and assuring that their data is used only for legitimate purposes. As you gather more data from more parts of your organization, that gets very tricky very fast. [...] It quickly becomes clear that this is about more than simply checking a box for whether data is "secure". It?s incredibly valuable to have all that data in one place where it can be analyzed, but you need to assure that different types of stakeholders can see only the information they legitimately need, and no more.

Énoncé du problème

Dans cette thèse, nous nous sommes intéressés à l'exposition sélective des données RDF et du problème de fuite d'inférence. Au cours des dernières années, le problème de contrôler l'accès aux données RDF a attiré une attention considérable à la fois la communauté de la sécurité et celle de base de données. Notre objectif était de définir une politique d'autorisations qui sera intégrée à l'entrepôt RDF pour contrôler l'exposition des données RDF. De plus, nous devons nous assurer que les données divulguées ne peuvent pas être utilisées pour déduire des informations confidentielles. Dans ce contexte, nous étions intéressés par les problèmes suivants:

Exposition sélective des données RDF

Compte tenu de la nature sensible de l'information, les différentes parties de données RDF peuvent nécessiter des droits d'accès selon les privilèges du requérant. Dans cette thèse, nous nous sommes intéressés à l'exposition sélective des informations en fonction du contenu RDF, de qui le demande et sous quel contexte. La plupart des entrepôts RDF de nos jours offrent une protection au niveau graphe nommé. Par exemple, une telle fonctionnalité a été introduite dans 4store version 1.1.5 17 . La sécurité au niveau graphe est disponible dans Virtuoso 18 ou aussi sur Stardog version 3.1 19 . Le problème avec ces modèles est que les politiques de contrôle d'accès sont définies sur des graphes nommés qui doivent être créés par rapport aux politiques. Par exemple, si une politique stipule qu'une infirmière possède l'accès aux dossiers des patients, alors tous les triplets liés aux dossiers du patient doivent être réunis dans un seul graphe nommé sur lequel la politique est définie. En outre, les politiques complexes peuvent conduire à la création de plusieurs graphes nommés. Avoir un grand nombre de politiques complexes peut conduire l'administrateur à créer plusieurs graphes nommés qui pourraient être difficiles à gérer. De plus, un problème de redondance est soulevé puisque un triplet peut appartenir à plusieurs graphes nommés. Certains entrepôts RDF sont plus expressifs comme AllegroGraph 20 sur lequel l'accès est basé sur des motifs relatifs à un unique triplet 21 . Ceci permet la définition des autorisations simples telles que interdire ou autoriser l'accès aux triplets représentant les dossiers des patients. Cependant, des politiques plus expressives ne peuvent pas être spécifiés. Par exemple, une autorisation, telle que Refuser l'accès aux dossiers des patients s'ils ont le cancer ne peut pas être spécifiée.

Étant donné la nature ouverte du web dans lequel les données RDF sont publiées, le sujet pourrait ne pas être connu par le système avant l'envoi d'une requête. Par conséquent, l'exposition sélective ne peut pas compter que sur des politiques de contrôle d'accès traditionnelles basées sur l'identité ou le rôle. Le controle d'accès basé sur les attributs (Attribute Based Access Control (ABAC)) est un modèle qui permet plus de flexibilité en définissant des autorisations sur la base des attributs des sujets et objets. ABAC permet d'éviter la nécessité d'attribuer directement les autorisations à des sujets 17. http://4store.org/trac/wiki/GraphAccessControl 18. http://docs.openlinksw.com/virtuoso/rdfgraphsecurity.html 19. http://docs.stardog.com/#_security 20. http://franz.com/agraph/allegrograph 21. http://franz.com/agraph/support/documentation/v4/ security.html#filters individuels avant leur demande d'effectuer une opération sur l'objet.

Problème de fuite d'inférence

Le deuxième enjeu est de veiller à ce que des informations sensibles ne puissent pas être déduites, en utilisant les règles d'inférence, une fois que les données ont été communiquées à l'utilisateur. Ce problème est connu dans la littérature de contrôle d'accès comme problème d'inférence [START_REF] Farkas | The inference problem: A survey[END_REF] appelé dans le manuscrit problème de fuite d'inférence. Selon le World Wide Web Consortium (W3C), l'inférence sur le Web sémantique en utilisant le Resource Description Framework (RDF) permet "d'améliorer la qualité de l'intégration des données sur le Web en découvrant de nouvelles relations, et d'analyser automatiquement le contenu des données". Les règles d'inférence sont utilisées pour obtenir de nouveaux triplets à partir de ceux qui sont explicitement affirmés dans un entrepôt RDF. En particulier, un ensemble de règles d'inférence connu par RDF Schema (RDFS) a été normalisé [START_REF] Patrick | Rdf 1.1 semantics[END_REF]. Des modèles d'autorisation ont été proposés pour le contrôle des accès aux données RDF, à la fois en présence de règles d'inférence [RFJ05, LKZ + 12, PMF + 12, JF06] ou non [ADCH + 07, [START_REF] Flouris | Controlling access to rdf graphs[END_REF][START_REF] Rachapalli | Towards fine grained RDF access control[END_REF]. Cependant, le problème est que cette capacité d'inférence peut être utilisée par un utilisateur (malveillant) pour déduire des données sensibles à partir de données publiques.

Pour illustrer le problème de fuite d'inférence, supposons que les triplets RDF indiquant que quelqu'un a un cancer sont étiquetés comme confidentiels (ex.triplets similaires à (?p ; rdf : type ; :Cancerous) avec ?p désignant une personne), tandis que ceux indiquant qu'une personne a une tumeur sont publics au sein d'un hôpital (ex. triplets de la forme (?p; :hasTumor; ?t)). S'il existe un triplet public indiquant que le domaine du prédicat : hasTumor est : Cancerous (ex. (: hasTumor; rdfs : domain; :Cancerous)), alors, en utilisant la règle RDFS qui fait correspondre le domaine d'un prédicat au type de ses sujets, des informations sensibles peuvent être déduites des triplets publics. La situation est encore pire lorsque le système de déduction est enrichi avec des règles définies par l'utilisateur.

Application et performance

Des enjeux particuliers découlent de l'application du contrôle d'accès. Le premier enjeu est l'impact de l'application du modèle de contrôle d'accès sur la performance du système: nous devons nous assurer que l'application du contrôle d'accès occasionne un faible surcoût sur la performance des entrepôts RDF. Le deuxième enjeu sont les mécanismes nécessaires pour appliquer le contrôle d'accès. Le mécanisme d'application doit être déployable dans l'entrepôt RDF avec des mécanismes supplémentaires minimes et, idéalement, sans altération de ses composants internes.

Étude des travaux connexes

Une première étude de l'état de l'art a conduit à la définition des critères d'évaluation des travaux connexes dans le contrôle d'accès aux données RDF, y compris l'expressivité de spécification des politiques, la résolution des conflits générés par des décisions contradictoires et la vérification des inférences non autorisées. Nous nous sommes appuyés sur ces critères pour analyser les travaux réalisés dans le domaine du contrôle d'accès aux données RDF. L'étude a permis de déterminer des critères bien traités tels que les actions supportées, l'expressivité des objets et la protection des triplets explicites et implicites. D'autres critères ont été peu considérés, y compris la résolution des conflits, l'expressivité des sujets et le problème de fuite inférence. Nous nous sommes intéressés sur ces derniers critères pour les contributions de cette thèse.

Contributions

Suite à une analyse détaillée des modèles existants de contrôle d'accès aux données RDF, nos contributions ont concerné quatre aspects, illustrés par la Figure 2.

Conception d'un nouveau modèle de contrôle d'accès

Nous avons conçu un nouveau modèle de contrôle d'accès pour les données RDF appelé AC4RDF pour Access Control For the Resource Description Framework. Nous avons défini la sémantique formelle d'un langage déclaratif basé sur les motifs de graphe élémentaires du langage SPARQL, afin de faciliter l'intégration du modèle dans les systèmes concrets. La sémantique du modèle est définie par le sous-graphe positif (autorisé) à partir du graphe de base. La requête de l'utilisateur est évaluée sur son sous-graphe positif ne contenant que les triplets accessibles. Notre modèle est ainsi complètement indépendant du langage de requêtes utilisé. Notre langage permet de définir des autorisations positives et négatives afin de traiter les exceptions des droits d'accès qui pourraient se produire dans la vie réelle. L'utilisation des autorisations négatives donne lieu au traitement des conflits qui se produisent lorsque le même objet est autorisé par une autorisation et refusé par une autre. Des stratégies de résolution des conflits sont utilisées pour résoudre de tels conflits en sélectionnant les autorisations préférées à appliquer par rapport à certaines propriétés des autorisations. Alors que la plupart des travaux codent en dur leurs stratégies, d'autres les définissent comme des paramètres qui sont fixés par l'administrateur lors de la conception de la politique. Nous proposons une approche plus libérale en définissant notre politique en utilisant une fonction abstraite de résolution de conflits qui est fournie par l'administrateur. Nous montrons comment coder les stratégies classiques telles que la First Applicable, Denials Take Precedence et la Permissions Take Precedence en plus de stratégies plus élaborées telle que la Most Specific Takes Precedence.

Problème de fuite d'inférence et solutions

Les modèles de contrôle d'accès classiques offrent une protection contre les accès directs à des informations sensibles. Cependant, les accès indirects à des informations sensibles peuvent encore être possible via des règles inférences. Dans le contexte du Linked Data, le problème se produit lorsque les triplets implicites sensibles peuvent être déduite à partir de triplets non sensibles à l'aide de règles d'inférence connues. Notre deuxième contribution a consisté à définir formellement la propriété de cohérence qui capture le problème des fuites d'inférence qui se pose lorsque des triplets confidentiels sont déduits à partir de triplets autorisés. Cette propriété garantit que les informations confidentielles ne peuvent pas être déduites à partir d'informations non confidentielles par rapport à un ensemble de règles d'inférence. Pour résoudre ce problème, nous proposons un algorithme de vérification statique, prouvé correct et complet, qui permet de détecter si une politique est cohérente quel que soit le graphe RDF utilisé. En cas d'incohérence de la politique, l'algorithme génère un ensemble de motifs de graphes contreexemples qui représentent des modèles sur lesquels la politique présente un problème de fuite d'inférence. Ces graphes contre-exemples peuvent être utilisés par l'administrateur pour corriger la politique. Nous proposons une méthode itérative qui permet à l'administrateur de corriger la politique en utilisant l'algorithme. Nous montrons une autre alternative d'utilisation des graphes contre-exemples qui consiste à les utiliser comme contraintes d'intégrité lors des mises à jour du graphe de base.

Administration des politiques

Les politiques du modèle AC4RDF sont définies sans spécifier le sujet pour lequel les autorisations sont assignés. Ce qui permet d'utiliser n'importe quel modèle de contrôle d'accès en amont pour mapper les utilisateurs à leurs autorisations assignées. Nous proposons un langage de contrôle d'accès de haut niveau qui permet la définition de politiques globales qui sont ensuite compilées en politiques concrètes du modèle AC4RDF. Nous avons choisi de définir nos politiques sur la base des attributs d'utilisateur suivant l'approche Attribute Based Access Control (ABAC), où l'accès aux ressources protégées est basé sur un utilisateur ayant des attributs spécifiques (par exemple le nom, le rôle, la date de naissance, adresse, numéro de téléphone, etc). Nous avons défini la syntaxe et la sémantique d'un langage inspiré par XACML en définissant les principaux composants de la solution proposée et en montrant comment la politique de l'utilisateur est générée et appliquée. Intuitivement, une politique globale peut être représentée dans une structure d'arbre où les noeuds intermédiaires représentent les politiques, les feuilles représentent les autorisations et les arêtes sont étiquetées avec des cibles représentant des conditions à base d'attributs. Les conditions sont évaluées en utilisant des paires clé/valeur représentant les attributs fournis par les sujets. Celuici fournit ses attributs dans une demande qui est évaluée sur l'arbre de la politique globale pour déterminer les autorisations qui lui sont attribuées. Sur la base de ces autorisations, le sous-graphe positif du sujet est calculé, et la requête est évaluée sur ce sous-graphe ne retournant que ses triples accessibles.

Application du modèle de contrôle d'accès et expérimentations

Cette contribution consiste en la proposition d'un cadre d'application basé sur les annotations pour le modèle AC4RDF. L'idée est de matérialiser les autorisations applicables à chaque triplet dans un bitset qui est utilisé pour annoter ce triplet. De même, des bitsets sont aussi attribués aux sujets représentant le sous-ensemble des autorisations qui leur est assigné. Pour calculer le sous-graphe positif du sujet, la fonction de résolution de conflits est appliquée sur l'intersection entre l'ensemble des autorisations applicables au triplet et celles assignées au sujet. Ce qui revient à faire un et logique entre les bitsets du triplet et du sujet. Le système évalue ensuite la requête du sujet sur son sous-graphe positif. Pour stocker les bitsets, nous utilisons la position du nom de graphe. Faisant ainsi, nous n'avons pas besoin de mécanismes supplémentaires pour appliquer notre modèle vu que la majorité des entrepôts RDF actuels supportent les graphes nommés. Nous avons implémenté notre solution sur Jena TDB 22 et effectué des expérimentations pour 22. https://jena:apache:org/documentation/tdb calculer les surcoûts de l'intégration du modèle sur la performance du système. Nos expérimentations ont montré que notre implémentation entraîne un surcoût raisonnable durant l'exécution (environ + 50%) par rapport à la solution optimale qui consiste à matérialiser le sous-graphe positif. Il faut noter que cette dernière solution n?assure pas le passage à l?échelle puisqu?il faut matérialiser le sous-graphe positif de chaque utilisateur.

Organisation du manuscrit

Ce manuscrit comporte 3 chapitres précédés d'une introduction et suivi d'une conclusion. Il comporte également une annexe qui contient des définitions et lemmes techniques additionnels ainsi que la liste des requêtes utilisées dans les expérimentations.

Chapitre 1 : Introduction

L'introduction décrit le contexte et les différents défis auxquels nous nous sommes intéressés dans cette thése et les solutions qu'on a proposées. Dans la section 1.1, nous commençons par donner des définitions générales du Linked Data ainsi que quelques statistiques concernant les données publiées. Ensuite, nous discutons dans la section 1.2 les défis scientifiques en s'appuyant sur l'état de l'art. Enfin, nous présentons dans la section 1.4 nos contributions permettant d'atteindre les différents objectifs de cette thèse.

Chapitre 2 : Technical background and related work

Ce chapitre est consacré à positionner les contributions proposées dans cette thèse par rapport à l'état de l'art. Nous commençons par une introduction du Web sémantique en section 2.1 avec un rappel de la syntaxe et la sémantique du modèle de données RDF. Nous donnons un aperçu du langage de requête SPARQL 1.1 RDF, et comment il peut être utilisé pour traiter les données RDF. Nous définissons l'inférence, notamment les inférences RDFS, qui permet la déduction des nouvelles données à partir de celles qui sont explicitement définies. Dans la section 2.2, nous donnons un aperçu des modèles de contrôle d'accès les plus connus dans la littérature, suivi par les stratégies de résolution des conflits utilisées pour résoudre les conflits qui découlent de l'utilisation des autorisations négatives. Ensuite, dans la section 2.3, nous présentons les travaux qui ont été proposés pour contrôler l'accès aux données RDF, et les critères utilisés pour les comparer, suivis par la synthèse de l'étude de ces travaux en section 2.4. En se basant sur les critères qui ne sont pas bien considérés, nous présentons enfin dans la section 2.5 les solutions que nous avons proposées.

Chapitre 3 : A fine-grained access control model for RDF stores

Ce chapitre présente notre première contribution, à savoir un modèle de contrôle d'accès a grains fins pour les données RDF. La sémantique de notre modèle est présentée dans la section 3.1, dans laquelle nous commençons par donner la sémantique des autorisations qui est basée sur des motifs SPARQL, suivie par la définition des politiques de contrôle d'accès. Nous donnons des conditions qui doivent être respectées pour que la politique soit bien formée. Pour résoudre les conflits éventuels, nous donnons les caractéristique de la fonction abstraite de résolution de conflits, et nous définissons des propriétés qui permettent de prouver si une fonction applique une stratégie de résolution de conflits donnée. Enfin nous montrons dans la section 3.2 comment construire les stratégies de résolution de conflits connues dans la litérature de contrrôle d'accès.

Chapitre 4 : Inference leakage problem and solution

Dans ce chapitre, nous présentons le problème de fuite d'inférence et la solution proposée pour y faire face. La section 4.1 est dédiée à l'introduction du problème d'inférence dans les autres modèles de données. Par la suite, nous donnons, dans la section 4.2, nous donnons un exemple qui illustre le problème de fuite d'inférence suivi par la définition formelle de la propriété de cohérence. Nous proposons ensuite une solution à ce problème en section 4.3 dans laquelle nous proposons un algorithme de vérification statique qui permet de vérifier si une politique est cohérente Nous donnons les preuves de la correction et la complétude de notre algorithme. Enfin nous montrons par des exemples comment utiliser les contre-exemples générés par l'algorithme pour corriger la politique. Enfin nous montrons la deuxième alternative pour utiliser les graphes contre-exemples, qui consiste à utiliser les graphes contre-exemples comme contraintes d'intégrité.

Chapitre 5 : Policy administration

Dans ce chapitre nous présentons un langage de haut niveau basé sur les attributs, qui permet la définition de politiques multi-utilisateurs. Nous commençons par un exemple qui illustre l'idée de la représentation de la politique sous la forme d'un arbre. Ensuite, dans la section 5.1, nous donnons l'architecture globale de la solution proposée. Pour définir formellement la sémantique de notre langage, nous fournissons une syntaxe de notre formalisme par une grammaire BNF étendue (EBNF) en section 5.2. Nous présentons ensuite la sémantique de chaque composant du langage. Dans la section 5.3, nous montrons par des exemples, la façon avec laquelle, une demande d'un sujet est évaluée sur une politique globale pour générer une politique utilisateur. Enfin, nous donnons un exemple complet de l'évaluation d'une requête d'un utilisateur ayant un certain nombre d'attributs.

Chapitre 6 : Policy enforcement and experiments

Dans ce chapitre nous montrons comment appliquer des politiques multiutilisateurs en utilisant une approche d'annotation de données. Nous commençons par présenter notre méthode d'encodage dans la section 6.1. Nous prouvons que notre encodage est correct et montrons comment une requête utilisateur est évaluée sur une graphe annoté. Nous donnons ensuite dans la section 6.2, des détails de l'implémentation de notre solution sur un entrepôt RDF concret, à savoir Jena TDB. A la fin, nous présentons les résultats de nos expérimentations qui sont séparés en deux parties : statique et dynamique. La partie statique présente les temps d'annotation du graphe de base en variant la taille du graphe de base et le nombre d'autorisations. La partie dynamique présente les temps d'évaluation des requêtes en variant la taille du graphe de base,le nombre d'autorisations de la politique et enfin les requêtes et les autorisations assignées à l'utilisateur.

Chapitre 7 : Conclusion

Ce chapitre rappelle les contributions et présente des extensions et des travaux futurs. Ces derniers sont subdivisés par rapport aux exigences sur lesquelles nos propositions ont été conduites, à savoir : l'expressivité, la vérifiabilité et la performance.

Références

Le manuscrit en anglais

Abstract

The emergence of the Semantic Web has led to a rapid adoption of the RDF (Resource Description Framework) to describe the data and the links between them. The RDF graph model is tailored for the representation of semantic relations between Web objects that are identified by IRIs (Internationalized Resource Identifier). The applications that publish and exchange potentially sensitive RDF data are increasing in many areas: bioinformatics, e-government, open data movement. The problem of controlling access to RDF content and selective exposure to information based on privileges of the requester becomes increasingly important. Our main objective is to encourage businesses and organizations worldwide to publish their RDF data into the linked data global space. Indeed, the published data may be sensitive, and consequently, data providers may avoid to release their information, unless they are certain that the desired access rights of different accessing entities are enforced properly, to their data. Hence the issue of securing RDF content and ensuring the selective disclosure of information to different classes of users is becoming all the more important. In this thsesis, we focused on the design of a relevant access control for RDF data. The problem of providing access controls to RDF data has attracted considerable attention of both the security and the database community in recent years. New issues are raised by the introduction of the deduction mechanisms for RDF data (e.g., RDF/S, OWL), including the inference leakage problem. Indeed, when an owner wishes to prohibit access to information, she/he must also ensure that the information supposed secret, can not be inferred through inference mechanisms on RDF data.

In this PhD thesis we propose a fine-grained access control model for RDF data. We illustrate the expressiveness of the access control model with several conflict resolution strategies including most specific takes precedence. To tackle the inference leakage problem, we propose a static verification algorithm and show that it is possible to check in advance whether such a problem will arise. Moreover, we show how to use the answer of the algorithm for diagnosis purposes. To handle the subjects' privileges, we define the syntax and semantics of a XACML inspired language based on the subjects' attributes to allow much finer access control policies. Finally, we propose a data-annotation approach to enforce our access control model, and show that our solution incurs reasonable overhead with respect to the optimal solution which consists in materializing the user's accessible subgraph.

Résumé

L'émergence du Web sémantique a mené à une adoption rapide du format RDF (Resource Description Framework) pour décrire les données et les liens entre elles. Ce modèle de graphe est adapté à la représentation des liens sémantiques entre les objets du Web qui sont identifiés par des IRI. Les applications qui publient et échangent des données RDF potentiellement sensibles augmentent dans de nombreux domaines : bio-informatique, e-gouvernement, mouvements open-data. La problématique du contrôle des accès aux contenus RDF et de l'exposition sélective de l'information en fonction des privilèges des requérants devient de plus en plus importante. Notre principal objectif est d'encourager les entreprises et les organisations à publier leurs données RDF dans l'espace global des données liées. En effet, les données publiées peuvent être sensibles, et par conséquent, les fournisseurs de données peuvent être réticents à publier leurs informations, à moins qu'ils ne soient certains que les droits d'accès à leurs données par les différents requérants sont appliqués correctement. D'où l'importance de la sécurisation des contenus RDF est de l'exposition selective de l'information pour différentes classes d'utilisateurs. Dans cette thèse, nous nous sommes intéressés à la conception d'un contrôle d'accès pertinents pour les données RDF. De nouvelles problématiques sont posées par l'introduction des mécanismes de déduction pour les données RDF (e.g., RDF/S, OWL), notamment le problème de fuite d'inférence. En effet, quand un propriétaire souhaite interdire l'accès à une information, il faut également qu'il soit sûr que les données diffusées ne pourront pas permettre de déduire des informations secrètes par l'intermédiaire des mécanismes d'inférence sur des données RDF.

Dans cette thèse, nous proposons un modèle de contrôle d'accès à grains fins pour les données RDF. Nous illustrons l'expressivité du modèle de contrôle d'accès avec plusieurs stratégies de résolution de conflits, y compris la Most Specific Takes Precedence. Nous proposons un algorithme de vérification statique et nous montrons qu'il est possible de vérifier à l'avance si une politique présente un problème de fuite d'inférence. De plus, nous montrons comment utiliser la réponse de l'algorithme à des fins de diagnostics. Pour traiter les privilèges des sujets, nous définissons la syntaxe et la sémantique d'un langage inspiré de XACML, basé sur les attributs des sujets pour permettre la définition de politiques de contrôle d'accès beaucoup plus fines. Enfin, nous proposons une approche d'annotation de données pour appliquer notre modèle de contrôle d'accès, et nous montrons que notre implémentation entraîne un surcoût raisonnable durant l'exécution. The Web is becoming the main information dissemination for private and public organizations. A huge amount of information is exchanged every day. The traditional web is used to transmit, receive, and display content encapsulated as documents. These documents were intended for human consumption and could not be understood by machines. The Semantic Web also referred to as web of data can be conceptualized as an extension of the current Web so as to enable the creation, sharing and intelligent re-use of machine-readable content on the Web.

Chapter 1

Introduction Contents

Context

Linked Data [Bizer 2009] is simply about using the Web to create typed links between data from different sources. Technically, Linked Data refers to a set of best practices for publishing and connecting structured data on the Web in such a way that they are machine-readable, their meaning is explicitly defined, they are linked to other external data sets, and can in turn be linked to from external data sets [Berners-Lee 2006]. Berners-Lee discusses the four basic principles for linked data as:

1. Use URIs as names for things 2. Use HTTP URIs so that people can look up those names 3. When someone looks up a URI, provide useful information, using the standards (RDF, SPARQL)

4. Include links to other URIs, so that they can discover more things

The Linked (Open) Data trend 1 is followed by institutions (eg., Higher Education and Research in France 2 ), local authorities (eg., Cities of Lyon and Grenoble 3 ), Thematic databases (eg., Dbtune, MusicBrainz 4 ), Organizations (BBC in its internal content production systems [Kobilarov 2009]), geographical and of course general data (eg., GeoNames, Wikipedia 5 )).

Linking data distributed across the Web requires a standard mechanism for specifying the existence and meaning of connections between items described in this data. This mechanism is provided by the Resource Description Framework (RDF), which is examined in detail in Chapter 2. Figure 1.1 shows datasets that have been published in Linked Data format 6 . The figure shows datastores that belong to different thematic domains (government, publications, life sciences, etc). The size of the Web of Data is estimated to over 3400 open sources for a total volume of over 85 billion triples (statements) 7 , and more than 8500 sources on the open data portal of the European Union 8 RDF has gained a lot of attention, and as a result an increasing number of data sets are now being represented with this language. From this popularity stemmed the need to efficiently store, query and reason over large amounts of As the demand for data and information management increases, there is also a critical need for maintaining the security of the data sources, applications, and information systems. Different fields of study have been introduced to design appropriate approaches able to provide security guarantees. These security fields involve authentication [Lamport 1981], access control [START_REF] Griffiths | [END_REF]], cryptography [Diffie 1976, Rivest 1978] and auditing [Agrawal 2004]. Following the evolution of these fields, database systems offer new security paradigms to cope with vulnerabilities induced by new features (e.g., distribution, heterogeneity, autonomy, reasoning).

The protection of resources against unauthorized accesses, is one of the main features of todays systems. One of the main security services needed to achieve data protection is access control. Access control ensures that a user can access only resources she/he is allowed to see. Historically, the first access control model was defined by [START_REF] Griffiths | [END_REF]] in the framework of the System R DBMS. In this model, the protected objects are tables and views, and the possible access modes that subjects can exercise on tables correspond to SQL operations that can be executed on tables. Later, other access control models have been proposed for different data models such as object-oriented DBMS [START_REF] Rabitti | [END_REF]] and XML [START_REF] Damiani | [END_REF]].

In this thesis, we focus on the security challenges that mainly arise in Linked Data context, particularly the selective disclosure of RDF data.

Our main objective is to encourage businesses and organizations worldwide to publish their RDF data into the linked data global space. Indeed, the published data may be sensitive, and consequently, data providers may avoid to release their information, unless they are certain that the desired access rights of different accessing entities are enforced properly, to their data, and that no sensitive data are revealed (by mistake). Hence the issue of securing RDF content and ensuring the selective disclosure of information to different classes of users is becoming all the more important.

An inspiring quote from Paul Terry who wrote in CTO Vision16 : To realize value from your data, you need to be able to share it among many stakeholders-internal lines of business, partners, researchers, and many others. But you also have a moral, ethical, and often legal, obligation to make sure that data is used responsibly. That means protecting individuals' privacy and assuring that their data is used only for legitimate purposes. As you gather more data from more parts of your organization, that gets very tricky very fast. [...] It quickly becomes clear that this is about more than simply checking a box for whether data is "secure". It's incredibly valuable to have all that data in one place where it can be analyzed, but you need to assure that different types of stakeholders can see only the information they legitimately need, and no more.

Problem statement

In this thesis, we are interested in RDF data disclosure and inference leakage problem. The problem of providing access controls to RDF data has attracted considerable attention of both the security and the database community in recent years. Our goal is to define an authorization policy to be integrated to RDF stores in order to control RDF data disclosure. Moreover, we must ensure that the disclosed data can not be used to infer confidential information. In this context, we are interested in the following issues :

Selective RDF data disclosure

Given the sensitive nature of information, different portions of RDF data may require different access rights with respect to the privileges of the requester. In this thesis, we are interested in selectively disclosing information based on the RDF content, who requests it and under what context. Most of nowadays RDF Stores offer protection at named graph level. For instance, such a feature has been introduced in 4store version 1.1.5 17 . Graph-based security is available in Virtuoso 18 or in Stardog version 3.1 19 as well. The issue with these models is that the access control policies are defined over named graphs which must be created with respect to policies. For instance if a policy states that the nurses have access to patient's records, then all triples related to the patient's records must be gathered into one named graph over which the policy is defined. Moreover, complex policies may lead to the creation of several named graphs. Having a large number of complex policies may lead the administrator to create several named graphs that may be difficult to manage. In addition, a redundancy problem arises because a triple may belong to several named graphs. Some RDF stores such as AllegroGraph 20 support triple pattern based access control 21 which allows the definition of simple authorizations such as deny or allow access to triples representing patients' records. However, more expressive policies can not be specified. For instance an authorization such as Deny access to patients' records if they have cancer cannot be specified.

Given the open nature of the web where the RDF data are published, the subject may not be known by the system prior to the submission of a query. Hence, the selective disclosure can not only rely on traditional identity based and role based access control policies. Attribute Based Access Control (ABAC) model gives more flexibility by defining authorizations on the basis of subject's and object's attributes. ABAC avoids the need for explicit authorizations to be directly assigned to individual subjects prior to a request to perform an operation on the object.

Inference leakage

The second issue is to ensure that sensitive information can not be inferred once the data have been disclosed to the user. This problem is known in the access control literature as the Inference problem [Farkas 2002] called in this manuscript the Inference leakage problem. According to the World Wide Web Consortium (W3C), inference on the Semantic Web using the Resource Description Framework (RDF) "improve the quality of data integration on the Web, by discovering new relationships, automati-17 http://4store.org/trac/wiki/GraphAccessControl 18 http://docs.openlinksw.com/virtuoso/rdfgraphsecurity.html 19 http://docs.stardog.com/# security 20 http://franz.com/agraph/allegrograph 21 http://franz.com/agraph/support/documentation/v4/ security.html#filters cally analyzing the content of the data". Inference rules are used to derive new triples from those explicitly asserted in an RDF store. In particular, a set of inference rules known as RDF Schema (RDFS) is standardized [START_REF] Hayes | [END_REF]]. Authorization models for RDF data have been proposed to control accesses to RDF data, both in the presence of inference rules [Reddivari 2005[START_REF] Lopes | [END_REF][START_REF] Papakonstantinou | [END_REF][START_REF] Jain | [END_REF] or not [Abel 2007, Flouris 2010, Rachapalli 2014]. However, the issue is that inference capabilities can be used by a malicious user to infer sensitive information from authorized ones.

To illustrate the inference leakage problem, suppose that RDF triples stating that someone has a cancer are labeled as confidential (e.g. triples similar to (?p ; rdf : type ; :Cancerous) with ?p denoting a person), while the ones stating that a person has a tumor are public (e.g., triples of the form (?p ; :hasTumor ; ?t)). If there exists a public triple stating that the domain of the : hasTumor predicate is : Cancerous (e.g. (: hasTumor ; rdfs : domain ; :Cancerous)) then, using the RDFS rule that relates the domain of a predicate to the type of its subjects, sensitive information can be inferred from the authorized triples. The situation is even worse when the deduction system is enriched with user-defined rules.

Enforcement and performance

Specific issues arise from the enforcement of the access control. The first issue is the impact of access control enforcement on the system's performance : we must ensure that the enforcement of the access control incurs a low overhead in the RDF store performance. The second issue regards the mechanisms needed to enforce the access control. The enforcement mechanism must be deployable in the RDF store with minimal additional mechanisms and ideally, with no alteration of its internal components

Related work study

A first study of the state of the art has led to the definition of the evaluation criteria in order to compare the related works in access control to RDF data, including the expressiveness of policy specification languages, conflict resolution generated by conflicting decisions and the verification of unauthorized inferences. The study has resulted in the determination of well treated criteria such as the supported actions, the expressiveness of objects and the protection of explicit and implicit triples. Other criteria have not been deeply considered, In Chapter 2 we introduce the Semantic Web and a recalling of the syntax and semantics of the RDF Data Model. We give an overview about SPARQL 1.1 RDF query language, and how it can be used to process RDF data. We define inference, in particular RDFS inferencing, which allows the deduction of new data from those explicitly defined. We give an overview of the most known access control models found in the literature, followed by the conflict resolution strategies used to resolve conflicts that stem from the use of negative authorizations. Next, we present the works that were proposed to control access to RDF data, and the criteria used to compare them. We finally present the criteria that have not been well considered, which are the basis of our proposals.

Contributions

We present in the following, the main contributions of this thesis depicted by Figure 1.2.

Access control model for RDF

We define in Chapter 3 the formal semantics of a triple-level access control model for RDF. The semantics are defined by means of positive (authorized) subgraph from the base graph, over which the user's query is evaluated. This makes the model independent from the query language. Our model supports negative authorizations to handle real-life exceptions. This leads to possible conflicts that may occur between authorizations. Conflict resolution strategies are used to resolve such conflicts by selecting the preferred authorizations to apply, with respect to some properties of the authorizations. Whereas most of the works hard-code their strategies, others define them as parameters that are fixed by the administrator during policy design. We propose a more liberal approach by defining our policy using an abstract conflict resolution function which is defined by the administrator. We illustrate the applicability of the authorization model by showing that usual conflict resolution strategies can be expressed in our framework. We show how to build classic conflict resolution strategies namely : Denials Take Precedence, Permissions Take Precedence. Moreover, we show how to build more elaborate strategies such as Most Specific Takes Precedence to handle exceptions.

Inference leakage problem and solution

To deal with the inference leakage problem, we propose in Chapter 4 an approach based on a static analysis. The idea is to detect, at the time of specifying the confidentiality policy, whether authorizations and inference rules interact in such a way they can lead to sensitive information disclosure. Several authorization models for RDF which consider inference use annotations to determine whether the inferred triples are accessible or not [Reddivari 2005[START_REF] Lopes | [END_REF][START_REF] Papakonstantinou | [END_REF]]. The problem is that these approaches do not guarantee that forbidden information cannot be inferred again, once the data have been disclosed. The inference leakage problem in the case of RDFS has been investigated by Jain and Farkas [START_REF] Jain | [END_REF]], but the base RDF graph kept in the RDF store is needed and conflict resolution strategies are hard-coded in their algorithm. We identify and formalize a consistency property that captures the inference leakage arising when inference rules and authorizations interact, as exemplified informally in this introduction. Intuitively, a policy is consistent w.r.t. a set of inference rules R if the authorized subgraph G + of a closed graph G is itself closed, that is, no new facts can be produced using R another time. This property ensures that confidential information can not be inferred from authorized information with respect to a set of inference rules. To solve the issue, we propose an algorithm that, given a policy P and a set of inference rules R, but without any prior knowledge of G, checks if the consistency property holds. The algorithm is proved correct and it is constructive: whenever the answer is positive, a set of counterexample graphs is computed. This answer can be used by the administrator to analyze and then solve the issue. We show how the counterexamples could be used by the administrator to fix the policy, or how to use them as integrity constraints that do not allow updates which could lead to inference leakage

Policy administration

The policies of the model proposed in Chapter 3 are defined without specifying the subject for which permissions are assigned. This allows to use any upstream access control model to map the users to their assigned permissions. We propose in Chapter 5 a high level access control language which permits the definition of global policies which are then compiled into subject specific policies enforced by our access control model. We have chosen to define our policies on the basis of the user attributes following the Attribute Based Access Control Approach (ABAC), where access to protected resources is based on users having specific attributes (eg. name, role, date of birth, address, phone number, etc.). This approach allows a much finer approach of access control combining not only user attributes, but other environmental information, such as location and time. Rather than just using the role of a user to decide whether or not to grant access to protected resource, ABAC combines multiple attributes to make a context-aware decision regarding individual requests for access. ABAC is implemented through XACML which is a declarative language to define policies which are structured as a tree of sub-policies. We define the syntax and semantics of a language inspired by XACML by defining the main components of the proposed solution and showing how the user's policy is created and enforced. Intuitively, a global policy can be represented in a Tree structure where the intermediate nodes represent policies, the leaves are authorizations and nodes edges are labeled with targets representing attribute based conditions. The latter are evaluated using key/value pairs representing attributes provided by subjects. The subject provides her/his attributes in a request which is evaluated over the global policy tree to determine her/his assigned authorizations. Based on these authorizations, the subject's query is evaluated over her/his positive subgraph returning the her/his accessible triples.

Policy enforcement

In Chapter 6, we propose an enforcement framework based on dataannotations for our access control model. We propose an approach where we annotate every triple of the base graph with a bitset representing its applicable authorizations. Similarly, users are assigned bitsets representing the authorizations applicable to them. We show the annotation process of the base graph, and how the user query is evaluated over the annotated graph, and we prove that our encoding is correct. We use the graph name position to store the bitset of applicable authorization of the triple. As todays RDF stores support named graphs [START_REF] Haslhofer | [END_REF]], no additional mechanisms are needed to enforce our model, in contrast to approaches that use specific extensions of RDF data model to store annotations. The annotation process is performed by transforming the authorizations into (CONSTRUCT) queries that are evaluated using the RDF store query engine. Once the base graph annotated, it is made available to the requesters. When a query is sent from a requester, her/his positive subgraph is computed by making logical and between the requester's bitset, and the triple's bitset. The result is used to determine the triple's that take part of the positive subgraph. The requester's query is then evaluated over her/his positive subgraph and the result is returned to the user. Finally we show the results of experiments of our solution implemented on a concrete RDF store. We show that our implementation incurs reasonable overhead at runtime (about +50%) with respect to the optimal solution which consists in materializing the user's accessible subgraph. In this chapter, we start by introducing the Semantic Web (aka Web of Data) and recalling the syntax and semantics of the RDF Data Model. We present an overview of the RDF query language SPARQL, and how it can be used to process RDF data. We present inference, in particular RDFS inferencing, a key feature of the Semantic Web, which allows the deduction of new data from those explicitly defined. We give an overview of the most known access control models found in the literature, followed by the conflict resolution strategies used to resolve conflicts that stem from the use of negative authorizations. We present the works that have been proposed to control access to RDF data, and the criteria used to compare them. We finally give the summary of our study by showing the criteria that have not been well considered, which are the basis of our proposals.

Semantic Web

Most of today's Web content is suitable for human consumption. Even Web contents that are generated automatically from databases are usually presented without the original structural information found in databases. The Semantic Web initiative consists in representing Web contents in a form that is more easily machine-processable. World Wide Web Consortium (W3C) is promoting the mobilization of semantic web technology. In their vision, semantic web is achieved with a layered stack solution (Figure 2.1). RDF(S) and OWL specifications have been suggested as mature recommendations.

Graph Data Model

Graph database models can be defined as those in which data structures for the schema and instances are modeled as graphs or generalizations of them, and data manipulation is expressed by graph-oriented operations and type constructors [START_REF] Angles | Survey of graph database models[END_REF]]. The graph data model used in the semantic web is RDF (Resource Description Framework ) [START_REF] Hayes | [END_REF]].

Resource Description Framework

RDF has been developed under the auspices of the W3C and has become the de facto standard for representing semantic relations between web resources which are uniquely identified by Universal Resource Identifiers (URIs) or Internationalized Resource Identifiers (IRIs) [START_REF] Cyganiak | RDF 1.1 concepts and abstract syntax[END_REF]]. URIs represent common global identifiers for resources across the Web. An IRI is an extension of a URI which allows the use of Unicode characters. The syntax and format of IRIs is very similar to the well-known uniform resource locators (URLs); e.g., http://example.com/hospital#alice. In fact, URLs are just special cases of IRIs. Another form of IRIs is a Uniform Resource Name (URN), which identifies something that is not associated to a Web resource but on which people on the Web want to write about such as books. To represent value data types such as numbers, booleans and strings, RDF uses Literals. In RDF, a resource which do not have an IRI can be identified using Blank nodes. Blank nodes are used to represent these unknown resources, and also used when the relationship between a subject node and an object node is n-ary (as is the case with collections). The purpose of RDF is to promote encoding, exchanging and reusage of structured metadata. RDF allows to decompose knowledge into small portions called triples or statements. Triples have the form "(subject ; predicate ; object)" built from pairwise disjoint countably infinite sets I, B, and L for IRIs, blank nodes, and literals respectively. The subject represents the resource for which information is stored and is identified by an IRI. The predicate is a property or a characteristic of the subject and is identified by an IRI. The object is the value of the property and is represented by an IRI of another resource or a literal.

For ease of notation, in RDF, one may define a prefix to represent a namespace, such as rdf : type where rdf represents the namespace http: //www.w3.org/1999/02/22-rdf-syntax-ns Note 2.1.1 In this manuscript, we explicitly write rdf and rdfs when the term is from the RDF or the RDFS standard vocabulary. However, we do not prefix the other terms for the sake of simplicity.

For instance the triple (: alice ; :hasTumor ; :breastTumor) states that alice has a breast tumor. A collection of RDF triples is called an RDF Graph and can be intuitively understood as a directed labeled graph where resources represent the nodes and the predicates the arcs as shown in Figure 2 In this manuscript, we reuse the formal definitions and notation used by Pérez and Gutierrez [START_REF] Pérez | [END_REF]]. Throughout the manuscript, P(E) denotes the finite powerset of a set E and F ⊆ E denotes a finite subset F.

RDF Semantics

The W3C document [START_REF] Hayes | [END_REF]] defines a modeltheoretic semantics for RDF 1.1. Model-theoretic semantics for a language assumes that the language refers to a world, and describes the minimal conditions that a world must satisfy in order to assign an appropriate meaning for every expression in the language. A particular world is called an interpretation. An RDF interpretation is a mapping from IRIs and literals into a set, together with some constraints upon the set and the mapping.

Definition 2.1.4 (Simple interpretation) A simple interpretation I of a given vocabulary V consists of:

1. A non-empty set IR of resources, called the domain or universe of I.

2. A set IP, called the set of properties of I.

3. IEXT : IP → P(IR × IR) a mapping from properties into set of pairs in IR.

4. IS : V → (IR ∪ IP) a mapping from IRIs in V into the union of sets IR and IP.

A partial mapping IL from literals into IR

Given a triple (s, p, o), Simple interpretation has no particular extra conditions on the vocabulary. Additional extensions of simple interpretation have been introduced, such as RDF(S)-Interpretation which assign special meanings to the symbols in particular vocabularies (RDF(S)). For more details, we refer the reader to [START_REF] Hayes | [END_REF]].

I((s, p, o)) = true if s, p, o ∈ V , IS (

SPARQL

We just presented RDF as the data model of the Semantic Web. In general, a data model comes equipped with a language to support queries over some data set. The emergence of RDF recommendation has spun up several RDF query languages, such as SPARQL [START_REF] Harris | Steve Harris and Andy Seaborne[END_REF]], RQL [Lassner 2002],

SeRQL [Broekstra 2003], TRIPLE [Sintek 2002], RDQL [START_REF] Seaborne | RDQL-a query language for RDF[END_REF]] and N3 [Berners- [START_REF] Berners-Lee | [END_REF]]. An RDF Query Language is a formal language used for querying RDF Triples from an RDF Store also called Triple Store. An RDF store is a database specially designed for storing an retrieving RDF triples. SPARQL (SPARQL Protocol and RDF Query Language) is a W3C recommendation and has established itself as the de facto language for querying RDF data. SPARQL borrowed part of its syntax from the popular and widely adopted Structured Query Language (SQL). The main mechanism for computing query results in SPARQL is subgraph matching: RDF triples in both the queried RDF data and the query patterns are interpreted as nodes and edges of directed graphs, and the resulting query graph is matched to the data graph using variables. The SPARQL building blocks are graph patterns which are built from pairwise disjoint countably infinite sets I, V and L for IRIs, variables, and literals respectively. In this manuscript, we do not explicitly use blank nodes which are replaced by variables. Blank nodes of RDF are semantically equivalent to existentially quantified variables [START_REF] Polleres | From SPARQL to Rules (and Back)[END_REF]]. Not to distinguish between blank nodes and variables significantly reduces the overhead of formal definitions but it does not change the expressiveness of the framework. Moreover, we use an extended version of RDF [START_REF] Ter | [END_REF] which allows variables in property position. When graph patterns are considered as instances stored in an RDF store, we simply call them graphs.

The evaluation of a graph pattern B on another graph pattern G is given by mapping the variables of B to the terms of G such that the structure of B is preserved. First, we define the substitution mappings as usual. Then, we define the evaluation of B on G as the set of substitutions that embed B into G.

Definition 2.1.7 (Substitution Mappings) A substitution (mapping) η is a partial function η : V → T. The domain of η, dom(η), is the subset of V where η is defined. We overload notation and also write η for the partial function η : T → T that extends η with the identity on terms. Given two substitutions η 1 and η 2 , we write η = η 1 η 2 for the substitution η : ?v → η 2 (η 1 (?v)) when defined.

B G = {η : V → T | dom(η) = var(B) ∧ (B)η ⊆ G}
Example 2.1.9 shows the evaluation of a triple pattern.

Example 2.1.9 Let B be defined as B = {(?p ; rdf : type ; :Patient)}. B is a triple pattern with a variable in the subject position which will be used to match all triples of type Patient. The evaluation of B on the example graph G 0 of Figure 2.2 is B G 0 = {η}, where η is defined as η : ?p → : alice. Formally, the definition of BGP evaluation captures the semantics of SPARQL restricted to the conjunctive fragment of SELECT queries that do not use FILTER, OPT and UNION operators (see [START_REF] Pérez | [END_REF]] for further details). Another key concept of the Semantic Web is named graphs in which a set of RDF triples is identified using an IRI. This allows to represent metainformation about RDF data such as provenance information and context. In order to handle named graphs, SPARQL defines the concept of dataset. A dataset is a set composed of a distinguished graph called the default graph and pairs comprising an IRI and an RDF graph constituting named graphs. Definition 2.1.11 (RDF dataset) An RDF dataset is a set :

D = {G 0 , u 1 , G 1 , . . . , u n , G n }
where G i ∈ BGP, u i ∈ I, and n ≥ 0. In the dataset, G 0 is the default graph, and the pairs u i , G i are named graphs, with u i the name of G i .

SPARQL Query result forms SPARQL has four query result forms :

• SELECT returns all, or a subset of, the variables bound in a query pattern match

• CONSTRUCT returns an RDF graph constructed by substituting variables in a set of the BGP defined as template.

• DESCRIBE returns an RDF graph that describes the resources

• ASK returns a boolean indicating whether a query pattern matches or not an instance in the queried RDF graph.

Inference

One of the main features of the Semantic Web is the ability to do inferencing. Inference is the act of deriving new facts from known premises. A graph may contain implicit triples even though they are not explicitly present in it. Inference rules are used to add triples to a graph when it contains triples conforming to a graph pattern. Thus, inference rules turn an RDF store into a deductive database similar to positive Datalog that extends traditional (non-deductive) relational databases.

An inference rule consists of a head and a body. The head is a triple pattern which represents the rule conclusion. The body is a BGP which represents the rule premises.

Definition 2.1.12 (Inference Rule) An inference rule r is a formal expression of the form (tp ← tp 1 , . . . , tp k ) where tp, tp 0 , . . . , tp k ∈ TP that is subjected to the condition var(tp) ⊆ var({tp 0 , . . . , tp k }). The sets of inference rules are denoted by R. The following notation is also used to represent inference rules: tp 1 , . . . , tp k tp For a rule (tp ← tp 1 , . . . , tp k ), the condition var(tp) ⊆ var({tp 0 , . . . , tp k }) ensures that it does not introduce fresh uninstantiated variables when applied to a graph. We define an operational semantics for the rules, inspired by the fixpoint semantics of Datalog. It is known that the closure of a finite graph is finite and the operator is increasing, monotonic and idempotent [Abiteboul 1995, Chap. 12]. Definition 2.1.13 (Rule Semantics, Closure) Given a graph pattern G ∈ BGP and an inference rule r = (tp

← tp 1 , . . . , tp k ), the set of triples (imme- diately) deduced from G by r is φ r (G) = {(tp)σ | σ ∈ {tp 1 , . . . , tp k } G }. We extend the operator φ(G) to sets of inference rules R, φ R (G) = r∈R φ r (G).
Given a set of inference rules R, let (G i ) i∈N be the infinite sequence of basic graph patterns defined by G 0 = G and for any

i ∈ N, G i+1 = G i ∪ φ R (G i ). The closure of G w.r.t. R is Cl R (G) = i∈N G i . We write Cl(G) when R is clear from the context. We say that a graph is closed when Cl R (G) = G
The above closure takes a graph and a set of inference rules and iteratively applies the rules over the union of the original graph and the inferences until a fixpoint. The following lemma shows that the closure is finite.

Lemma 2.1.14 (Finite Closure) Let Cl R (G) = i∈N G i the closure of a graph G according to a set of rules R, there exists some k ∈ N such that for all l ∈ N .l ≥ k ⇒ G l = G k .
Proof For the sake of the contradiction, assume that for all i ∈ N,

G i G i+1 = G i ∪ φ R (G i ). It follows that there exists some x i ∈ φ R (G i ) not in G i obtained from some r i ∈ R and some σ i ∈ {tp i 1 , . . . , tp i k } G with {tp i 1 , .
. . , tp i k } the body of r i . Repeating this construction for each i, we obtain a finite sequence of triples x i with associated mapping σ i . However, the condition dom(η) = var(B) ∧ η(B) ⊆ G in Definition 2.1.8 ensures that only a finite number of mappings σ i can be obtained: it is bounded by T V where V is the total number of variables that appears in the heads of the rules from R and T is number of terms of G. This contradicts the hypothesis. The following is an example of the application of an inference rule on a given graph. RDF provides a way to express simple statements about resources, using named properties and values. However, RDF user communities also need a way to define the vocabularies (terms) they intend to use in those statements, specifically to indicate that they are describing specific kinds or classes of resources, and will use specific properties in describing those resources. RDFS is the schema language for RDF, and provides a way to specify the vocabulary (also known as ontology) that will be used in an RDF graph. It allows to define how individuals are related to one another, the properties we use to define our individuals and how they are related to other sets of individuals and to one another. In RDFS, a class corresponds to a group of resources RDFS allows reasoning over RDF triples using a set of defined inference rules (aka entailment rules). Table 2.1 shows a subset of RDFS inference rules used in our examples. We refer the reader to [START_REF] Hayes | [END_REF]] for the rest of the rules.

RDom states that if there exists a triple with a given property, then its subject is an instance of this property domain. RRan is similar to RDom and generates the fact that the triple object is an instance of the property range. RSc 1 and RSp 1 define the subclass and subproperty transitivity respectively. RSc 2 defines the type propagation, in other words if a resource is an instance of a given class, then it is also an instance of the parents of this class. RSp 2 defines the property propagation, which mean that if two resources are related with a property then they are related with the parents of this property.

Access control

Access control refers to the process of regulating access to protected data based on pre-defined security policies. The advantage of using policies is that the system behavior can be managed without the need of reimplementation. The development of an access control system requires the definition of the regulations according to which access is to be controlled and their implementation as functions executable by a computer system. The development process is usually carried out with a multi-phase approach based on the following concepts [Samarati 2001]:

• Security policy: it describes the most abstract view of the system. At this level access control rules are defined. The requirements of the system are described in order to comply with some specification (e.g., laws, regulations). This description does not provide any method on how it should be enforced.

• Security model: it formalizes the rules defined in the security policy and describes the way they should work. This level aims at providing a framework where proof of properties could be accomplished.

• Security mechanism: it describes the low level methods that are used to enforce the rules formalized at the security model level.

Access control models

The most well-known access control models in the literature are : Identity Based Access Control (IBAC) where the access to objects is based on the identity of the user, Mandatory Access Control (MAC) where access is based on security levels assigned to both users and resources and Role Based Access Control (RBAC) where authorizations are granted to roles instead of users.

Other more flexible models have been introduced such as Attribute Based Access Control [Wang 2004] and Organization Based Access Control (Or-BAC) [START_REF] Cuppens | Modelling Contexts in the Or-BAC Model[END_REF]].

In the following we give more details on IBAC, MAC, RBAC and ABAC models.

Identity-Based Access Control (IBAC)

In the IBAC model, the access to objects is based solely on the identity of the subject and the rights specified for that identity on each object. In this model, privileges can be passed from a subject to another, where an administrative policy regulates grants and revocations of the privileges. The access control matrix provides a basic framework for describing IBAC. It was first proposed by Lampson [Lampson 1974] for resource protection within operation systems. In this model, authorizations are represented as a matrix |S| × |O| where |S| is the set of subjects and |O| the set of objects. The matrix is arranged as a two-dimensional array where each row is labeled by a subject and each column labeled by an object. Each entry of the matrix specifies the actions of the subject on the object. For instance, a matrix entry for s and o which contains read, grants to s the right to read o. The drawback of the access control matrix is that it will be enormous in size if used in large systems and most of its cells are likely to be empty. In practical systems, there exists multiple ways to implement the access control matrix. A popular approach is using ACLs (Access Control List). An ACL is associated with an object and consists of a number of entries defining the rights assigned to each subject on that object. Another way to implement the access control matrix is the C-List (Capability list) where each subject is associated with a list of objects and the rights that the subject has on them.

Mandatory Access Control (MAC)

A different approach of controlling access to resources is the MAC model in which access to resources is controlled based on the perspective attributes of the subject and object. Such approach was motivated by the problem of Trojan Horses which the DAC model suffers of. Unlike DAC where the owner defines the access rights, in MAC accesses are centrally controlled. In this model, mandatory policies govern access on the basis of subjects and objects classifications. Each user and each object is assigned a security level. The security level associated with the object reflects the sensitivity of the information it contains. The security level associated with a user reflects the user's clearance. The MAC model is usually associated with the Bell-LaPadula Model (BLP) [START_REF] Bell | Secure computer systems: Mathematical foundations[END_REF]]. In the BLP model clearance and sensitivity levels take values from the set of access classes. Definition 2.2.1 (Access class) An access class consists of two components : a security level and a category set. The security level is an element of a totally ordered set of levels. The category set is a subset of an unordered set specific to the application area.

The set of the access classes is partially ordered according to relation called dominance relation.

Definition 2.2.2 (Dominance relation) Let L and C be the set of security levels and categories respectively. Let c

i = (L i , SC i ) and c k = (L k , SC k ), with L i , L k ∈ L and SC i , SC k ⊆ C,
be two access classes. We say that c i dominates c k denoted by c i ≥ c k if the following holds :

• L i ≥ L k
the security level of c i is greater than or equal to the security level of c k ;

• SC i ⊇ SC k the category set of c i includes the category set of c k .

Access classes with the dominance relationship between them therefore form a lattice [Denning 1976]. In the context of flow control, the BLP model follows two principles that are required to hold.

• no read-up : The subject clearance must dominate the object sensitivity level, in other words a subject s with an access class c s can read an object with an access class

c o if c s ≥ c o .
• no write-down : The subject clearance must be dominated by the object sensitivity level, i.e. a subject s with an access class c s can write an object with an access class

c o if c o ≥ c s .
Satisfaction of these principles prevents information flows from high levels to low levels.

Role-Based Access Control (RBAC)

The principle purpose of RBAC is to specify and enforce enterprise-specific security policies in a way that maps naturally to an organization's structure. Moreover, RBAC facilitates security administration by granting authorizations to roles instead of individual users. Role based policies regulate users' access to the information on the basis of the activities the users execute in the system. A role can be defined as a set of actions and responsibilities associated with a particular work activity. Access authorizations on objects are specified for roles and a user playing a role is allowed to execute all accesses assigned to this role. A user can have multiple roles and similarly a role can be granted to different users. Some RBAC approaches allow users to exercise Figure 2.6: RBAC architecture multiple roles at the same time, in addition other approaches limit the user to use one role only at a time. The concept of grouping privileges was initially proposed by [Baldwin 1990], and different types of RBAC models have been proposed in the literature [START_REF] Ferraiolo | [END_REF]], [START_REF] Sandhu | [END_REF]].

Figure 2.6 illustrates the basic concepts of standard RBAC which is defined by a set of users U , a set of roles R and a set of permissions P . A permission is an approval of a particular mode of access to one or more objects in the system. Users are associated with roles using relation UA. Similarly, permissions are associated with roles by relation P A. Users activate sessions to interact with RBAC system. A session is a mapping of one user to possibly many activated roles. The activated roles determine which permissions are available to the user at a given time during the session. Administration has been further reduced by the use of roles hierarchy to allow the propagation of access control privileges. Role hierarchies are a natural means for structuring roles to reflect an organization's lines of authority and responsibility [Sandhu 2000]. The hierarchy is defined as a partial order relation RH on R. A role inherits all permissions of less-powerful (junior) roles which avoids the need to assign these permissions explicitly. This reduces the administration overhead, but on the other hand increases the enforcement overhead because the permissions of the junior roles need to be considered in the decision computation. In this case a user is authorized for permission p if there exist roles r and r such that (u, r) ∈ UA, r RH r and (p, r ) ∈ P A.

Attribute Based Access Control (ABAC)

Whereas traditional access control systems were based on the identity of the requester or through predefined attribute types such as roles or groups assigned to that requester, in open environments such as the Internet, this approach is not effective because often the requester and the resource belong to It has also been noted that the requester qualifiers of identity, groups, and roles are often insufficient in the expression of real-world access control policies. An alternative is to grant or deny user requests based on arbitrary attributes of the user and arbitrary attributes of the object, and environment conditions that may be globally recognized and more relanevant to the policies at hand. This approach is often referred to as ABAC. The main advantage of ABAC is enabling object owners or administrators to apply access control policy without prior knowledge of the specific subject and for an unlimited number of subjects that might require access. One example of an access control framework that is consistent with ABAC is the Extensible Access Control Markup Language (XACML) [START_REF] Ramli | [END_REF]]. XACML architecture consists of several logical components (see Figure 2.7).

First of all, a reference monitor concept is used to intercept access requests. This component is called a Policy Enforcement Point (PEP). Access requests are transmitted from the PEP to a Policy Decision Point (PDP) for retrieval and evaluation of applicable policies. Policies are specified and stored in Policy Administration Point (PAP). The PDP gets the attributes of subjects, objects, and the environment from the Policy Information Points (PIP). The XACML policy language is based on three .9: XACML policy example of single Rules which have a Condition, an Effect, and a Target. To find the relevant policy for an access control request, every PolicySet, Policy, and rule has a Target, which is evaluated at the access request time. A Target consists in a specification of sets of subjects, objects, operations, and environment using their respective attributes which can be evaluated with match functions. Conditions can be used beyond the Target to further specify the applicability of a Rule using predicates, while Effects denote the result of a Rule, e.g. permit or deny.

Example 2.2.4 Figure 2.8 shows an example of a XACML request, from the subject alice who is a nurse, requesting access to record1. Figure 2.9 is an example of a policy targeting record1. The policy contains one rule which permits access to nurses. Hence alice request will return permit.

When the relevant Policies and Rules are found, they are evaluated independently of each other; contradicting evaluation results can be resolved using policy combining algorithms which apply conflict resolution strategies. For instance, the policy of Figure 2.9 resolves conflicts with deny-overrides algorithm. In the next section we describe the conflict resolution and we give details about the strategies known in the literature.

Conflict resolution

Negative authorizations have been introduced by [START_REF] Bertino | [END_REF]] to extend the System R access control model by the possibility of specifying explicit denials. This feature enables adding of exceptions in existing permissions. An access control model that supports positive and negative authorizations has a sign (effect) field in permission tuple.

Definition 2.2.5 (Authorization tuple) From a conceptual point of view, an authorization is defined by the tuple subject; sign; access right; object . The sign is either positive or negative, and determines whether the subject can perform the access right on the object.

Traditionally, positive and negative authorizations have been used in mutual exclusion using a default policy that determines the sign of a permission corresponding to two classical approaches namely: [Samarati 2001]:

• Closed Policy: denies all accesses, unless a corresponding positive authorization permits it.

• Open Policy: a policy where accesses are by default allowed, and denied if there exists an explicit negative authorization.

The open policy has usually found application in those scenarios where the need for protection is not strong and by default access is to be granted. The closed policy is the mostly adopted where denying access by default ensures better protection. In the recent access control models, negative and positive authorizations are combined to handle exceptions, giving rise to other issues, namely:

• Completeness : how to treat objects which have no defined authorization?

• Consistency : how to treat objects which are both allowed and denied at the same time?

In order to achieve completeness, one has only to define the above-cited default policy. Consistency is more complex and it is achieved by defining a Conflict Resolution Strategy. Conflict resolution consists in choosing one of the conflicting authorizations to make a final access decision. Below are examples of known conflict resolution strategies in the access control literature.

• Denials Take Precedence (DTP): in this case, negative authorizations are always adopted when a conflict occurs. In other words the principle says that if we have one reason to authorize an access and another to deny it then we deny it.

• Permissions Take Precedence (PTP): in this case, positive authorizations are always adopted when a conflict occurs. In other words the principle says that if we have one reason to authorize an access and another to deny it then we authorize it.

• First Applicable (FA):in this case, the first applicable authorization in order of presentation is picked.

• Most Specific Takes Precedence (MSTP): in this case it is supposed that subjects or objects are hierarchically related. The most specific authorization w.r.t. the hierarchical relation should be the one that prevails.

A strategy may not achieve consistency such as with MSTP where a partial order is supposed to exist between authorizations. The conflict may still remain if the conflicting authorizations are incomparable. Since conflict resolution strategies are not mutually exclusive, one can decide to combine strategies together to achieve a more effective conflict resolution. Thus a strategy chain can be constructed to solve the issue. For instance, one can decide to try solving conflicts with the MSTP first, and apply the DTP principle on the remaining conflicts (i.e. conflicting authorizations that are not hierarchically related).

Access control for RDF data

The importance of confidentiality problems have been recognized for long. As such, access control models for different data models data have been proposed. RDF graphs can be written in a standard XML format, but there can be many different syntactical expressions that denote the same graph. Thus access control models for XML are quite difficult to transpose, if feasible, when applied to RDF graphs [START_REF] Jain | [END_REF]]. The Datalog model extends the relational one with deductive rules, thus one may devise a transformation that encodes graphs and rules into a Datalog program that uses a unique 3ary relation symbol for triples [START_REF] Polleres | From SPARQL to Rules (and Back)[END_REF]], and then rely on access control mechanisms for deductive databases, such as the one by Barker [Barker 2002]. Unfortunately, it seems that problems that arise when dealing with RDF data have not received much attention from the database community. We argue this because RDF is thought to be openly used between independent web sources, with shared or even standardized inference rules. In contrast, the Datalog model is more centralized, with rules and data under the control of a single authority. Several access control models related to RDF data have been proposed:

• Abel et al. [Abel 2007] propose a query rewriting mechanism to enforce authorizations. Their framework evaluates the applicable policies and expands the query depending on the result of the evaluation. The modified query is then sent to the RDF store which executes it like a usual RDF query. The authors used a specific language to define their policies.

• Flouris et al. [Flouris 2010] propose an annotation based access control language with its formal semantics for fine-grained authorizations on RDF data. In their proposal, authors propose to enforce their policy.

The triples are specifically annotated as accessible or not accessible using access control permissions.

• Costabello et al. [START_REF] Costabello | [END_REF]] propose a context-aware access control model. The authors present an ontology based on existing vocabularies and relies on SPARQL ASK queries to determine whether the requester has the necessary attributes to access the resource. They use context information to rewrite the user SPARQL query which is executed over the accessible named graphs only.

• Reddivari et al. [Reddivari 2005] propose an access control language for RDF stores that considers update operations. They use meta-rules to define conflict resolution strategies and default policies. They propose a query-time approach, where each triple in the user query result is checked whether it is accessible or not.

• Lopes et al. [START_REF] Lopes | [END_REF]] propose an annotation approach using an extended version of RDF called Annotated RDF [Udrea 2010]. They propose an access control annotation domain where each triple is annotated with a label and labels are propagated through inference rules.

The annotated triples are queried using an extended SPARQL language AnQL [START_REF] Lopes | [END_REF]].

• Papakonstantinou et al. [START_REF] Papakonstantinou | [END_REF]] propose a flexible model that defines the access label of a triple as an algebraic expression. Their model assigns abstract labels to RDF triples and computes the access decision using abstract operators that encode inference and propagation. Their main contribution is the efficient handling of updates by easy determination of the labels that are affected by these updates. When a triple is assigned different tokens, they use a conflict resolution operator which returns one concrete token that represents the final decision.

• Jain et al. [START_REF] Jain | [END_REF]] propose a label-based model to control access to RDF data. Security labels are assigned to graph patterns. The patterns are mapped to the triples to determine their security classifications.

They propose an algorithm that detects unauthorized inferences where higher security triples may be inferred from lower security triples.

Comparison of related works

In order to study the works related to the domain of controlling access to RDF data, we defined a set of comparison criteria. The study summary is shown in Table 2.2. In the following, we give the details about the criteria and the results of the study.

Authorization object An important aspect of access control models is their granularity with respect to the protected objects. Most of the works define authorizations over graph patterns to ease administration. [START_REF] Jain | [END_REF]] and [Reddivari 2005] define their authorizations over simple Triple Patterns which does not allow the specification of expressive policies. For instance an authorization such as Deny access to patients records if they have cancer cannot be specified. [Flouris 2010], [Abel 2007] and [START_REF] Papakonstantinou | [END_REF]] models are more expressive by using BGPs in their authorizations. [START_REF] Costabello | [END_REF]] authorizations are coarse-grained as they are defined over Named Graphs.

Triples protection

The purpose of this part of study is to check whether the proposed models consider the implicit triples or only explicit ones. As the semantics of an RDF graph are given by its closure, it is important for an access control model to take into account the implicit knowledge held by

• • • - • BGP • • - • Named Graph • - Triples protection Explicit • • • • • • • Implicit • • • • Considered rules RDFS • • • • User defined • Inference leakage detection • Default policy Open • • - - • Closed • • • • - - • Conflict resolution PTP • • • • DTP • • • • • • Language semantics Syntax • • • • • • Semantics • • • • • Subject specification Not specified • • • Attributes • • • • Actions Read • • • • • CRUD • • Query language SPARQL • • • • • • SeRQL • • • RDQL • • Enforcement approach pre-processing • • post-processing • annotation-based • • • • this graph.
In the Semantic Web context, the policy authorizations deny or allow access to triples whether they are implicit or not. In [Reddivari 2005] model, the implicit triples are checked at query time. Inference is computed during every query evaluation, and if one of the triples in the query result could be inferred from a denied triple, then it is not added to the result.

In the [START_REF] Jain | [END_REF]] label-based model the implicit triples are automatically labeled on the basis of the labels assigned to the triples used for inference. [START_REF] Lopes | [END_REF]] propose an approach inspired from provenance where each triple is annotated with a label and labels are propagated through inference rules to the implicit triples. [START_REF] Papakonstantinou | [END_REF]] propose a flexible model that defines the access label of a triple as an algebraic expression (abstract tokens).

The labels are propagated to the implicit triples through the inference rules. [Flouris 2010], [Abel 2007] and [START_REF] Costabello | [END_REF]] consider explicit triples only.

Considered inference rules

In this part of study, we examined the proposed models with respect to the supported inference rules. All the analyzed works that consider inference, support the RDFS rules only except [START_REF] Lopes | [END_REF]], who extend inference rules with labels in order to propagate them to implicit triples. Their model allows to specify a custom rules in order to provide application specific inferencing.

Inference leakage detection

As specified earlier, the inference leakage problem arises when denied triples are inferred from the accessible ones. [START_REF] Jain | [END_REF]] was the only work that considered the inference leakage problem.

They proposed an algorithm that detects unauthorized inferences by checking if triples with high security label, may be inferred from lower security triples.

Default policy As described in Section 2.2.2, a Default Policy is used to achieve completeness of the access control model. The Default Policy in the models proposed by [START_REF] Jain | [END_REF]] and [Abel 2007] is hard-coded, whereas in the [Reddivari 2005], [Flouris 2010] and [START_REF] Papakonstantinou | [END_REF]] models, it can be specified by administrators. [START_REF] Costabello | [END_REF]] and [START_REF] Lopes | [END_REF]] do not mention how they treat the triples without defined authorizations.

Conflict resolution

Conflict resolution strategies allow us to remove inconsistencies that may occur when multiple authorizations with different effects are applicable to the same triples. In the model of [START_REF] Jain | [END_REF]] a partial order is defined between security labels, and when more than one pattern maps to the same triple, the most restrictive or the lowest upper bound takes precedence. Unfortunately, their conflict resolution is hard-coded. [START_REF] Costabello | [END_REF]] and [START_REF] Lopes | [END_REF]] resolve conflicts by hard-coding the DTP strategy, whereas [Reddivari 2005] and [Flouris 2010] models allow the specification of PTP or DTP strategies only. [START_REF] Papakonstantinou | [END_REF] define the strategies at an abstract level which is mapped to concrete strategies such as DTP or PTP.

Language semantics Access control models use policy languages to define which objects are accessible and which are not. Only [START_REF] Jain | [END_REF]], [START_REF] Costabello | [END_REF]] and [Flouris 2010] gave the formal semantics of their language.

Subject specification Information about the subject is used by the access control system to determine its accessible objects. It can be based on simple credentials such as user name and password, or on context information and attributes. [START_REF] Costabello | [END_REF]], [Abel 2007], [Reddivari 2005] and [START_REF] Lopes | [END_REF]] use attribute-based approach to determine the accessible triples of the requester, whereas [START_REF] Papakonstantinou | [END_REF]] and [START_REF] Jain | [END_REF]], [Flouris 2010] did not consider subject specification.

Actions

The purpose of access control mechanisms is to check whether or not the subject has the authorization to perform the action on the data. The actions that can be performed on RDF data are Create, Read, Update and Delete (CRUD). Since version 1.1, updates are supported in SPARQL by the use of keywords : insert, modify and delete. The model proposed by [Reddivari 2005] supports RDF updates. They consider insertion by defining the three actions, namely, insert for adding a triple, insertModel for adding an implicit triple and insertSet for adding a set of triples. Regarding triples deletion, they defined three actions, namely remove for removing a triple, removeModel for removing an implicit triple and removeSet for removing a set of triples. [START_REF] Costabello | [END_REF]] also consider RDF updates using SPARQL 1.1 update language.

Query language

In this part of study we examined the different works with respect to the supported query languages. [START_REF] Lopes | [END_REF]] demonstrate how AnQL [START_REF] Lopes | [END_REF]] an extension of the SPARQL query language can be used to enforce access control, by rewriting using the requesters credentials to rewrite a SPARQL query to an AnQL query. [START_REF] Costabello | [END_REF]] express access conditions as SPARQL ASK queries in order to determine the authorized named graphs of the user querying the SPARQL endpoint. Besides SPARQL, [Flouris 2010] and [Abel 2007] support SeRQL query language whereas [Reddivari 2005] supports RDQL only.

Enforcement approach

In this part of study, we examined the different works with respect to the used enforcement approach. The latter can be pre-processing, post-processing, or annotation based.

• The pre-processing approaches enforce the policy before evaluating the query. For instance, the query rewriting technique consists in reformulating the user query using the access control policy. The new reformulated query is then evaluated over the original data source returning the accessible data only. This technique was used by [START_REF] Costabello | [END_REF]] and [Abel 2007] where the user query is rewritten with respect to the policy, and then evaluating the expanded query on the original dataset.

• In the post-processing approaches, the query is evaluated over the original data source. The result of the query is then filtered using the access control policy to return the accessible data. [Reddivari 2005] use a post-processing approach by evaluating the query over the original graph, filtering the triples in the query result and then returning the authorized triples to the requester.

• The rest of the works use annotation approach to enforce their models. In this case, every triple is annotated with access control information. During query evaluation, only the triples annotated with a permit access are returned to the user. In the label-based model proposed by [START_REF] Jain | [END_REF]], each triple is annotated with a label that represents its security classification. [Flouris 2010] annotate each triple with a boolean stating whether it is accessible or not. [START_REF] Lopes | [END_REF]] annotate the triples with non-recursive Datalog with negation programs which evaluation decision defines whether the triple is accessible or not. [START_REF] Papakonstantinou | [END_REF]] annotate the triples with abstract labels that encode inference and propagation of labels along the RDFS inference rules. To evaluate the label, each application provides its own concrete policy and semantics which allows the application to decide whether a triple is accessible or not.

Study summary

Regarding the protection of implicit triples, we mentioned that the propagation techniques assign automatically an accessibility label to the implicit triples on the basis of the triples used to infer them. Hence if one of the triples used for inference is denied, then the inferred triple is also denied even if it is explicitly authorized. This goes against the intuition that implicit triples are part of the knowledge held by the graph, hence they must be regarded as the explicit triples and not depend on the triples used to infer them. We illustrate with the following example.

Example

} (G 0 ) = G 0 ∪ {it 1 , it 3 }.
With the propagation approaches which consider inference [START_REF] Lopes | [END_REF][START_REF] Papakonstantinou | [END_REF]], the triple it 3 =(: alice ; rdf : type ; :Patient)} will be denied since it is inferred from denied triples (et 4 ). Hence the fact that alice is a patient will not be returned in the result even though the policy clearly allows access to it.

Another problem which the propagation techniques suffer from, is the inference leakage. In fact, even some implicit triples are labeled as denied by the policy, they could be inferred from triples labeled as accessible. To illustrate, consider the following example.

Example 2.4.2 We want to protect the graph G 0 of Figure 2.2 in presence of RDom inference rule, using the policy P ={allow access to triples having : breastTumor property, deny access to all resources which are instance of : Cancerous}. As the closure of the graph Cl {RDom} (G 0 ) = G 0 ∪ {it 1 }, there is one implicit triple i.e. it 1 . With the propagation techniques which consider inference [START_REF] Lopes | [END_REF][START_REF] Papakonstantinou | [END_REF][START_REF] Jain | [END_REF], it 1 will be assigned two labels, a deny label from the policy and a permit label inherited from the premises et 1 and et 4 . After resolving conflicts, it 1 will be denied and will not be returned to the requester, whereas et 1 and et 4 will be. Using a local reasoner, the requester could apply RDom on et 1 and et 4 to infer it 1 , hence an information leakage through inference. Note that even [Reddivari 2005] query-time approach suffer from the inference leakage problem.

The propagation approaches that consider the inference leakage problem such as [START_REF] Jain | [END_REF]], propose solutions after the labeling operation. In fact, they check the labeled graph to detect information leakage.

Regarding the conflict resolution, it is clear that different approaches can be taken to deal with positive and negative authorizations. Hard-coding the conflict resolution strategy makes the access control model less expressive. Moreover, even giving the choice to the administrator over pre-defined strategies would not make the model more expressive. Indeed, there are always situations where the pre-defined strategies do not fit.

As regards the supported query languages, the approaches that are based on query rewriting techniques support one or a limited number of languages.

Concerning policy enforcement, the pre-processing approaches such as query rewriting, are tied to the used query language. Changing the query language would lead to an update of the policy enforcer. Furthermore, the execution of a the reformulated query can be computationally expensive depending on the number of triple patterns in the query and size of the triple store. For instance, [Abel 2007], rewrite SeRQL queries using path expressions found in the body of the user's applicable policies, combined with "OR" keyword. A query with a triple pattern ?s ?p ?o will be reformulated to a query that may be computationally expensive since it combines all the possible policies which leads to a long path expression. Moreover, not all the user queries can be handled. More complex queries such as path queries are not supported. In the post-processing approaches, policies conditions are usually not based on the data content but on the subject attributes [Reddivari 2005]. The query is evaluated on the RDF store, and the policies are checked afterward on the result triples. The query answer time may be considerably too large. As an example, suppose an unauthorized user submits a query asking for all available triples in the store. A post-processing approach would retrieve all the triples first and then filter them all out.

The data annotation approaches that use custom language such as [START_REF] Lopes | [END_REF]], rewrite the user query to include annotations based on the access control policy. The query that contains annotations is then evaluated over an extension of RDF that supports annotations. Similarly to the rewriting technique, these approaches are tied to the query language. Moreover, additional mechanisms are needed in the RDF store to support custom languages and extended RDF models. Other approaches use the graph name position to store a boolean representing the access decision [Flouris 2010]. Which means that for each triple, all the user profiles decisions must be computed and stored at the design time. Moreover, this kind of approaches does not support incremental re-computation of annotations, as the latter do not store any information about the policy.

Filling the gaps

Our formal approach and its concrete enforcement are driven by the following key requirements: expressiveness, modularity, applicability, verifiability, and performance.

• Expressiveness: We propose in Chapter 3 the syntax and semantics of an expressive fine-grained access control model for RDF. In our model, authorizations are defined using SPARQL BGPs, which allows the definition of fine-grained policies. Moreover, instead of hardcoding the conflict resolution strategy or selecting one from predefined strategies, we proposed a more liberal approach. Indeed, abstracting the conflict resolution function allows the administrator to define not only the classical conflict resolution strategies but also custom strategies, which makes our model more expressive.

• Modularity: Our model semantics are defined by means of positive subgraph which relies on the access control policy and the base graph, without reference to a concrete query language such as SPARQL, in contrast to models driven by query rewriting. In our model, the supported set of inference rules is not be limited to RDFS rules. User defined rules can be used as well. Indeed, to cope with inference, it suffices to replace the base graph G by its closure Cl(G) according to a set of inference rules. This makes our model independent from the entailment engine as well.

Moreover the implicit triples are considered as the explicit ones and do not depend on the triples used to infer them. In our model, the entity to which the authorizations are granted or denied is left implicit. The upstream mapping from requesters to authorizations may use any model from the literature. In Chapter 5 we propose a XACML-inspired policy language that allows the definition of subject attribute-based policies.

• Verifiability: In Chapter 4, we formally characterize the issue that arises when inference rules produce facts which would have been forbidden otherwise. This issue occurs when the positive subset of a closed graph is not, itself, closed. We show that it can be statically checked, without knowledge of the base graph G, whether a policy is consistent w.r.t. a set of inference rules.

• Applicability: Our model is defined with triple-based authorizations which are both natural for SPARQL knowledgeable administrators and are naturally converted to efficient SPARQL CONSTRUCT queries to be run on the store. In Chapter 3, we show that our policies can capture quite complex access control requirements with exceptions that occur in real-life scenarios. We propose in Chapter 6 a data-annotation-based enforcement approach to our model and we show that no additional mechanisms are needed to apply our enforcement.

• Performance: We focus our attention on search queries on graphs. We show in Chapter 6 that our implementation incurs reasonable overhead at runtime (about +50%) with respect to the optimal solution which consists in materializing the user's accessible subgraph. We show that the query evaluation overhead is independent from the size of the base graph and the number of policy authorizations. In this chapter, we define an access control model for RDF called AC4RDF (Access Control For the Resource Description Framework), that uses the ingredients from Section 2.1 (P. 14). First, we define atomic authorizations and policies, then we give their formal semantics. Conflict resolution strategies are used to resolve such conflicts by selecting the preferred authorizations to apply, with respect to some properties of the authorizations. Whereas most of the works hard-code their strategies, others define them as parameters that are fixed by the administrator during policy design. We propose a more liberal approach by defining our policy using an abstract conflict resolution function ch which is defined by the administrator. We present three conditions that must be respected by the authorization policy to be well-formed. In Section 3.2 we give examples of how to build ch to apply simple strategies such as DTP. Moreover, we show how to build more elaborate strategies such as MSTP to handle exceptions.

Authorization policy

An authorization policy is an encoding of the control requirements of a application using the authorization language that is understood by the PDP. An authorization is defined as a tuple made of an effect, some resource definition and a condition. The resources under consideration are triples from the RDF graph being accessed by the requester. These triples are selected by means of triple patterns. The conditions are graph patterns that tell when the authorization is applicable. The effect is a boolean value denoting giving or forbidding action to the selected resources.

In this chapter, we assume that the PDP knows what are the authorizations applicable to a given authenticated requester. The entity to which authorizations are granted or denied is left implicit. The upstream mapping from requesters to authorizations may use any model from the literature, for instance using users' identifiers, groups, roles or set of attributes. In other words, we assume that the PDP is able to produce a set of authorizations in our formalism for each requester. Moreover, we restrict ourselves to the read action on RDF graphs. Regarding upstream policy definitions, we propose in Chapter 5 an attribute based high level language that allows to define global policies. When a user requests access, her/his policy is enforced by AC4RDF.

Authorization semantics

We define authorizations using basic SPARQL constructions, namely basic graph patterns, in order to facilitate the administration of access control and to include homogeneously authorizations into concrete RDF stores without additional query mechanisms. . 3.1. Authorization a 1 grants access to triples with predicate : hasTumor. Authorization a 2 states that all triples of type : Cancerous are denied. Authorizations a 3 and a 4 state that triples with predicate : service and : treats respectively are permitted. Authorization a 5 states that triples about admission to the oncology service are specifically denied, whereas the authorization a 6 states that such information are allowed in the general case. a 7 grants access to properties domain and a 8 denies access to any triple which object is : Cancerous. Finally, authorization a 9 denies access to any triple, it is meant to be a default authorization.

Given an authorization a ∈ Auth and a graph G, we say that a is applicable to a triple t ∈ G if there exists a substitution θ such that the head of a is mapped to t and all the conditions expressed in the body of a are satisfied as well. In other words, we evaluate the underlying graph pattern hb(a) = {head(a)} ∪ body(a) against G and we apply all the answers of hb(a) G to head(a) in order to know which t ∈ G the authorization a applies to. In a concrete system, this evaluation step would be computed using the mechanisms used to evaluate SPARQL queries. In fact, given an authorization a, the latter is translated to a SPARQL query which is evaluated over G. The result represents the triples over which a is applicable. Definition 3.1.3 (Applicable Authorizations) Given a finite set of authorizations A ∈ P(Auth) and a graph G ∈ BGP, the function ar assigns to each triple t ∈ G, the subset of applicable authorizations from A : 3.1. The applicable authorizations on triple it 2 are computed as follows : ar(Cl(G 0 ), A)(it 2 ) = {a 5 , a 6 , a 9 }. The mappings from hb(a 5 ), hb(a 6 ) and hb(a 9 ) to Cl(G 0 ) are illustrated by Figure 3.1.

ar(G, A)(t) = {a ∈ A | ∃θ ∈ hb(a) G .t = (head(a))θ}
The scope of an authorization over a given graph G is the set of triples in G to which the authorization is applicable. The scope is computed by the evaluation of the BGPs forming the authorization (see Definition 2.1.8 (P. 19)). Please note that the fragment defined in Definition 3.1.1 is basically used to define our access control model, and it is not meant to replace the generic SPARQL query language on RDF stores, as our approach is independent from the query language. 3.1, and the graph Cl(G 0 ) in Figure 2.4 (P. 23). The scope of a 8 is computed as follows : scope(a 8 ) = {et 1 , it 1 }.

Policy and conflict resolution function

As exemplified above, there may exist some t such that the set ar(G, A)(t) is not a singleton authorization, which can lead to policy inconsistency. When several authorizations with different effects are applicable, one has to specify a conflict resolution strategy that defines which of the effects has to be selected. Also note that there may exist a triple for which the set of applicable authorizations is empty which leads to policy incompleteness. The solution to ensure that the decision function is total, is to specify a default decision.

To prevent us from defining many extra parameters, arbitrarily fixing some conflict resolution strategies or running into considerations on conflict resolutions, we abstract from the details of the concrete resolution strategies by assuming that there exists a choice function that, given a finite set of possibly conflicting authorizations, picks a unique one out. This design choice as well as the issues related to the modeling of classical conflict resolution strategies are discussed in Section 3.2.

Definition 3.1.7 (Policy, Conflict Resolution Function) An

(authorization) policy P is a pair P = (A, ch), satisfying the following well-formedness conditions, where A is a finite set of authorizations and ch ∈ P(A) \ {∅} → A is a conflict resolution function:

• Totality: ∀G ∈ BGP.∀t ∈ G. ar(G, A)(t) = ∅ • Closedness: ∀A ⊆ A.A = ∅ ⇒ ch(A ) ∈ A • Monotony: ∀B ⊆ A, B = ∅. ch(B) = a ⇒ (∀B ⊆ B. a ∈ B ⇒ ch(B ) = a)
The subset of P(Auth) × (P(Auth) → Auth) that satisfies the above wellformedness conditions is denoted by Pol.

The well-formedness conditions are properties which ensure that the conflict resolution functions behave well when applied to set of authorizations. The Totality property avoids a corner case. We explain in Section 3.2 how to enforce default decisions that ensure this property. The Closedness property guarantees that the selected authorization is taken from the input. The Monotony property is more technical but it captures an intuitive requirement that is: the conflict resolution function makes consistent choices, which means its answer is kept the same when lesser choices are available. 3.1 and ch is defined as follows. For all non-empty subset B of A, ch(B) is the first authorization (using syntactical order of Table 3.1) of A that appears in B. Totality stems from a 9 , as it is applicable to any triple. Closedness and Monotony directly stem from the definition of ch.

We are ready to give semantics of policies by composing the functions ar, ch and then effect in order to compute the authorized subgraph of a given graph.

Definition 3.1.9 (Policy Evaluation, Positive Subgraph) Given a policy P = (A, ch) ∈ Pol and a graph G ∈ BGP, the set of authorized triples that constitutes the positive subgraph of G according to P is defined as follows, writing G + when P is clear from the context:

G + P = {t ∈ G | (effect • ch • ar(G, A))(t) = +}
As illustrated by Figure 3.2, to construct the positive subgraph, the first step consists in computing the closure of the base graph, then assigning each triple of the result with its applicable authorizations. The next step consists in applying ch on the applicable authorizations and assigning every triple with the decision of the chosen authorization. The last step consists in generating the positive subgraph which contains the triples assigned with positive effect. Algorithm 1 allows the computation of the positive subgraph, given a policy, a set of inference rules and a base graph. 3.2. Regarding the triple it 2 = (:alice ; :admitted ; :onc), ar(Cl(G 0 ), A)(it 2 ) = {a 5 , a 6 , a 9 }. Since a 5 is the first among authorization in Table 3

t ar(Cl(G 0 ), A)(t) ch(ar(Cl(G 0 ), A)(t)) effect(ch(ar(Cl(G 0 ), A)(t))) et 1 {a 7 , a 8 , a 9 } a 7 + et 2 {a 9 } a 9 - et 3 {a 9 } a 9 - et 4 {a 1 , a 9 } a 1 + et 5 {a 3 , a 9 } a 3 + et 6 {a 4 , a 9 } a 4 + it 1 {a 2 , a 8 , a 9 } a 2 - it 2 {a 5 , a 6 , a 9 } a 5 - it 3 {a 9 } a 9 -

Conflict resolution strategies semantics

In this section, we define properties of the ch function, related to the conflict resolution strategies. In other words, ch applies a given strategy if it satisfies the property of this strategy.

To define the DTP(PTP) properties, we need to define a partition of the set of authorizations into two sets containing the positive and negative authorizations respectively. Definition 3.1.11 Given a set of authorizations A. ∀B ⊆ A. B can be partitioned into two sets B -and B + such that:

B -= {a ∈ B | effect(a) = -} B + = {a ∈ B | effect(a) = +}
Example 3.1.12 Consider the set of authorizations A shown in Table 3.1. Let us consider the subset of authorizations B = {a 7 , a 8 , a 9 }. The subset of negative and positive authorizations in B are defined as follows: B -= {a 7 }, B + = {a 8 , a 9 } A function ch applies the DTP(PTP) strategy if it returns a negative (positive) authorization from the input set, when the latter contains at least one negative (positive) authorization. Definition 3.1.13 ( DTP(PTP) property) A function ch applies the DTP(PTP) strategy if it satisfies the DTP(PTP) property. The DTP and PTP properties are defined as follows:

DTP property: ∀B ⊆ A. ∃a ∈ B -⇒ ch(B) ∈ B - PTP property: ∀B ⊆ A. ∃a ∈ B + ⇒ ch(B) ∈ B +
Regarding the MSTP strategy, it is particularly adequate to capture exceptions in policies in a natural way. For instance, in Table 3.1, the authorization a 5 that denies admissions to oncology service is an exception of the authorization a 6 which allows admissions in general. According to the MSTP strategy, a 5 should prevail over a 6 . A function ch applies the MSTP strategy if it returns an authorization that have no other more specific authorization. Semantically, an authorization a 1 is more specific than a 2 if for any given graph G, the scope of a 1 in G is a subset of the scope of a 2 in G, formally, scope(G)(a 1 ) ⊆ scope(G)(a 2 ). Syntactically, an authorization a 1 is more specific than authorization a 2 when the underlying graph pattern of a 2 can be matched to the one of a 1 with the restriction that the head of a 2 is mapped to the head of a 1 . Definition 3.1.14 We say that an authorization a 1 is more specific than authorization a 2 denoted by a 1 MS a 2 if ∃θ. hb(a 2 )θ ⊆ hb(a 1 )∧head(a 2 )θ = head(a 1 ).

Example 3.1.15 Consider authorizations a 5 and a 6 shown in Table 3.1. There exists a substitution mapping θ between a 5 and a 6 s.t. θ = {?p → ?p, ?s → ?s} and hb(a 6 )θ ⊆ hb(a 5 ) ∧ head(a 6 )θ = head(a 5 ), hence a 6 MS a 5 ;

After defining the specificity relation, we can now check if a function ch satisfies the MSTP property, i.e. when it returns one of the smallest authorizations with respect to MS .

Definition 3.1.16 ( MSTP) property) A function ch applies the MSTP strategy if it satisfies the following property:

Let MS be the specificity relation between authorizations MSTP property:

∀B ⊆ A. ch(B) = a ⇒ (∀a ∈ B. a MS a ⇒ a MS a)

Building Policies

In this section, we illustrate the applicability of policies as defined in Definition 3.1.7 by showing how to construct ch functions for applying conflict resolution strategies known in the literature. Note that our ch function is responsible for resolving conflicts between authorizations, as well as applying the default strategy.

Default Strategy

A default strategy is a decision that is selected when no other authorization is applicable, that is when ar(G, A)(t) = ∅. Such a default strategy can either be deny by default or permit by default. In order to respect the Totality well-formedness condition of Definition 3.1.7, we cannot simply apply a default decision. However, we have to identify a default authorization called universal authorization denoted by a u , that is applicable to any triple. a u is added to the set of authorizations in order to achieve Totality. In fact, the triples that have no applicable authorizations but a u , will have a decision that is equal to the effect of a u . Hence the effect of a u plays the role of the default decision of classical approaches. An authorization is applicable to any triple if it has three different variables in the head, and an empty body.

Definition 3.2.1 An authorization a

u ∈ Auth is called universal if a u = GRANT/DENY (s ; p ; o) such that s, p, o ∈ V and s = p, p = o, s = o.
The following lemma shows that the Totality condition can be ensured by adding a universal authorization. Lemma 3.2.2 Let A be a finite subset of Auth. The following statements are equivalent:

∀G.∀t ∈ G. ar(G, A)(t) = ∅ ∃a u ∈ A.∀G.∀t ∈ G.a u ∈ ar(G, A)(t) Proof One direction is straightforward, if a u ∈ A is such that a u ∈ ar(G, A)(t), then ar(G, A)(t) = ∅.
For the opposite direction, consider a triple t e = (?s e ; ?p e ; ?o e ) with fresh variables not already used in A, that is, t e is such that for all authorizations a ∈ A, it is the case that ∀(?s; ?p; ?o) ∈ hb(a).?s = ?s e ∧?p = ?p e ∧?p = ?p e . Such a triple t e always exists because there is an infinite set V of variables but only finitely many appear in A. Consider the graph G e = {t e }, by hypothesis ar(G e , A)(t e ) is not empty, so consider an authorization a u in this set.

We show that this authorization is universal. By Definition 3.1.3, we know that there exists some η ∈ hb(a u ) G with t e = (head(a u ))η. Thus, by Definition 2.1.8 (P. 19), we have that (hb(a u ))η = {t e } because hb(a u ) cannot be empty. Let G a an arbitrary graph and t a = (?s a ; ?p a ; ?o a ) ∈ G a . Consider the substitution η that maps t e to t a defined by (?s e )η = ?s a , (?p e )η = ?p a . By construction, (hb(a u ))ηη = {t a } and t e = (head(a u ))ηη , thus a u ∈ ar(G a , A)(t a ).

For instance, the default strategy in Table 3.1 is given by authorization a 9 which effect is DENY. Hence a closed policy. Note that there may be several different universal authorizations in the set A. Therefore, conflicts will be systematically triggered. Even though it is formally possible to have several universal authorizations, we can assume that such authorization is unique. Assumption 3.2.3 Given a policy P = (A, ch).The set of authorizations A contains a unique universal authorization.

Note that the addition of a default rule at the end of a rule set is standard practice in firewall policies. Moreover, following previous discussion on the total syntactical order, this authorization should be naturally appended to the end of the set of authorizations. More generally, given a total order on A, the universal authorization should be the maximum element of A with respect to . Doing so, it wont be selected unless it is the only choice. This reflects the semantics of the default strategy which only applies when there is no other applicable authorization.

First Applicable strategy

First of all, we notice that if there exists a total order denoted by over a set of authorizations A, we can apply the FA satrategy by constructing a conflict resolution function ch that selects the minimum element from a subset B ⊆ A ordered by .

Definition 3.2.4 Given a set of authorizations A and a total order on A.

For any B ⊆ A, the minimum authorization of B with respect to is defined as follows:

min (B) = a ∈ B | ∀a ∈ A. a a
Lemma 3.2.5 Given a set of authorizations A and a total order on A, P = (A, min ) is a well-formed policy.

Proof We prove that P = (A, min ) satisfies the well-formedness conditions.

For Totality, by assumption 3.2.3, there exists a universal rule a u ∈ A. Closedness and the Monotony are satisfied by construction of min .

There are several ways to equip A with a total order. For instance, the administrator can explicitly assign a unique prevalence level to each authorization or she/he can rely on the syntactical order. When one writes a set of authorizations such as the one shown in Table . 3.1, there is a total order given by the order of the statements. The syntactical order is always available and it is used, for example, in firewalls, so that no ambiguity arises. Note that given a policy P = (A, ch), we can construct a total order ch on A with ch. From an implementation point of view, constructing a total order from ch could improve performance of the access control enforcement. The idea is to compute the total order ch during policy design time, and replace the original ch by min ch .

Lemma 3.2.7 Given a policy P = (A, ch), then we can construct a total order ch on A with ch function s

.t. ∀a 1 , a 2 ∈ A.a 1 ch a 2 ⇐⇒ ch({a 1 , a 2 }) = a 1 .
Proof We prove that ch is reflexive, antisymmetric, transitive and total.

• Reflexivity: Since ch({a, a}) = a then a ch a. Thus ch is reflexive.

• Antisymmetry: If a 1 ch a 2 then ch({a 1 , a 2 }) = a 1 , hence if a 1 = a 2 then ch({a 2 , a 1 }) = a 2 ,
which means that a 2 ch a 1 . Thus ch is antisymmetric.

• Transitivity: We prove that if a 1 ch a 2 and a 2 ch a 3 then a 1 ch a 3 . If ch({a 1 , a 2 , a 3 }) = a 3 then ch({a 2 , a 3 }) = a 3 from Monotony condition. Contradiction with a 2 ch a 3 . If ch({a 1 , a 2 , a 3 }) = a 2 then ch({a 1 , a 2 }) = a 2 from Monotony condition. Contradiction with a 1 ch a 2 . Since ch({a 1 , a 2 , a 3 }) = a 3 and ch({a 1 , a 2 , a 3 }) = a 2 then ch({a 1 , a 2 , a 3 }) = a 1 from ch Closedness. Hence ch({a 1 , a 3 }) = a 1 from ch Monotony. Which means that a 1 ch a 3 . Thus ch is transitive.

• Totality:

By ch Closedness, ∀a 1 , a 2 ∈ A. ch({a 1 , a 2 }) = a 1 or ch({a 1 , a 2 }) = a 2 . Hence, a 1 ch a 2 or a 2 ch a 1 . Thus ch is to- tal.
The following proposition shows that there exists a bijection between total orders and choice functions.

Proposition 3.2.8 Given a policy P = (A, ch), there exists a bijection between ch and ch Proof Let P = (A, ch) be a policy.

Let ch be a binary relation s.

t ∀a 1 , a 2 ∈ A.a 1 ch a 2 ⇐⇒ ch(a 1 , a 2 ) = a 1 . First we prove that min ch (A) = ch(A). If min ch (A) = a ∈ A then ∀a ∈ A.a ch a (by ch definition). Let b = ch(A). We have b ∈ A, hence a ch b, which means that ch(a, b) = a. Since {a, b} ⊆ A, then, by ch Monotony, ch(a, b) = b = ch(A), hence a = b.
Let be a total order. Let min the choice function associated to . Let min a total order constructed from min s.t ∀a 1 , a 2 ∈ A.a 1 min a 2 ⇐⇒ a 1 = min ({a 1 , a 2 }).

We prove that min ⇐⇒

a 1 min a 2 ⇐⇒ min ({a 1 , a 2 }) = a 1 ⇐⇒ a 1 a 2

Precedence Strategies

As we mentioned in Chapter 2 (P. 13), the DTP strategy resolves conflicts by stating that the negative authorizations prevail over the positive ones; the PTP strategy being its dual. The idea to capture the DTP (resp. PTP) strategy is to transform a policy P = (A, ch) into a policy P -= (A, ch -) where ch - privileges negative (resp. positive) effects. Considering the previous discussion on default policies, we assume that there is a unique universal authorization a u ∈ A. As a u is assumed to be a default authorization, we require that B \ {a u } = ∅ if and only if ch(B) = a u . Remind that B -(resp. B + ) is the subset of B with a negative (resp. positive) effect. With B ⊆ A, the ch - function is formally defined as follows:

ch -(B) = ⎧ ⎨ ⎩ ch(B -\ {a u }) if B -\ {a u } = ∅ (1) ch(B + \ {a u }) if B -\ {a u } = ∅ ∧ B + \ {a u } = ∅ (2) a u if B \ {a u } = ∅ (3)
Similarly, the dual function ch + is defined by flipping + and -in the definition of P -. The next lemma ensures that the construction is correct. Lemma 3.2.9 (Correctness of P -) Given P = (A, ch) a policy according to Definition 3.1.7 with a unique universal authorization a u ∈ A such that Lemma 3.2.10 (DTP strategy application) Given a policy P -= (A, ch -), ch -applies the DTP strategy.

Proof We prove that ch -satisfies the DTP property (see Definition 3.1.13).

∀B ⊆ A. if ∃a ∈ B -s.t. a = a u then B -\ {a u } = ∅, hence, by ch - definition, ch -(B) = ch(B -\ {a u }). Which means that ch -(B) ∈ B -. Thus ch -satisfies the DTP property.
Similarly, Lemmas 3.2.9 and 3.2.10 apply to P + and ch + respectively.

Example 3.2.11 Consider the graph Cl(G 0 ) shown in Figure 2.4 (P. 23) and the set of authorizations A shown in Table 3.1. Let us consider the authorizations applicable to triple et 1 , that is ar(Cl(G 0 ), A)(et 1 ) = {a 7 , a 8 , a 9 }. If we consider the ch given in Example 3.1.8, that is, the syntactical order, authorization a 7 , a positive one, is selected. However, with the DTP construction, we have that ch -({a 7 , a 8 , a 9 }) = ch({a 8 }) = a 8 .

Most Specific Takes Precedence (MSTP)

We showed in Section 3.1.3 that the MSTP property is captured by a binary relation MS defined by substitutions. Clearly, the identity substitution makes MS relation reflexive and composition of substitution makes it transitive. Therefore, it is a preorder (quasiorder). Note that MS being a preorder, it is not anti-symmetric. Indeed, we may have two different authorizations with different effects a 1 and a 2 where a 1 MS a 2 and a 2 MS a 1 . Chosing the most specific authorization amounts to select the smallest authorization w.r.t MS . Since MS is a preorder, then the smallest authorizations may be more than one. As shown by Lemma 3.2.5, given a total min order, we can construct a policy P = (A, min ). The idea is to construct a total order from the preorder MS to make a ch function that applies MSTP. First, we consider two equivalent authorizations as incomparable in order to make a partial order MSTP from the preorder MS . Definition 3.2.12 Given a set of authorizations A. MSTP is a binary relation over A defined as follows:

• ∀a 1 ∈ A, ∀a 2 ∈ A. a 1 = a 2 . a 1 MSTP a 2 if a 1 MS a 2 and a 2 MS a 1 • ∀a ∈ A.a MSTP a Lemma 3.2.13 MSTP is a partial order.
Proof We prove that MSTP is reflexive, anti-symmetric and transitive.

• Reflexivity : By Definition 3.2.12, MSTP is reflexive.

• Transitivity : We prove that if a 1 MSTP a 2 and a 2 MSTP a 3 then a 1 MSTP a 3 .

If a 1 = a 2 or a 2 = a 3 , then transitivity is trivial. By Definition 3.2.12 a 1 MSTP a 2 ⇒ a 1 MS a 2 and a 2 MS a 1 a 2 MSTP a 3 ⇒ a 2 MS a 3 and a 3 MS a 2

We want to prove that a 1 MSTP a 3 i.e. a 1 MS a 3 and a 3 MS a 1 Since a 1 MS a 2 and a 2 MS a 3 then a 1 MS a 3 by MS transitivity. Now we prove that a 3 MS a 1 . For the sake of the contradiction, suppose that a 3 MS a 1 . Since a 1 MS a 2 then a 3 MS a 2 by MS transitivity. Which is a contradiction with a 3 MS a 2 , hence a 3 MS a 1 . Since a 1 MS a 3 and a 3 MS a 1 then a 1 MSTP a 3 by Definition 3.2.12.

• Anti-symmetry : We prove that if a 1 = a 2 and a 1 MSTP a 2 then a 2 MSTP a 1 By Definition 3.2.12 a 1 MSTP a 2 ⇒ a 1 MS a 2 and a 2 MS a 1 For the sake of the contradiction, suppose that a 2 MSTP a 1 i.e. a 2 MS a 1 and a 1 MS a 2 , contradiction. Hence a 2 MSTP a 1 .

Hence MSTP is partial order After making a partial order MSTP from the preorder MS , we can now construct a total order MSTP using the partial order MSTP and the total lexical order LEX already defined by the administrator.

MSTP represents a topological sort (i.e. linear extension) of the partially ordered authorizations. Many algorithms could be used for the topological sort, such as Kahn's Algorithm [Kahn 1962]. We adapted Kahn's Algorithm to make it deterministic, where instead of selecting a random authorization, we select the smallest one with respect to LEX . Algorithm 2 takes as parameters, the total order LEX and H A a Directed Acyclic Graph (DAG) where the nodes represent authorizations in A, and edges represent the irreflexive related authorizations with , i.e. (a b and a = b) ⇒ a → b.

Algorithm 2 starts by inserting all authorizations without incoming edges into a set S. Then it starts a loop where the smallest authorization a in S w.r.t LEX is inserted into L at an indice equal to the current iteration. a is then removed from S and all edges outgoing from it are removed as well. Next, the new authorizations with no incoming edges are inserted to S. The loop stops when S becomes empty. Finally if there are remaining edges in the graph, then it contains cycles, otherwise the Algorithm returns the total order A representing a linear extension of .

Algorithm 2 Algorithm for constructing a total order from partially ordered authorizations Input: a graph H A of authorizations ordered by , and the total syntactical order LEX . Output: a total order relation A .

1: Let L ← an Array that will contain the sorted authorizations, with indices from 1..|A| 2: Let S ← the set of all authorizations with no incoming edges 3: Let iteration ← 0 4: while S is not empty do 5:

iteration ← iteration + 1 6: Let a = min LEX (S) 7: L[iteration] ← a 8:
Remove a from S

9:

for all a with an edge e from a to a do Error, the graph contains a cycle, and the topological sort is not possible 18: else 19:

Let A be the following binary relation:

L[i] A L[j] ⇐⇒ i ≤ j 20: Return A 21: end if
The following lemma shows that at each iteration of the loop between lines 4 and 15, the next selected authorization is the smallest one w.r.t LEX from the rest of the not processed authorizations. Using Algorithm 2, we generate a total order denoted by MSTP , from MSTP and LEX . After generating the total order over authorizations, we can now define the ch that applies the MSTP by choosing the smallest authorization w.r. 3.1. Algorithm 2 takes as parameters the total syntactical order of the Table 3.1, and the DAG H A MSTP depicted by Figure 3.3. Table 3.3 shows the values of S and L at the end of each iteration of the loop between lines 4 and 15. The result of the Algorithm is a total order equal to LEX since the latter is a linear extension of MSTP as shown by Lemma 3.2.15.

Iteration S L 1 {a 3 , a 4 , a 2 , a 5 , a 7 } a 1 2 {a 3 , a 4 , a 5 , a 7 , a 8 } a 1 a 2 3 {a 4 , a 5 , a 7 , a 8 } a 1 a 2 a 3 4 {a 5 , a 7 , a 8 } a 1 a 2 a 3 a 4 5 {a 7 , a 8 , a 6 } a 1 a 2 a 3 a 4 a 5 6 {a 7 , a 8 } a 1 a 2 a 3 a 4 a 5 a 6 7 {a 8 } a 1 a 2 a 3 a 4 a 5 a 6 a 7 8 {a 9 }
a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 9 {} a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9

Conclusion

In this chapter, we introduced a fine-grained access control model for RDF stores with inference capabilities. Whereas some models allow or deny queries, we gave semantics to authorizations by means of the authorized subgraph of a base graph, doing so we are independent of a given query language. Instead of hard-coding the conflict resolution strategy, we proposed a more liberal approach, by defining an abstract conflict resolution function ch. The latter can be coded by the administrator during policy design time. We showed how concrete resolution strategies can be instances of our abstract framework. Moreover, we showed how more elaborate strategies, notably most specific takes precedence, can be built in our framework. To prevent a malicious user who knows the inference rules, from accessing confidential triples by applying these rules on his accessible triples, we propose in the next chapter a static verification approach to detect and fix the inference leakage problem.

Chapter 4

Inference leakage problem and solution Access control models offer protection against direct accesses to sensitive information; however, indirect accesses to sensitive information may still be possible via inferences. Indeed, security violations via inferences called inference problem (inference leakage problem) occurs when sensitive information can be inferred from authorized data. In this chapter we show how static verification could be used to detect policy inconsistencies with respect to inference. In Section 4.1 we give an overview about the inference problem in different data models, and we show the different techniques to deal with it. In Section 4.2, we formally define the inference leakage problem which arises when confidential triples are inferred from authorized triples. We formalize the consistency property that captures the inference leakage problem. This property ensures that confidential information can not be inferred from authorized information with respect to a set of inference rules. To solve the issue, we propose in Section 4.3 a static verification algorithm which is run at policy design time. The algorithm checks if the interaction between policy authorizations and inference rules may lead to inference leakage. It generates a set of counterexample BGPs which represent graphs over which the policy presents an inference leakage problem. In Section 4.3.2 we show how to use the answer of the algorithm to fix the policy, or how to use them as integrity constraints that do not allow updates which could lead to inference leakage.

The inference problem

The inference problem (see [Farkas 2002] for a survey) exists in all types of database systems and has been studied extensively within the context of multilevel databases. Early works on the inference problem focused on statistical database security [START_REF] Adam | [END_REF]]. The main requirement for securing statical databases is to allow users to make statistics by giving access to groups of entities while protecting the confidentiality of the individual entities. The problem is that a user might obtain confidential information about an individual entity by correlating different statistics. Another kind of inference problem appeared on data models which use semantic constraints such as functional dependencies [START_REF] Su | [END_REF]]. Here, sensitive information can be disclosed from non-sensitive data and meta-data. We illustrate with the example used by [START_REF] Su | [END_REF]]. Assume that a company database consists of the relation scheme EMP-SAL, which has three attributes: Name, Rank, and Salary. The relation < N ame, Salary > is a secret, but user u requests the following two queries: List Rank and Salary of all employees and List the Name and Rank of all employees. None of the queries violates the security requirement because they do not contain the secured < N ame, Salary > pair; however, suppose u is aware of the constraint that all employees having identical ranks have the same salaries, then she/he can infer the salary of employees.

Several works have been devoted to detect and deal with inference leakages. Inference control techniques can be divided according to the time of the inference detection control, i.e. static and dynamic approaches:

• Static approaches In the static approaches [START_REF] Su | [END_REF]], all processing is done offline during design time. Once a security violation via inferences is detected, the system is modified to repair such violations. Modifications are done on the database schema or on the access control policy.

The main advantage of this approach is that it is computationally less expensive than the dynamic approach. However, this approach may result in reduced availability of data because the inference problem may not materialize in a particular database instance.

• Dynamic approaches

In the dynamic approaches ( [Thuraisingham 1987]), the processing is done during runtime. Every issued query is checked whether or not it could lead to confidential data disclosure. If an inference violation is detected, the query is either refused or modified to avoid such violations. Most of these approaches keep a log of all queries issued by the user so they can be combined with the current one to check if the query is allowed or not. Whereas this kind of approaches increase availability, they are computationally expensive, since the violation check is done for every query.

In the context of RDF, [START_REF] Jain | [END_REF]] used a static approach by defining an algorithm that detects inference violations using the policy and the base graph (see Section 2.3). Since we focus on the publication of RDF triples in the context of linked data, we concentrate on fast query answering, hence we favor the static approach. Before we show how to detect whether a policy presents a problem of inference leakage, we define the consistency property.

Consistency property

The inference rules which are applied to a graph reflect the particular knowledge conveyed by the graph. Hence, the real semantics of a graph are represented by its closure, regardless it is materialized or not. Thus, inference leakage has to be considered in the closure of a graph, rather than considering only the base graph which is under control of a trusted RDF store. The interaction between authorizations and inference rules raises the issue of policy violation because it could lead to confidential data leakage. A malicious user who knows the inference rules could use a local reasoner and apply the inference rules over her/his accessible triples to infer triples she/he is not supposed to access. To illustrate this issue, consider the following example.

Example 4.2.1 Assume a set of inference rules R = {RDom, RAdm}, as shown in Example 2. 1.16 (P. 22). We want to apply the policy defined in Example 3.1.10 (P. 50) on the graph Cl R (G 0 ) of Figure 2.2 (P. 16). According to Example 3.1.10 (P. 50), the authorized subgraph is

(Cl R (G 0 )) + P = {et 1 , et 4 , et 5 , et 6 }. If one computes the closure of (Cl R (G 0 )) + P , she/he obtains (Cl R (G 0 )) + P ∪ {it 1 , it 2 }.
Whereas the policy states that triples it 1 and it 2 must be denied, they are deduced from the authorized subgraph, hence the inference leakage. Figure 4.1 illustrates the inference leakage using RDom.

We formally characterize the issue that arises when inference rules produce facts that would have been forbidden otherwise. This issue occurs when the positive subset of a closed graph is not, itself, closed. The consistency property has to hold for all graphs. It does not have to be checked when stored graphs are updated, but solely at the policy design-time or when the inference rules or the authorizations change.

Static verification

In computer programming, static code analysis provides a way to analyze the code in order to detect possible errors and security weaknesses [START_REF] Livshits | [END_REF]]. In the context of access control, the static analysis could be used to check whether given properties are satisfied by the policies. In this section, we show a key property of the framework introduced so far: it is possible to check, without any knowledge of a base graph, if a policy is consistent w.r.t. a set of inference rules. We define Algorithm 3 that, given an authorization policy P = (A, ch) and a set of inference rules R, checks whether the consistency property (Definition 4.2.2) holds. Algorithm 3 is an enumeration algorithm and not a mere decision algorithm: it is constructive and finds all possible counterexamples to the consistency property.

Algorithm 3 Algorithm for enumerating inconsistency patterns

Input: a set of inference rules R, an authorization policy P = (A, ch) Output: a collection BGP s of counterexample basic graph patterns 1: function RdfLeaks(R, P )

2: BGP s ← ∅ 3: for all r = (tp ← tp 1 , . . . , tp k ) ∈ R do 4: for all (a 1 , . . . , a k , a) ∈ A + k × A -do 5:
let ρ 1 , . . . , ρ k , ρ be renaming substitutions for a 1 , . . . , a k , a 6:

let (ha 1 , . . . , ha k , ha) = (head(a 1 )ρ 1 , . . . , head(a k )ρ k , head(a)ρ) 7:
if ∃μ = mgu((ha 1 , . . . , ha k , ha), (tp 1 , . . . , tp k , tp)) then return BGP s 16: end function The principle of Algorithm 3 is to find an inference rule (tp ← tp 1 , . . . , tp k ) ∈ R and related sets of authorizations (a 1 , . . . , a k , a) such that a is negative and its head is unifiable with tp and all authorizations a i for i ∈ {1, . . . , k} are positive and their heads are unifiable with {tp 1 , . . . , tp k }. Pictorially:

8: let B = k i=1 hb(a i )ρ i μ ∪ hb(a)ρμ 9: if {(tp 1 )μ, . . . , (tp k )μ} ⊆ (Cl R (B)) + P and (
r = hb(a 1 ) tp 1 . . . hb(a k ) tp k tp hb(a)
with effect(a i ) = + and effect(a) = -Intuitively, let us consider the graph B built by considering the union of the underlying graphs hb(a 1 ) . . . hb(a k ) and hb(a), properly renamed and unified. By construction, the inference rule r is applicable. Moreover, all authorizations are applicable as well. On the one hand, triples tp 1 to tp k are authorized by some positive authorizations. On the other hand, tp is inferred using rule r but is forbidden by authorization a: an inconsistency.

The key idea that ensures the completeness of Algorithm 3 is that all

Lemma 4.3.7 If Cl R (G) = G, then there exists t ∈ φ R (G) ⊆ Cl R (G) such that t ∈ G. Proof By definition 2.1.13, Cl R (G) = i∈N G i , where G 0 = G and G i+1 = φ R (G). By induction on i, we prove that if G = G i+1 then there exists t ∈ φ R (G) such that t ∈ G. If G = G i+1 , and since G ⊆ G i+1 , there exists t ∈ G i+1 such that t ∈ G. If t ∈ G i , then G i = G and we get the result by induction hypothesis on G i . If t ∈ G i , then t ∈ φ R (G i ). If G i = G, then it is sufficient to take t = t . Otherwise G i = G and we get the result by induction hypothesis on G i . Proof of Theorem 4.3.2 Let G ex be such that Cl R ((Cl R (G ex )) + P ) = (Cl R (G ex )) + P . By Lemma 4.3.7, there exists t ex ∈ φ R ((Cl R (G ex )) + P ) such that t ex ∈ (Cl R (G ex )) + P .
By Definition 2.1.13 (P. 21), there is a rule r = (tp ← tp 1 , . . . , tp k ) ∈ R and a substitution σ such that t ex = (tp)σ and

σ ∈ {tp 1 , . . . , tp k } (Cl R (G ex )) + P . Let us consider i ∈ {1, . . . , k}. Since σ ∈ {tp 1 , . . . , tp k } (Cl R (G ex )) + P , it is the case that (tp i )σ ∈ (Cl R (G ex )) + P . Let a i = ch(ar(Cl R (G ex ), A)((tp i )σ)) be the authorization selected for (tp i )σ in Cl R (G ex ). Since (tp i )σ ∈ (Cl R (G ex )) + P , a i ∈ A + . Similarly and since (tp)σ = t ex ∈ (Cl R (G ex )) + P , if we pose a = ch(ar(Cl R (G ex ), A)((tp)σ)) then a ∈ A -. Thus (a 1 , . . . , a k , a) ∈ A + k × A -,
and Algorithm 3 evaluates this combination of rule and authorizations at Line 4.

Let us assume ρ (resp. for any i ∈ {1, . . . , k}, ρ i ), ha (resp. ha i ) as they are defined by Algorithm 3 at Lines 5 and 6. Since P respects the Closedness and the Totality conditions of Definition 3.1.7 (P. 49), a ∈ ar(Cl R (G ex ), A)((tp)σ) (resp. for any i ∈ {1, . . . , k}, a i ∈ ar(Cl R (G ex ), A)((tp i )σ)). That is, by Lemma 4.3.5, there exists a substitution θ (resp. θ i ) such that:

(tp)σ = (ha)θ (1) (tp i )σ = (ha i )θ i (2) θ ∈ hb(a)ρ Cl R (G ex ) (3) θ i ∈ hb(a i )ρ i Cl R (G ex ) (4)
Because ρ, ρ 1 , . . . , ρ k are renaming substitutions, var(ha), var(ha 1 ), . . . , var(ha k ) and var({tp, tp 1 , . . . , tp k }) are pairwise disjoint. Thus we can in-troduce the following substitution μ :

μ (x) = ⎧ ⎪ ⎨ ⎪ ⎩ θ(x) if x ∈ var(ha) θ i (x) if x ∈ var(ha i ) σ(x) if x ∈ var({tp, tp 1 , . . . , tp k })
One can remark that (ha)μ = (tp)μ (resp.

for any i ∈ {1, . . . , k}, (ha i )μ = (tp i )μ ). Therefore, there exists μ = mgu((ha 1 , . . . , ha k , ha), (tp 1 , . . . , tp k , tp)), and there exists a substitution η such that μ = μη so condition at Line 7 is satisfied.

Let us consider B = k i=1 hb(a i )ρ i μ ∪ hb(a)ρμ as in Algorithm 3 at Line 8. By definition of μ and because of ( 1)-( 4

), Bη = ( k i=1 hb(a i )ρ i μ ∪ hb(a)ρμ ) ⊆ Cl R (G ex ).
Since hb(a)ρμ ⊆ B and head(a)ρμ = (ha)μ, we have a ∈ ar(B, A)((ha)μ). One can remark that (tp

)σ = (tp)μ = (ha)μ = ((ha)μ)η, (tp)σ ∈ Cl R (G ex ) and Bη ⊆ Cl R (G ex ).
Thus by Lemma 4.3.6, ar(Cl

R (B), A)((ha)μ) ⊆ ar(Cl R (Cl R (G ex )), A)((tp)σ) = ar(Cl R (G ex ), A)((tp)σ), as Cl R (Cl R (G ex )) = Cl R (G ex ). Moreover, since a ∈ ar(Cl R (B), A)((ha)μ) and a = ch(ar(Cl R (G ex ), A)((tp)σ))
, we deduce by the Monotony condition of Definition 3.1.7 (P. 49) applied on P that a = ch(ar(Cl R (B), A)((ha)μ)). Since effect(a) = -, we conclude that (tp)μ = (ha)μ ∈ (Cl R (B)) + P .

Similarly, for any i ∈ {1, . . . , k}, we deduce that (tp i )μ ∈ (Cl R (B)) + P . Therefore B is added in BGP s by Algorithm 3 at Line 10. Thus there is B ∈ RdfLeaks(R, P ) and η such that η ∈ B Cl R (G ex ) .

Understanding the Counterexamples

As Algorithm 3 enumerates inconsistency patterns, its output can be used to correct the access control policy. A proof of concept of the algorithm has been implemented in Prolog1 . The methodology to correct an inconsistent policy, as shown in Figure 4.2, is to iteratively apply the following two steps:

(1) use Algorithm 3 to obtain counterexample graph patterns; (2) change the authorization policy to correct inconsistencies illustrated by these graph patterns. The iteration stops when the authorization policy is consistent w.r.t. the set of inference rules, in other words when Algorithm 3 returns an empty set. We illustrate this methodology on the inference rules of Example 2.1.16 (P. 22) and the policy defined in Table 3.1 (P. 47) with syntactical order. After three iterations, no inconsistency subsists anymore. The complete policy once corrected is given in Table 4.1.

Run

The first run points out the fact that triples with predicate rdf : type are forbidden by the default authorization a 9 , but they can be deduced by rule RDom. Figure 4.3a depicts a counterexample generated from RDom, positive authorizations a 7 , a 1 and the negative universal authorization a 9 . Since most of rdf : type predicates information should be public for integration purposes, we add a new authorization a 8 that grants access to triples with predicate rdf : type. a 8 is added after a 8 so that the triples with predicate rdf : type will be granted except those which object is : Cancerous.

A second run points out that triples of the form (X; rdf : type; :Cancerous) can be deduced by rule RDom since triples (Y ; rdfs : domain ; :Cancerous) are accessible.

Figure 4.3b depicts a counterexample generated from RDom, positive authorizations a 7 , a 1 and negative authorization a 2 , i.e. B = {(?x ; :hasTumor ; ?y), (: hasTumor ; rdfs : domain ; :Cancerous), (?x ; rdf : type ; :Cancerous)}. Note that the triple (: hasTumor ; rdfs : domain ; :Cancerous) has been granted because its applicable authorizations are a 7 and a 8 , and ch chose the first applicable one which is the positive authorization a 7 . To remove such source of inconsistencies, one can switch the order of a 7 and a 8 , denying access to (Y ; rdfs : domain ; :Cancerous). After switching the two authorizations, at the next run, the Algorithm constructs the same BGPs but it does not insert them into the set of counterexamples. For instance, the BGP B of Figure 4.3b will be constructed at line 8 but the test at line 9 will not succeed since (: hasTumor ; rdfs : domain ; :Cancerous) is denied by a 8 , thus it does not belong to (Cl R (B)) + P .

Note that even the counterexamples generated by the Algorithm 3 are valid RDF graphs, they may be inconsistent w.r.t a given vocabulary. For instance, the counterexample depicted by Figure 4.3c, states that : treats domain is : Cancerous, whereas in our RDFS vocabulary the triple et 1 in Figure 2.4 states that it is the domain of : hasTumor. As handling vocabularies is out of the scope of this thesis, we will discuss this issue and possible solutions in Chapter 7.

We give more details about the third run that produces a single counterexample graph depicted by Figure 4.4, i.e. B = {(?d ; :service ; ?s), Table 4.1: Corrected authorization policy a 1 = GRANT(?p ; :hasTumor ; ?t) a 2 = DENY (?p ; rdf : type ; :Cancerous) a 3 = GRANT(?d ; :service ; ?s) a 3 = DENY (?d ; :treats ; ?p) WHERE {(?d ; :service ; ?s), (?s ; rdf : type ; :Oncology)} a 4 = GRANT(?d ; :treats ; ?p) a 5 = DENY (?p ; :admitted ; ?s)

WHERE {(?s ; rdf : type ; :Oncology)} a 6 = GRANT(?p ; :admitted ; ?s) a 8 = DENY (?s ; ?p ; :Cancerous) a 7 = GRANT(?p ; rdfs : domain ; ?s) a 8 = GRANT (?x0 ; rdf : type ; ?x1) a 9 = DENY (?s ; ?p ; ?o) Figure 4.4: Counterexample constructed from RAdm and {a 3 , a 4 , a 5 } (?d ; :treats ; ?p), (?p ; :admitted ; ?s), (?s ; rdf : type ; :oncology)} which involves the rule RAdm together with authorizations a 3 , a 4 and a 5 . A first and simple solution would be to change the effect of authorization a 4 to deny access to triples matching (?d ; :treats ; ?p). However, such an authorization would be extreme while the counterexample suggests to add a finer authorization a 3 just before a 4 . a 3 denies access to triples of doctors treating patients only if they work in an oncology service. Note that we can alternatively switch (?d ; :treats ; ?p) and (?d ; :service ; ?s) in a 3 , but such a choice should be discussed with domain experts first. After adding a 3 , a final execution of the algorithm confirms that the new policy is consistent w.r.t {RDom, RAdm} as it returns no counterexample.

Another way of using the counterexamples is to keep the policy unchanged, but to check if they occur in the actual closed graph managed by the RDF store. By Theorem 4.3.2, if there is no such instance, no inference leakage will occur. Thus, one could use each B produced by Algorithm 3 as an integrity constraint in the RDF store, thereby reject updates that may lead to inference leakage.

In order to guarantee the absence of inference leakage, one has to add such an integrity constraint for every graph pattern in the output of Algorithm 3.

Consider the aforementioned counterexample of Figure 4.4, this means that no leakage corresponding to a 5 and resulting from a 3 , a 4 and RDom will occur. However, in case of a high number of counterexamples, this approach may burden the query evaluation.

Conclusion

In this chapter we formalized an inference leakage problem that arises when inferred triples are computed out of the RDF store by a (potentially) malicious user. We showed that, whenever the inference system can be expressed in a set of Datalog-like rules without negation, this property can be statically verified at the time of writing the authorization policy without the need of a base graph. Note that OWL2RL, an OWL profile, can also be statically verified since it is described as a collection of positive Datalog rules [START_REF] Kolovski | [END_REF]]. We proposed a correct and complete algorithm which generates a set of counterexample patterns in case the policy presents an inference leakage problem. We showed how these counterexamples could be used by the administrator to fix the policy or as integrity constraints of the base graph. We did some experiments with the implemented Prolog program, using RDFS rules and a set of authorizations. The experiments showed that some RDFS inference rules which have only variables in the premises, cause the generation of several counterexamples, since the premises are unifiable with any authorization's head. One of these rules is :

(?x ;?y ;?z) (?x ;rdf:type ;rdfs:Resource) . It caused the generation of many counterexamples since in the set of our authorizations, we did not grant access to triples which object is rdfs : Resource, and they were denied by default by the universal authorization. Since this kind of triples does not need to be private, adding a grant authorization that gives access to them, reduced considerably the number of counterexamples. In Chapter 3 we defined AC4RDF, a fine grained access control model for RDF which semantics are defined by means of positive subgraph from the base graph. The AC4RDF policies are defined for a given requester and we mentioned that the upstream mapping from requesters to authorizations may use any model from the literature. In this chapter we propose a high level access control language which allows the definition of high level global policies which are then compiled to AC4RDF policies to be enforced. We choose to define our policies on the basis of the user's attributes following the Attribute Based Access Control (ABAC) which allows a much more fine-grained access control approach combining not only user attributes but other environment information, such as location and time. First we define the main components of the proposed solution then we give the syntax and semantics of a XACML-like policy language. Policies are defined by trees where nodes represent policies, the leaves represent authorizations and edges represent targets. A target defines certain conditions to determine whether this policy is applicable to a user's request. Finally, we show how the user's policy is generated and enforced. [START_REF] Costabello | [END_REF]] proposed an attribute based access control at named graph level. The intercepted user query is rewritten with respect to the user's attributes by adding the accessible named graphs to the query which is then evaluated on the dataset. Similarly, [Abel 2007] proposed a query rewriting technique. The user attributes are first bound boolean expressions. If it is evaluated to true, then the query is expanded using policies and evaluated over the dataset. The drawback of this kind of approaches is that they depend on the query language. [Reddivari 2005] proposed a language in which policies are based on user's attributes that are modeled as RDF triples and stored in the RDF store. They gave examples on static attributes such as allow A to see the salary of B if A is the supervisor of B. They did not mention how to treat dynamic attributes such as time and position. [START_REF] Lopes | [END_REF]] proposed a model where triples are annotated with non-recursive Datalog with negation programs which evaluation determines the access permission to the triple given a specific set of attributes.

In this chapter we give the syntax and the semantics of the language that allows the definition of global policies. We define a XACML-like language which allows to describe global policies. Our intuition is to represent the policy in Tree structure where the intermediate nodes represent policies, the leaves are authorizations and nodes edges are labeled with targets representing attribute based conditions. To illustrate, consider the following example.

Example 5.0.1 Suppose we want to protect RDF data about patients and their medical records. The hospital policy rules state that:

• R 1 : The administration staff can access all information about patients during working time only.

• R 2 : The administration staff can access all information in the medical records during working time, except the patient's disease.

• R 3 : Doctors and nurses can access medical records except those belonging to patients admitted to oncology.

• R 4 : Doctors working in oncology service can access medical records of patients admitted to oncology service.

• R 5 : Doctors and nurses can access medical records belonging to patients admitted to oncology only if the patient is in critical condition.

First we translate the objects and conditions of the above rules by means of authorizations and targets. R 1 is translated by one authorization a 4 which grants access to all the patient's information. R 1 has two conditions, the user must belong to the administration staff which is translated by target T admin staff and the access must be at working time, translated by target T work time . R 2 is translated by two authorizations a 1 and a 3 . a 1 grants access to all information in medical records. a 3 is an exception of a 1 since it denies access to disease name in the medical record. R 2 has the same conditions as R 1 . R 3 is translated by authorizations a 1 and a 5 . a 5 is an exception of a 1 that denies access to medical records of patients admitted to oncology. R 3 condition is that the user must be a doctor or a nurse, translated by target T doc∨nurse . R 4 is translated by authorization a 2 which grants access to medical records of patients admitted to oncology. R 4 condition is that the user is a doctor working in oncology, translated by target T doc∧onc . R 5 is translated by authorization a 6 which is an exception a 5 that grants access to medical records of patients admitted to oncology and who are in critical condition. R 5 has the same conditions as R 3 . Figure 5.1 depicts the above policy in a tree data structure.

P • P 0 • P 1 • a 4 a 3 a 1 P 2 • a 2 P 3 • a 1 a 6 a 5 a u T admin staff

System architecture

As shown in Figure 5.2, our solution has three main components:

• Policy Enforcer intercepts the user query Q and attributes rq and returns the result Q G + to the user.

• User Policy Generator is responsible for the constitution of the user policy (A s , ch) using the user's attributes sent from the Policy Enforcer.

• AC4RDF receives the user's policy and her/his query from the Policy Enforcer and answers with the result of the query over the user's positive subgraph.

The Policy Enforcer is a simple component which plays the role of interconnection between the user, the User Policy Generator and AC4RDF. AC4RDF was defined in Chapter 3 where we showed how the user positive subgraph is computed from the base graph using a user policy. The User Policy Generator allows to construct a user policy using her/his attributes and a Global Policy.

Language syntax and semantics

To formally define the semantics of our language and reasoning on it, we provide a syntax of our formalism through the Extended BNF (EBNF) grammar in Table 5.1. "*" (The Kleene Star) means 0 or more occurrences, whereas "+" (The Kleene Cross) means 1 or more occurrences. Note that Auth, OP, Key and Value are pairwise disjoint.

Abstracting Policy Components

The global policy is made of multiple components which are defined as follows:

Request is the component used to query the GPolicy to get the necessary information about policies that are applicable to the user. The latter represents the entity requesting to perform an operation upon the policy objects, and is characterized by attributes. In our language we define attributes as a pair (Key, Value) where Key specifies the attribute's name such as user-id, date of birth, home address, job function . . . , and Value specifies the value. A user request is defined by a list of pairs (Key, Value). The evaluation of a request over a GPolicy amounts to compare the Key and the Value according to the criteria defined in GPolicy, more precisely in the Target. In other words the Request component represents meta-data of the user, and not the action she/he wants to execute. Note that the attributes authenticity is out of the scope of this thesis. Several mechanisms exist to handle attributes authenticity such as attribute certificate [Farrell 2002]. GPolicy is the main component of our formalism and it is the root of all policy components. A GPolicy can be an atomic authorization or a list of pairs of targets and child policies which themselves belong to GPolicy.

Auth is the atomic component which represents the policy authorizations, on which we do not need to have details. In this chapter, we use authorizations of the AC4RDF model defined in Section 3.1.1 (P. 46). On the other hand, other kind of authorizations may be used instead of Auth. Indeed, our model can be used to define upstream policies in order to generate authorizations that are processable by other models such as [Flouris 2010], which makes the solution modular.

Target is the component which reflects the needed conditions under which a GPolicy is applicable. It is defined as a propositional logic formula which is evaluated using the user attributes to check whether the targeted policy is applied or not to the user. The formula uses logical connectors (∨, ∧, ¬) between atoms (Atom).

OP is a binary operator used in the Atom definition to compare keys and values. Operators may be mapped to arithmetic operators such as = . , ≤ . , < . , > . and , ≥ . . ), ( , a u )] P 0 = [(T admin staff , P 1 ), (T doctor∨nurse , P 2 )] P 1 = [( , a 4 ), (T work time , a 3 ), (T work time , a 1 )] P 2 = [(T doctor∧onc , a 2 ), ( , P 3 )] P 3 = [( , a 1 ), ( , a 6 ), ( , a 5 )] Targets T admin staff = (role = . admin staff) T doctor∨nurse = ((role = . doctor) ∨ (role = . nurse)) T work time = ((time ≤ . "17 : 00") ∧ (time ≥ . "08 : 00")) T doctor∧onc = ((role = . doctor) ∧ (service = . onc))

Authorizations a 1 = GRANT (?r ; ?x ; ?y) WHERE {(?p ; :hasRec ; ?r)} a 2 = GRANT (?r ; ?x ; ?y) WHERE {(?p ; :hasRec ; ?r), (?p ; :admitted ; :onc)} a 3 = DENY (?r ; :disease ; ?d) WHERE {(?p ; :hasRec ; ?r)} a 4 = GRANT (?p ; ?x ; ?y) WHERE {(?p ; rdf : type ; :Patient)} a 5 = DENY (?r ; ?x ; ?y) WHERE {(?p ; :hasRec ; ?r), (?p ; :admitted ; :onc)} a 6 = GRANT (?r ; ?x ; ?y) WHERE {(?p ; :hasRec ; ?r), (?p ; :admitted ; :onc), (?p ; :condition ; "CRITICAL")} a u = DENY (?x ; ?y ; ?z) as well as a u , are targeted to any user. P 0 has two child policies namely: P 1 and P 2 . P 1 is targeted if the user belongs to the administration staff (T admin staff ) and P 2 if the user is a doctor or a nurse (T doc∨nurse ). P 1 is defined by three authorizations a 1 , a 3 and a 4 . a 1 and a 4 are applied at working time only (T work time ), whereas a 3 is always applied. P 2 is targeted if the user is a doctor or a nurse (T doctor∧onc ). P 2 has two child policies namely the authorization a 2 and the policy P 3 . a 2 is applied if the user is a doctor whose service is onc (T doctor∧onc ), whereas P 3 is applied for everyone, i.e. doctors and nurses. P 3 targets three authorizations a 1 , a 6 and a 5 for any user.

After defining the syntax of our high-level language for an attribute based access control, we show, in the next section, how are the user requests evalu-ated over policies. To define the evaluation we use the notation x , where x represents the name of the evaluation function.

Targets evaluation over user requests

As mentioned above, the user request represents a set of key/value pairs that are used to determine her/his applicable policies. This is done by the evaluation of targets on the request. As a target is made of atoms, and the latter are made of keys and values, we start by showing the evaluation of keys/values on a user request, followed by the evaluation of atoms, and finally we show how targets are evaluated. OP is interpreted as a function that compares two values with the arithmetic operator ≥.

Atom Evaluation : An atom is made of a binary operator op and a couple of keys or a key and a value. We define a function Atom that checks whether an atom matches a request. To evaluate an atom, any key and value in the atom is transformed to two sets of values using KV and the user request. The result sets are then compared by checking whether there exists a couple of values, in their Cartesian Product, that are evaluated to true using the atom operator. Let k, k 1 , k 2 ∈ Key, v ∈ Value, rq ∈ Request and op be a predicate in OP.

Atom : Atom × Request → Boolean is defined as follows:

k op v Atom (rq)= ∃v 1 ∈ k KV (rq), ∃v 2 ∈ v KV (rq); v 1 op OP v 2 k 1 op k 2 Atom (rq)= ∃v 1 ∈ k 1 KV (rq), ∃v 2 ∈ k 2 KV (rq); v 1 op OP v 2
Example 5.2.5 Consider the requests rq 0 and rq 2 defined in Example 5.2.1.

The atom (role = . doctor) is evaluated on rq 0 as follows :

(role = . doctor) Atom (rq 0 ) = ∃v 1 ∈ {doctor, admin staff}, ∃v 2 ∈ {doctor}; v 1 = v 2 = true
The atom (role = . nurse) is evaluated on rq 2 as follows :

(role = . nurse) Atom (rq 2 ) = ∃v 1 ∈ {nurse}, ∃v 2 ∈ {nurse}; v 1 = v 2 = true
In this case, the interpretation of = . is string equality. The results of role KV (rq 2 ) and nurse KV (rq 2 ) are obtained by applying (Key, Value) evaluation which returns nurse for both key and value. Hence the atom is evaluated to true.

Target Evaluation : The global policy targets are evaluated over user requests to check whether or not the targeted policy is applicable to the user. To evaluate Target, we use the propositional logic based on (Key,Value) structure. We define the function TR : Target × Request → Boolean which checks whether a target matches a given request. Let t, t 1 , t 2 be a Target elements, rq be a Request and at be an Atom. Then, the evaluation of Target is as follows :

t 1 ∧ t 2 TR (rq)= t 1 TR (rq) ∧ t 2 TR (rq) t 1 ∨ t 2 TR (rq)= t 1 TR (rq) ∨ t 2 TR (rq) ¬t TR (rq)= ¬ t TR (rq) at TR (rq)= at Atom (rq) TR (rq)= true
Target component can be expressed in several forms of propositional logic using logical connector ∨, ∧, ¬ with usual semantics. We evaluate each Atom which is the smallest component of Target component, using Atom defined in 5.2.2, then, we combine its results using the classical propositional logic evaluation.

is always evaluated to true.

Example 5.2.6 Consider the target T doctor∧onc in Table 5.2, and the request rq 0 in Example 5.2.1. The evaluation of rq 0 over T doctor∧onc is performed as follows:

((role = . doctor) ∧ (service = . onc)) TR (rq 0 ) = (role = . doctor) Atom (rq 0 ) ∧ (service = . onc) Atom (rq 0 ) = true ∧ true = true.

Using the Atom evaluation defined in Section 5.2.2, and the truth table of logical connector ∧, the function will return true. In other words T doctor∧onc matches rq 0 .

User policy generation

In this section, we show how does the User Policy Generator proceed to construct a user policy. Our purpose is to define a global policy which is queried by user requests to finally generate the pair (A s , ch) that will be processed by AC4RDF. In our illustrative examples, we will suppose that a nurse is requesting access to the triplestore. We will use the request rq 2 = {(role, nurse)} of Example 5.2.1.

The first step of policy evaluation consists in computing the user's applicable authorizations. This is done by computing the user's subpolicy according to her/his attributes. The authorizations are computed with respect to the user subpolicy tree by performing a depth traversal of the tree and selecting the leaves i.e. authorizations. The next step consists in selecting a ch function that will be used to resolve conflicts. Figure 5.3 illustrates the user policy generation steps.

User SubPolicy

The first step involves the generation of the user subpolicy represented by a subtree of the global policy tree according to the user attributes given in a request. The subtree is generated by traversing the global policy tree in depth, Figure 5.3: User policy generation and keeping the nodes connected by edges tagged with targets which match the user attributes found in the request. The user policy evaluation is given by the function uPol : Request × GPolicy → GPolicy which maps a recursive policy to a recursive policy according to a given Request rq. uPol is defined as follows:

uPol(rq)(a) = a uPol rq [(t 0 , p 0 ), . . . , (t n , p n )] = t i , uPol(rq)(p i ) | t i TR (rq)
uPol starts from the root policy and performs a recursive traversing of the global policy tree returning a subpolicy tree in which edges are labeled with targets evaluated to true using the user request.

Example 5.3.1 Suppose a nurse is requesting access over the policy P defined in Table 5.2. Her request is translated by rq 2 of the Example 5.2.1. uPol will give the following subpolicy tree illustrated by Figure 5.4: P = [( , P 0 ), ( , a u )] P 0 = [(T doctor∨nurse , P 2 )] P 2 = [( , P 3 )] P 3 = [( , a 1 ), ( , a 6 ), ( , a 5 )]

User authorizations selection

Before showing how to select the user subset of authorizations A s of the pair (A s , ch), we need to define a function that returns the authorizations of a given policy, in other words it returns all the leaves of the policy tree.

leaves : GPolicy → P(Auth) is the function which maps a recursive policy to a set of authorizations. The function performs a depth first traversing of the tree and returns the leaves (authorizations). leaves is defined as follows : leaves starts from the root policy and makes a recursive call for all child policies. If the policy passed as parameter is not an authorization, then all its child policies are aggregated, whereas if it is an authorization, then it will be returned. Now we have all the ingredients to define the function uAuth which returns the authorizations for a given user request. The function is constructed by the composition of the two functions uPol and leaves. In other words uPol is applied first to get the user policy, then leaves is applied on the resulted policy to get the user authorizations. Formally uAuth : Request×GPolicy → P(Auth) is defined as follows:

P • P 0 • P 2 • P 3 • a 1 a 6 a 5 a u T doc∨nurse
rq uAuth (p) = leaves • uPol (rq, p)
uAuth generates the set of user authorizations A s of the pair (A s , ch) which will be sent to AC4RDF to be enforced. Remind that the user's policy (A s , ch) must respect the Totality well-formedness condition by the requirement that A s must contain a universal authorization a u (Lemma 3.2.2 (P. 54)). For simplicity, a u is assumed to be unique (Assumption 3.2.3 (P. 55)). Hence uAuth result must contain a u for any user's request. To achieve this condition, the root of the global policy should have a child policy a u with a target which is always evaluated to true. That way, a u will take part of the result of any user's request.

Example 5.3.2 Consider the last example 5.3.1 where we applied uPol to get the user policy. To select the user's authorizations, the function uAuth applies leaves on the result of uPol shown in Figure 5.4 as follows:

leaves(P)= leaves(P 0 ) ∪ leaves(a u ) = leaves(P 2 ) ∪ {a u } = leaves(P 3 ) ∪ {a u } = {a 1 , a 6 , a 5 , a u }
After receiving a user's request rq over the global policy P from the Policy Enforcer, the User Policy Generator answers with the user's policy ( rq uAuth (P), ch). ch is parameter that represents the conflict resolution function presented in Section 3.2 (P. 53). In practice, ch parameter can be the name of the Java class that implements the function. The Policy Enforcer sends the received couple ( rq uAuth (P), ch) as well as the user query Q to AC4RDF to be enforced. Finally, AC4RDF evaluates the query over the positive subgraph, and the result is sent back to the user. The following is an example of how AC4RDF generates the nurse positive subgraph.

Example 5.3.3 Following our examples where a nurse is requesting access, the User Policy Generator answers to the Policy Enforcer with the user policy {a 1 , a 6 , a 5 , a u }, ch where ch applies the MSTP strategy. Consider the following closed graph G where every triple is assigned the set applicable authorizations belonging to the user nurse:

Subject Predicate Object ar(Cl(G), A s )(et i ) ch et 1 : alice : hasRecord : r1 {a u } a u et 2 : chuck : hasRecord : r2 {a u } a u et 3 : r1 : disease : d1 {a 1 , a 5 , a u } a 5 et 4 : r2 : disease : d2 {a 1 , a u } a 1 et 5 : alice : admitted : onc {a u } a u
Since we want to apply MSTP strategy, a total order will be computed using Algorithm 2 which will give the following result : [a 3 , a 4 , a 6 , a 2 , a 5 , a 1 , a u ].

The triple et 3 is about record : r1 which belongs to the patient alice who is admitted to oncology, hence it should not be granted to nurses. For the user nurse, the set applicable authorizations to et 3 is : ar(G, A s )(et 3 ) = {a 1 , a 5 , a u }. ch function will select the smallest authorization a 5 . Thus et 3 will be denied as stated by the policy. By applying a similar processing on all triples in G, we obtain G + = {et 4 }. The policy states that doctors working in oncology service should be granted access to triple et 3 . In case a doctor working in oncology requests access to G, the generated user policy is {a 1 , a 2 , a 6 , a 5 , a u }, ch . The set of applicable authorizations to et 3 is ar(G, A)(et 3 ) = {a 1 , a 2 , a 5 , a u }. ch function will select the smallest authorization a 2 and et 3 will be granted.

Conclusion

In this chapter we gave the syntax and semantics of an expressive high level language which allows the definition of global policies for multiple users. The global policies are defined by means of trees which intermediate nodes represent other subpolicies and leaves represent authorizations. Subpolicies are accessible through targets which represent conditions over the user's attributes that allow to check whether or not a policy is applicable to the user. The users' requests are evaluated over global policies by the User Policy Generator which constructs the user policy. The latter is then enforced by AC4RDF which generates a positive subgraph, over which the user's query is evaluated.

Note that we have a global policy from which we computed a part that depends on the user's request (A s ), and a second part that does not depend on the user's request (ch). Hence it is fixed and could be coded in the RDF store once and for all for performance reasons. Then, to link the two parts, it suffices to make an and between the user's authorizations and those applicable to the triple. In the next chapter, we propose an enforcement approach for AC4RDF model where every triple t in the base graph is annotated with a subset of the global policy authorization set, representing the applicable authorizations ar(Cl(G), A)(t). Since the triples are already annotated with their applicable authorizations of the global policy, an upstream operation is needed before applying ch. In fact, given a triple t, ch must be applied on the authorizations applicable to the triple which are also assigned to the user, formally A s ∩ ar(Cl(G), A)(t). As mentioned in Chapter 3, AC4RDF model semantics are defined with the set of authorizations that belongs to the current subject. In a multi-subject policy context with a set of authorizations A, a subset A s ⊆ A of authorizations is associated to each subject s who executes a (SPARQL) query. In the previous chapter, we showed how this association could be performed using an attribute based approach to generate the subject's policy (A s , ch). The latter is then enforced by AC4RDF which computes the positive subgraph of the authenticated subject. In this chapter, we show how to enforce multi-subject policies using a data-annotation approach. The idea is to materialize every triple's applicable authorizations of the global policy, into a bitset which is used to annotate the triple. The base graph G is materialized into a graph G A by annotating every triple t ∈ G with a bitset representing ar(G, A)(t) ⊆ A. The subjects are similarly assigned a bitset which represents the set of authorizations assigned to them. When a subject sends a query, the system evaluates it over the her/his positive subgraph computed by AC4RDF. We start by giving the semantics of the enforcement approach, then we give the implementation details with experiments.

Policy enforcement

As we mentioned in Section 2.3.1 (P. 35), the policy enforcement may be classified into pre-processing, post-processing or annotation-based. The advantage of the pre-processing approaches such as query rewriting techniques, is that the policy enforcer is independent from RDF data. In other words, any updates on data would not affect the policy enforcement. On the other hand, this technique fully depends on the query language. In the post-processing approaches, the query response time may be considerably longer since policies are enforced after all data (allowed and not allowed) have been processed. In the annotation approach, since the triples are already annotated with the access information, only the triples with a grant access can be used to answer the query. On the other hand, any updates in the data would require the re-computation of annotations. Some works [START_REF] Papakonstantinou | [END_REF]] support incremental re-computation of the annotated triples after updates.

To enforce AC4RDF model, we use a data-annotation approach which materializes the applicable authorizations in an annotated graph denoted by G A . The latter is computed once and for all subjects at design time. The subjects queries are evaluated over the annotated graph with respect to their assigned authorizations. As illustrated by Figure 6.1, the triple's applicable authorizations as well as the subject's assigned ones are encoded into bitsets over which a logical and is performed to check whether the triple is authorized or not. In the following, we show how the base graph triples are annotated then we show how the subjects queries are evaluated.

Graph annotation

From a conceptual point of view, an annotated triple can be represented by adding a fourth component hence obtaining a quad. From a physical point of view, the annotation can be stored in the graph name of the SPARQL dataset (Definition 2.1.11 (P. 20)). To annotate the base graph, we use the graph name IRI of the dataset to store bitsets representing the applicable authorizations of each triple. Doing so, we do not need extra mechanisms to enforce our model, in contrast to other approaches which use specific language to interrogate the annotated triples [START_REF] Lopes | [END_REF]]. Given a set of authorizations A, each triple in the base graph is annotated with a bitset of size |A| in which the bits set to one are those in the position of the syntactical order of the authorizations applicable to the triple. In other words, given an authorization a i in the input set, the i-th bit is set to 1 in the generated bitset. First we need a bijective function authToBs which maps a set of authorizations to an IRI representing the bitset. authToBs -1 is the inverse function of authToBs.

Next we define a function arsg which takes a set of authorizations A and a graph G, and returns the subgraph containing triples which the set of applicable authorizations is A . The function arsg is formally defined as follows:

arsg

(A , G) = {t ∈ G | ar(G, A)(t) = A } Example 6.1.1 Consider the
}) = 100000001 arsg({a 9 }, Cl(G 0 )) = {et 2 , et 3 , it 3 }
Now we are ready to define the annotated graph represented by a dataset (Definition 2.1.11): a set of named graphs in which the name is the binary encoding of A and the graph is the nonempty set of triples arsg(A , G). Definition 6.1.2 (Annotated graph) Given a set of authorizations A and a graph G ∈ BGP, the dataset that represents the annotated graph denoted by G A , is defined as the following:

G A = u, arsg(A , G) | A ∈ P(A)
and arsg(A , G) = ∅ and u = authToBs(A ) Note that having A ∈ P(A) raises the problem of combinatorial explosion. This issue is discussed in Section 6.

A = { u 1 , G 1 , . . . , u n , G n }, the following properties hold: • ∀i, j ∈ 1..n : i = j =⇒ G i ∩ G j = ∅ • i∈1..n G i = G Proof In the following, we prove that ∀i, j ∈ 1..n : i = j =⇒ G i ∩ G j = ∅. We prove that ∀i, j ∈ 1..n : G i ∩ G j = ∅ =⇒ i = j. G i ∩ G j = ∅ means that there exists t such that t ∈ G i and t ∈ G j . Since t ∈ G i then u i = authToBs(ar(G, A)(t)). Similarly, since t ∈ G j then u j = authToBs(ar(G, A)(t)). Which means that u i = u j , hence i = j.
In the following we prove that

i∈1..n G i = G First we prove that ∀t ∈ i∈1..n G i =⇒ t ∈ G. ∀t ∈ i∈1..n G i means that ∃ u, G ∈ G A | t ∈ G . Since by definition, G ⊆ G then t ∈ G. We prove that ∀t ∈ G =⇒ t ∈ i∈1..n G i . Since a u ∈ A then ∀t ∈ G, ar(G, A)(t) = ∅, hence ∃ u , G ∈ G A s.t. t ∈ G . Which means that t ∈ i∈1..n G i .

User's query evaluation

Following Definition 3.1.9, given a global policy authorization set A, the positive subgraph of a subject having A s ⊆ A as applicable authorizations, is given by the following :

G + s = {t ∈ G | (effect • ch • ar(G, A s )(t) = +}.
Since we materialized the set of applicable authorizations in G A , we need to define the subject's positive subgraph from the graph annotation, more precisely from ar(G, A). The following lemma shows that ar(G, A s ) can be computed from A s and ar(G, A). Lemma 6.1.5 Given a graph G, a set of policy authorizations A and a subset of subject authorizations A s , the following holds for any t ∈ G:

A s ∩ ar(G, A)(t) = ar(G, A s )(t) Proof By Definition 3.1.3 (P. 47), ar(G, A)(t) = {a ∈ A | ∃θ ∈ hb(a) G .t = (head(a))θ}, hence A s ∩ ar(G, A)(t) = {a ∈ A s ∩ A | ∃θ ∈ hb(a) G .t = (head(a))θ}. Since A s ⊆ A then A s ∩ A = A s . Which means that A s ∩ ar(G, A)(t) = {a ∈ A s | ∃θ ∈ hb(a) G .t = (head(a))θ} = ar(G, A s )(t).
Similarly to the triples, subjects are assigned bitsets representing authorizations applicable to them. If a subject authorization set is A s , then he is assigned the bitset ubs where the i-th bit is set to one if a i ∈ A s . Example 6.1.6 Given the set of authorizations A in Table 3.1 (P. 47) Eve is a nurse who can see the patients having tumors (a 1 ) and which service the patients are admitted to (a 6 ). She is denied anything else (a 9 ). Her assigned bitset is the following: 100001001. Dave belongs to the administrative staff, he can access doctors services assignment (a 3 ) and the patients they treat (a 4 ). He is denied anything else (a 9 ). His assigned bitset is the following: 001100001.

Once the graph is annotated, it is made available to the subjects with a filter function which prunes out the inaccessible triples given the subject's authorization set. In other words, the filter function returns the subjects's positive subgraph by applying the ch function on the subject's assigned authorizations ar(G, A s )(t). We showed in Lemma 6.1.5 that this subset can be obtained from the applicable authorizations in G A by computing a bitwise logical and (denoted by & ) between the subjects' bitsets and triples' bitsets, as illustrated in Figure 6.1. Jena TDB is a native RDF store which allows to store and query RDF triples. Jena TDB follows the SPARQL standard by supporting quads that are stored in datasets. Jena provides rules engines to derive additional RDF triples from those that are explicitly defined. To be able to support inference, our access control model needs a forward chaining reasoner. In the presence of inference, both explicit and implicit triples will be annotated which means that the closure of the base graph is computed before the annotation operation. To generate G A , the dataset of annotated triples, we use SPARQL CONSTRUCT queries to obtain authorizations scopes (see Definition 3.1.5 (P. 48)). An authorization a is transformed into Q a = CONSTRUCT head(a) WHERE hb(a). We use an in-memory hash map in which we store the ids of the triples and the correspondent bitset. For every authorization a i , a CONSTRUCT query Q a i is run over the raw dataset, and the result triples are added/updated to the hash map with the bit i set to 1. Once the hash map computed, it is written into a dataset which represents G A . Note that we could have used the dataset directly instead of a hash map, but this would be time consuming due to the high number of disk accesses. During query evaluation, on the fly filtering is applied to the accessed triples. Jena TDB provides a low level quad filter hook3 that we use for implementation. For each accessed quad, let u be the quad's graph IRI, t its triple and ubs be the subject's bitset. A bitwise logical and is performed between (the bitset represented by) u and ubs. The ch function on the authorizations obtained by authToBs -1 is then applied in order to allow or deny access to t. If t is allowed, then it is transmitted to the ARQ engine to be used by query Q. Otherwise, it will be hidden to the ARQ engine. An in-memory cache is used to map quad graph IRIs to grant/deny decisions in order to speedup the filtering process. Algorithm 4 illustrates the quad filter function integrated to Jena TDB to filter the triples.

Experiments

The key input factors for the benchmarking of our solution are the sizes of the base graphs, the sizes of the access control policies, the sizes of positive subgraphs, the sizes of users policies and the user queries. The factors are reported in

Static performance

We distinguish the time needed to compute G A between the time required for its building and the time required for its writing. The time to build the authorization bitset ar(G, t) associated with each triple t ∈ G in memory is referred to as t A in Table 6.3. The time to write the annotated graph G A from the memory to the quad store is referred to as t W in Table 6.3. Figure 6.2 shows t A and t W with |A| being set to 100 authorizations. Figure 6.3 shows t A and t W with |G| being set to 1,591k triples. As each a ∈ A is mapped to a SPARQL CONSTRUCT query, the results show that t A grows linearly when |G| or |A| gets bigger. The annotation time is not negligible but we argue that it is not an issue: G A is computed once, as long as A is not modified. Figure 6.3 shows that t A grows linearly when |A| grows. However, as expected, the results show that t W is independent of |A| : the overhead incurred by the growing size of the bitsets is negligible for |A| ∈ {50, 100, 150, 200}. On average, the annotated graph G A requires 50% more space than G.

Dynamic performance

To evaluate the performance of our solution at runtime, we compare our approach to two extreme methods. Each method computes the positive subgraph G + obtained from the base graph G according to a set A of authorizations.

The first extreme (naive) method gives an upper bound on the overhead incurred by the filtering process. Indeed, in the post-processing approaches, the access control consists in two steps : (1) compute the full answer Q(G) and (2) filter out denied triples from Q(G) as a post-processing step. This method avoids duplication of the base graph G at the price of high overhead at runtime. In our experiments, we considered the step (1) only, by computing the full answer Q(G). We refer to this method as t G in Table 6.3.

The second extreme method gives a lower bound on the overhead incurred by the filtering process. The idea is to materialize G + for each user profile and then compute Q(G + ). We refer to this method as t G + in Table 6.3. This method avoids the filtering post-process at the price of massive duplication and storage overhead, as a graph is materialized for each user profile. In contrast, our approach, namely t G A in Table 6.3, is a trade-off between the extreme ones: it needs some static computation while offering competitive runtime performance. Our results are shown in Figure 6.4 for varying sizes of |G| with |A| and |A s | set to 100, and |G + | |G| set to 40%. The user's query Q s is set to the worst case which is the select all query.

The key insight from these experiments is that the overhead is independent from |G| and is about 50%.

Another advantage of our approach is its independence from the number of authorizations of both the policy and those assigned to the user. In In Figure 6.8 we run experiments on our system with a subset of LUBM test queries used by [Atre 2010], with |A| and |A s | set to 100, and |G + | |G| set to 40%. We computed the LUBM queries evaluation times and repeated the experiments 100 times. Q1 and Q3 are more complex queries having a high number of initial triples associated with the triple patterns, but the final number of results is quite small (28 and 0 respectively). For these queries, the initial selectivity of the triple patterns and selectivity of the intermediate join results were quite low, but together they gave highly selective results (these queries have cyclic dependency among join variables). Figure 6.8 shows that the time to evaluate query Q3 in presence of the filter t G A is smaller than the evaluation time over materialized positive subgraph t G + . The reasons could be the empty result of Q3 or different execution plans.

Conclusion

In this chapter, we proposed an enforcement framework to the AC4RDF access control model. We used a data annotation approach where the base graph is annotated at the policy design time. Each triple is annotated with a bitset representing its applicable authorizations. The subjects' queries are evaluated over their positive subgraph constructed using her/his bitset and the triples' bitset. The experiments showed that the annotation time is not negligible, but we argue that it is not an issue since this operation is done once and for all during policy design time. Moreover, in Figure 6.2 the ratio t A /t W is about 3.4 on average for fixed value of G. Which means that we need 3.4 times of the time to write the base graph to compute in-memory annotation plus the time to write the result to the disk, i.e. a total time of 4.4 times of the time to write the base graph. The materialization approach gives fast query answering, however it could lead to a massive duplication and storage overhead, as a graph is materialized for each user profile. Our method is amortized if the sum of triples in the materialized named graphs is approximatively 5 times greater then the number of triples in the base graph. We showed that the overhead of the subject query evaluation is independent from the size of the base graph, and it is about 50%. Moreover, we showed that the query evaluation is independent from the number of policy authorizations as well as the used query language since the way we implemented our access control is independent from the query language as we did not change anything on the ARQ query engine. The annotation bitset represents a combination of authorizations (Definition 6.1.2), may lead to the problem of combinatorial explosion. Theoretically, there is at most 2 |A|-1 bitsets, since the universal authorization is always applicable. However, some combinations may never happen. For instance, if a is more specific then b, then for any triple t, if b is not applicable to t then a is not applicable to t ∈ G. Hence we will never have a bitset where the position of b is set to 0 and that of a set to 1. Furthermore, some authorizations applicability may never apply at the same time. For instance, given two authorizations a and b with non-unifiable heads, then they will never apply to the same triple. Hence we will never have a bitset where the positions of a and b are set to 1. In addition, in real-life scenarios, the user is assigned a subset of authorizations, which reduces the number of combinations. In this chapter, we start by giving a summary of the contributions proposed in this thesis, namely : AC4RDF a fine-grained access control model for RDF, the static verification algorithm, the high-level attribute based language and the enforcement framework. In the next section, we discuss some limitations of the proposed solutions and we give directions for future improvements and future work.

Summary

In this thesis, we considered the problem of controlling the access to RDF data in the context of Linked Data. We started by considering the works that have been done in this research field, by defining the comparison criteria, including the expressiveness of policy specification languages, conflict resolution generated by conflicting decisions and the verification of unauthorized inferences. We found out that several criteria have not been well considered. Starting from this fact, we defined the syntax and the semantics of an access control model named AC4RDF allowing a fine grained selective disclosure of RDF data. The semantics of our model are defined by means of the positive subgraph from the base graph, on which the user query is evaluated. This makes our model independent from the query language in contrast to query rewriting techniques. As the real semantics of a graph are represented by its closure, we consider the inferred triples like the explicit ones with respect to authorization policy. In fact, our model grants/denies access to implicit triples if the policy states that it must be granted/denied to the user, in contrast to propagation approaches where some implicit triples could not be returned to the user even though the policy states that she/he is granted access to them.

We showed that inference could be used by a potentially malicious user to access forbidden information, this problem is named the inference leakage problem. A user who knows the inference rules, could use a local reasoner over her/his accessible triples, to infer triples she/he is not supposed to access. We formalized this problem into the consistency property which, if respected by the policy, ensures that denied triples can not be inferred once the data have been disclosed to the user. We showed that whenever the inference system can be expressed in a set of Datalog-like rules without negation, this property can be statically verified at the time of writing the authorization policy. We proposed a correct an complete algorithm, which, without any knowledge of the base graph, checks if a policy presents an inference leakage problem, in contrast to the works that considered such problem, on the base graph. In case of a policy inconsistency, the algorithm generates counterexample graph patterns that can be used by the administrator to fix the policy or as integrity constraints that do not allow updates leading to inference leakage.

The Attribute Based Access Control Model has shown its flexibility by allowing expressive policies based on the subject's attributes. Given the open nature of the web, we proposed the syntax and semantics of an expressive high level language which allows the definition of global policies for multiple users. The global policies are defined by means of trees which intermediate nodes represent other subpolicies and leaves represent authorizations. Subpolicies are accessible through targets which represent conditions over subject's attributes that define whether or not a policy is applicable to the subject. Subject's requests are evaluated over global policies to construct a subject's policy which is then enforced by AC4RDF to generate a positive subgraph, over which the user's query is evaluated.

To enforce our model, we proposed a data-annotation approach where we annotate every triple of the base graph with a bitset representing its applicable authorizations. Similarly, users are assigned bitsets representing the authorizations applicable to them. We proved that our encoding is correct and we gave details about the annotation process as well as the evaluation of the subject's queries. We used the graph name position to store the bitset of applicable authorization of the triple which means that no additional mechanisms are needed to enforce our model, in contrast to approaches that use specific extensions of RDF data model to store annotations. We run experiments of our solution implemented on a concrete RDF store and showed that our implementation incurs reasonable overhead at runtime (about +50%) with respect to the optimal solution which consists in materializing the user's accessible subgraph.

Discussion and future work

The solutions proposed in this thesis allow a fine-grained selective disclosure of RDF data in the context of Liked Data. Following our requirements on which our proposals were driven (Section 6.2), our future work regards the following directions :

Expressiveness

One limitation of our approach is that some real-life policies that depend on the user's profile may require the creation of several authorizations. For instance a policy may state that a doctor can access only the disease of the patients he treats. To apply this policy in the present framework, we should create an authorization for each user's profile and assign it to the user in question. We would like to extend our model with parameterized authorizations where the patterns may contain parameters in the subject or object position. To enforce the policies, the parameters are instantiated with terms which represent values of the user's attributes. For instance, the previous policy example would be translated into the authorization : a id = GRANT(?p ; :disease ; ?ds) WHERE {($id ; :treats ; ?p)}. This authorization is instantiated by replacing $id with the IRI representing the doctor's identifier. Hence, adding parameters, leads to changing the semantics of authorizations by introducing a new substitution which replaces parameters with user's attributes. This extension raises new issues related to our enforcement approach. Indeed, our enforcement solution is static, and the problem is that these parametrized authorizations are hard to deal with statically. One solution could be to consider parameters as variables in the annotation operation. However, the user query evaluation process must be extended. Indeed, the ch function may chose a parametrized authorization which once instantiated, may not be applicable to the triple. Hence all the parameterized authorizations in the subset of the triple's applicable authorizations must be dynamically instantiated with the user's attributes to check whether they are applicable or not.

We showed in Chapter 3 how to apply the Most Specific Takes Precedence (MSTP) strategy by defining the specificity relation between authorizations. We showed that this strategy has a semantic and syntactic definition. The issue is that they may no longer match when considering the inference rules. Hence, the MSTP strategy would not be fully applied, which decreases the effectiveness of the policy application. To illustrate this, consider the following two authorizations: a = GRANT (?d; :treats; ?p) WHERE {(?d; rdf : type; :Doctor)}, and b = GRANT (?d; :treats; ?p) WHERE {(?p; :condition; CRITICAL)}. By the definition of the partial order between authorizations (Definition 3.1.14), a and b are not comparable. However, if we have a vocabulary which states that : treats domain is : Doctor and its range is : Patient, then the two authorizations become semantically comparable on the closure of any graph G computed using RDFS rules (in particular rules RDom and RRan), i.e. b is more specific then a. One idea could be to translate schema triples into axiomatic inference rules R and to add them to set of inference rules R, i.e. R = R ∪ R . Definition 3.1.14 could be extended with R where an authorization a 1 is more specific than a 2 if ∃θ. Cl R (hb(a 2 ))θ ⊆ Cl R (hb(a 1 )) ∧ head(a 2 )θ = head(a 1 ). By this new definition, a and b of the above example are comparable, i.e. b is more specific then a.

We plan to extend AC4RDF with update operations. Syntactically, extending our model with updates amounts to add the operation name to the authorizations. For instance, to allow a user to insert patients' admissions, the authorization is as follows : GRANT INSERT (?p ; :admitted ; ?s). Semantically, new issues raise from updates, such as policy inconsistencies that stem from implicit insertion/deletion. Indeed, inserting/deleting a triple may lead to the insertion/deletion of other triples. Hence, an inconsistent policy may state that a user is allowed to insert a triple, but she/he she is not allowed to insert some of its consequences that can be inferred. Our static verification algorithm could be adapted to detect such policy inconsistencies by checking if the premises of an inference rule match GRANT INSERT authorizations and if its conclusion matches a DENY INSERT authorization. Triples' deletion could be treated similarly. Updates also raise a new kind of inference leakage problem linked to the so-called interference property [McLean 1990]. A user could send a write query to the system, and if the answer is negative then she/he can infer the existence of triples she/he is not supposed to read.

Verifiability

In Chapter 4 (Inference leakage problem and solution), the counterexamples are used to fix the policy manually by the administrator. Updating the policy may lead to the elimination of some counterexamples as well as the generation of new ones. The problem is that when the administrator updates the policy, she/he does not know what are the counterexamples eliminated/generated. The latter could help the administrator understand the inference leakage problem in her/his policy. We would like to improve the user interaction of the algorithm. When the administrator adds a new authorization, the next run of the algorithm finds the counterexamples affected by this new authorization. If the new added authorization effect is deny, the algorithm checks the inference rules which conclusion unifies with the head of the new authorization. The generated counterexamples from these rules are then displayed to the administrator as the impact of her/his policy modification.

Performance

Regarding the static verification Algorithm, we mentioned that the counterexamples can be used as integrity constraints. A high number of counterexamples may burden the query evaluation. Some of the counterexamples may have no sense w.r.t the application domain or w.r.t a given vocabulary. Languages such as ShEx [Prud'hommeaux 2014] enable RDF validation through the declaration of constraints on the RDF model, based on regular expressions. We plan to extend the algorithm to filter out the inconsistent graphs that do not satisfy such constraints. This would reduce considerably, the number of the generated counterexamples.

One future work direction is to optimize the annotation process using the specificity relation between authorizations. If an authorization a 1 is more specific than a 2 , then for all t in the base graph, if a 1 is applicable to t then a 2 is applicable as well. We could use this property to optimize the annotation operation since all the triples in the scope of a 1 do not need to be checked for a 2 . The annotation algorithm would be as follows : (1) compute the set mins MSTP (A) containing the most specific authorizations in A (2) for each bitset of the triples in the scope of a ∈ mins MSTP (A), set the bit of all authorizations {b | b MSTP a} to 1 (3) remove the subset mins MSTP (A) from A (4) repeat (1) to (3) until A is empty.

The issue of annotations re-computation arises when the annotated graph is updated. Instead of recomputing all the annotations after updates, we could use an incremental annotation, such that, if a triple is inserted/updated/deleted in the annotated graph, only the triples' bitsets affected by this update will be recomputed. Once a triple is inserted/updated/deleted in the annotated graph, the triples' bitsets that might be affected are those which match a pattern in the body of some authorizations. Hence, only some bits should be updated. Such an optimization would reduce the number of updates on the annotated graph.

Another issue concerns the implementation of the annotation algorithm. We used an in-memory cache to store the triples Ids and bitsets temporarily before being stored in the dataset representing the annotated graph. In case of a high number of triples that can't hold in memory, we could use a hybrid approach by loading the triples partially to reduce the disk I/O. One solution could be to select subsets from the set of authorizations A, and computing an in-memory hashmap containing annotated triples with respect to these subsets (see section 6.2 (P. 98)). Once the hashmap is computed, it is written to the disk, and another subset is selected. During the writing operation, if a triple has been already added in a previous iteration, then its bitset is updated with the result of the logical or between the old bitset and the new bitset.

  Technologie de Lyon 1 Ecole Supérieure du Professorat et de l'Education Institut de Science Financière et d'Assurances Directeur : M. F. DE MARCHI Directeur : M. le Professeur F. FLEURY Directeur : Mme Caroline FELIX Directeur : M. Hassan HAMMOURI Directeur : M. le Professeur S. AKKOUCHE Directeur : M. le Professeur Georges TOMANOV Directeur : M. le Professeur H. . le Professeur C. VITON Directeur : M. le Professeur A. MOUGNIOTTE Directeur : M. N. LEBOISNE A mes chers parents A ma chère épouse et mes adorables filles A mes frères et soeurs A la mémoire de ma grand-mère paternelle A mes amis et à la mémoire de mon ami Fares Khentout List of publications [Sayah 2015] Tarek Sayah, Emmanuel Coquery, Romuald Thion and Mohand-Saïd Hacid. Inference Leakage Detection for Authorization Policies over RDF Data. In DBSec, USA 2015 (CORE Ranking : A).

Figure 1 -

 1 Figure 1 -Diagramme du Linked Data (30/08/2014)

Figure 2 -

 2 Figure 2 -Contributions principales

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Selective RDF data disclosure . . . . . . . . . . . . . . 1.2.2 Inference leakage . . . . . . . . . . . . . . . . . . . . . 1.2.3 Enforcement and performance . . . . . . . . . . . . . . 1.3 Related work study . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 Access control model for RDF . . . . . . . . . . . . . . 1.4.2 Inference leakage problem and solution . . . . . . . . . 1.4.3 Policy administration . . . . . . . . . . . . . . . . . . . 1.4.4 Policy enforcement . . . . . . . . . . . . . . . . . . . . 2 Technical background and related work 2.1 Semantic Web . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Graph Data Model . . . . . . . . . . . . . . . . . . . . 2.2 Access control . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Access control models . . . . . . . . . . . . . . . . . . 2.2.2 Conflict resolution . . . . . . . . . . . . . . . . . . . . 2.3 Access control for RDF data . . . . . . . . . . . . . . . . . . . 2.3.1 Comparison of related works . . . . . . . . . . . . . . . vi Contents 2.4 Study summary . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Filling the gaps . . . . . . . . . . . . . . . . . . . . . . . . . . 3 A fine-grained access control model for RDF stores 3.1 Authorization policy . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Authorization semantics . . . . . . . . . . . . . . . . . 3.1.2 Policy and conflict resolution function . . . . . . . . . 3.1.3 Conflict resolution strategies semantics . . . . . . . . . 3.2 Building Policies . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Default Strategy . . . . . . . . . . . . . . . . . . . . . 3.2.2 First Applicable strategy . . . . . . . . . . . . . . . . . 3.2.3 Precedence Strategies . . . . . . . . . . . . . . . . . . . 3.2.4 Most Specific Takes Precedence (MSTP) . . . . . . . . . 3.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Inference leakage problem and solution 4.1 The inference problem . . . . . . . . . . . . . . . . . . . . . . 4.2 Consistency property . . . . . . . . . . . . . . . . . . . . . . . 4.3 Static verification . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Proof of completeness . . . . . . . . . . . . . . . . . . . 4.3.2 Understanding the Counterexamples . . . . . . . . . . 4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . architecture . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Language syntax and semantics . . . . . . . . . . . . . . . . . 5.2.1 Abstracting Policy Components . . . . . . . . . . . . . 5.2.2 Targets evaluation over user requests . . . . . . . . . . Contents vii 5.3 User policy generation . . . . . . . . . . . . . . . . . . . . . . 5.3.1 User SubPolicy . . . . . . . . . . . . . . . . . . . . . . 5.3.2 User authorizations selection . . . . . . . . . . . . . . . 5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Policy enforcement and Experiments 6.1 Policy enforcement . . . . . . . . . . . . . . . . . . . . . . . . 6.1.1 Graph annotation . . . . . . . . . . . . . . . . . . . . . 6.1.2 User's query evaluation . . . . . . . . . . . . . . . . . . 6.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Experiments . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Conclusion 7.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Discussion and future work . . . . . . . . . . . . . . . . . . . . 7.2.1 Expressiveness . . . . . . . . . . . . . . . . . . . . . . 7.2.2 Verifiability . . . . . . . . . . . . . . . . . . . . . . . . 7.2.3 Performance . . . . . . . . . . . . . . . . . . . . . . .

  Figure 1.2: Main contributions

  Web . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.1 Graph Data Model . . . . . . . . . . . . . . . . . . . . 14 2.2 Access control . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.1 Access control models . . . . . . . . . . . . . . . . . . 25 2.2.2 Conflict resolution . . . . . . . . . . . . . . . . . .

Figure

  Figure 2.1: Semantic Web Layers

  p) ∈ IP and (IS(s), IS(o)) ∈ IEXT; otherwise, I((s, p, o)) = false. Given a set of triples S, I(S) = false if I((s, p, o)) = false for some triple (s, p, o) in S, otherwise I(S) = true. I satisfies S, written as I S if I(S) = true; in this case, we say I is a simple interpretation of S. Example 2.1.5 Consider the vocabulary V = {: bob, : service, : onc, : Oncology, rdf : type}. The following is a simple interpretation I of V . IR = {a, b, c} IP = {e, f } IEXT = {e → { a, b }, f → { b, c }} IS = {: bob → a, : service → e, : onc → b, : Oncology → c, rdf : type → f } The verification of triples using I is done as follows: (IS(: bob), IS(: onc)) = (a, b) ∈ IEXT(e) = IS(: service). Hence I(: bob ; :service ; :onc) = true (IS(: onc), IS(: Oncology)) = (b, c) ∈ IEXT(f ) = IS(rdf : type). Hence I(: onc ; rdf : type ; :Oncology) = true. Thus I is a simple interpretation of S Where S = {(: bob ; :service ; :onc), (: onc ; rdf : type ; :Oncology)}

  Definition 2.1.6 (Triple Pattern, Graph Pattern) A term t is either an IRI, a variable or a literal. Formally t ∈ T = I ∪ V ∪ L. A tuple t ∈ TP = T × T × T is called a Triple Pattern (TP). A Basic Graph Pattern (BGP), or simply a graph, is a finite set of triple patterns. Formally, the set of all BGPs is BGP = P(TP). Given a triple pattern tp ∈ TP, var(tp) is the set of variables occurring in tp. Similarly, given a basic graph pattern B ∈ BGP, var(B) is the set of variables occurring in the BGP defined by var(B) = {v | ∃tp ∈ B ∧ v ∈ var(tp)}.

  Given a triple pattern tp = (s ; p ; o) ∈ TP and a substitution η such that var(tp) ⊆ dom(η), (tp)η is defined as (η(s) ; η(p) ; η(o)). Similarly, given a graph pattern B ∈ BGP and a substitution η such that var(B) ⊆ dom(η), we extend η to graph pattern by defining (B)η = {(tp)η | tp ∈ B}. Definition 2.1.8 (BGP Evaluation) Let G ∈ BGP be a graph, and B ∈ BGP a graph pattern. The evaluation of B over G denoted by B G is defined as the following set of substitution mappings:

  Example 2.1.10 shows the evaluation of a basic graph pattern.Example 2.1.10 Let B be defined as B = {(?d ; :service ; ?s), (?d ; :treats ; ?p)}. B returns the doctors, their services and the patients they treat. The evaluation of B on the example graph G 0 of Figure2.2 is B G 0 = {η}, where η is defined as η : ?d → : bob, ?s → : onc and ?p → : alice.

Figure 2

 2 Figure 2.3: Graph Pattern evaluation

Figure 2

 2 Figure 2.4: An example of G 0 closure (Cl(G 0 ))

Figure 2

 2 Figure 2.5: Security lattice example

Figure

  Figure 2.7: XACML Architecture

Figure 2

 2 Figure 2.8: XACML Request example

  Let Eff = {+, -} be the set of applicable effects. Formally, an authorization a = (e, h, b) is a element of Auth = Eff × TP × BGP. The component e is called the effect of the authorization a, h and b are called its head and body respectively. We use the function effect : Auth → Eff (resp., head : Auth → TP, body : Auth → BGP) to denote the first (resp., second, third) projection function. We call hb(a) = {head(a)} ∪ body(a) the underlying graph pattern of the authorization a. We use the concrete syntax "GRANT/DENY h WHERE b" to represent an authorization a = (e, h, b). We use the GRANT keyword when e = + and the DENY keyword when e = -. Condition WHERE ∅ is elided when b is empty. Example 3.1.2 Consider the set of authorizations shown in Table

Figure 3

 3 Figure 3.1: Authorizations applicable to it 2

  scope) Given a graph G ∈ BGP and an authorization a ∈ Auth, the scope of a on G is defined by the following function scope ∈ BGP × Auth → BGP: scope(G)(a) = {t ∈ G | ∃θ ∈ hb(a) G .t = (head(a))θ} Example 3.1.6 Consider authorization a 8 in Table

Figure

  Figure 3.2: Evaluation strategy for policies

  Let us consider the policy P = (A, ch) defined in Example 3.1.8 and the graph G 0 of Figure 2.2 (P. 16). The first step consists in computing the closure of the base graph, in this case, Cl(G 0 ) shown in Figure 2.4 (P. 23). The next steps of computing every triple decision are illustrated by columns of Table

  represents the ch function defined in Example 3.1.8, where the authorizations are ordered syntactically.

  Lemma 3.2.14 Let ns be the set of the not sorted authorizations defined as ns = {a | a ∈ A ∧ a ∈ L} Since b LEX c and c LEX b then b = c. Since an element cannot be inserted twice, i = j which contradicts i>j.

Finally

  , the obtained structure P = (A, min MSTP ) is a fully-fledged policy.

Figure

  Figure 3.3: MSTP DAG

Contents 4 . 1

 41 The inference problem . . . . . . . . . . . . . . . . . . 66 4.2 Consistency property . . . . . . . . . . . . . . . . . . . 67 4.3 Static verification . . . . . . . . . . . . . . . . . . . . . 68 4.3.1 Proof of completeness . . . . . . . . . . . . . . . . . . 70 4.3.2 Understanding the Counterexamples . . . . . . . .

  Figure 4.1: Inference leakage example

  Figure 4.2: Iterative Policy fix

  Figure 4.3: Counterexamples constructed from RDom

  syntax and semantics . . . . . . . . . . . . . 82 5.2.1 Abstracting Policy Components . . . . . . . . . . . . . 83 5.2.2 Targets evaluation over user requests . . . . . . . . . . 86 5.3 User policy generation . . . . . . . . . . . . . . . . . . 88 5.3.1 User SubPolicy . . . . . . . . . . . . . . . . . . . . . . 88 5.3.2 User authorizations selection . . . . . . . . . . . . . . 89 5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 92

  Figure 5.1: Policy Tree

Figure

  Figure 5.2: System architecture

  The following illustrates examples of requests: rq 0 = [(role, doctor), (role, admin staff), (service, onc)] rq 1 = [(role, admin stuff), (time, "09 : 00")] rq 2 = [(role, nurse)]

  Key, Value Evaluation :We first define an evaluation tool function KV : (Key ∪ + Value) × Request → P(Value). The function takes an element from the disjoint union of Key and Value as parameter, and evaluates it over the user request. If the input parameter is a Key, then KV returns the set of values corresponding to the key found in the request. If the input parameter is a value, then it returns a singleton containing this value. Formally:k KV (rq) = {v | (k, v) ∈ rq} v KV (rq) = {v}Example 5.2.4 Consider the user requests rq 0 , rq 1 , rq 2 defined in Example 5.2.1. We obtain the values of keys as follows : role KV (rq 0 )= {doctor, admin staff} service KV (rq 0 )= {onc} time KV (rq 1 )= {"09 : 00"} role KV (rq 2 )= {nurse} OP Evaluation : The function OP : OP →(Value × Value → Boolean) is an interpretation function that maps an operator in OP to a comparison function used to evaluate the atom. For instance ≥ .

Figure 5 . 4 :

 54 Figure 5.4: Nurse subpolicy tree

  Figure 6.1: Policy Enforcement

  Figure 6.2: Annotation (t A ) and writing (t W ) times

4Figure 6 Figure 6 . 4 :

 664 Figure 6.3: Annotation (t A ) and writing (t W ) times

Figure 6

 6 Figure 6.5: Query evaluation time (t G , t G A and t G + )

  Figures 6.5 and 6.6 we vary the number of policy authorizations (|A|) and user authorizations |A s | respectively, with |G| set to 1,591k triples and Q s to the select all query. The experiments show a constant overhead while changing |A| or |A s |. Regarding |G + | |G| , the size of the positive subgraph with respect to the size of the annotated graph, the experiments in Figure 6.7 show that the query answer time t G A grows linearly when |G + | |G| grows, with |G| fixed to 1,591k and |A| and |A s | fixed to 100. Q s being the select all query. This shows that the overhead w.r.t. Q(G + ) does not depend on the size of the positive subgraph. Note that t G does not vary since we did not consider the filtering step of post-processing approaches, otherwise it would grow when |G + | |G| grows.

Figure 6 Figure 6 . 7 :Figure 6

 6676 Figure 6.6: Query evaluation time (t G , t G A and t G + )

  and future work . . . . . . . . . . . . . . . 109 7.2.1 Expressiveness . . . . . . . . . . . . . . . . . . . . . . 109 7.2.2 Verifiability . . . . . . . . . . . . . . . . . . . . . . . . 111 7.2.3 Performance . . . . . . . . . . . . . . . . . . . . . . . 111

  AllegroGraph 10 , StarDog 11 , Jena TDB 12 and Sesame Native Store 13 . RDMS-backed RDF stores such as Virtuoso 14 and Jena SDB 15 , use a relational database to store triples. One of the key concepts of the Semantic Web architecture are Named Graphs which is a simple extension of the RDF data model that transforms RDF triples to quads. Named graphs are sets of triples identified by IRIs, allowing descriptions to be made of that set such as provenance information, context and other metadata.

	1 http://www.mckinsey.com/business-functions/business-technology/ our-insights/open-data-unlocking-innovation-and-performance-with-liquid-information 2 http://data.enseignementsup-recherche.gouv.fr 3 http://data.grandlyon.com and http://data.beta.metropolegrenoble.fr 4 http://dbtune.org and http://linkedbrainz.org 5 http://www.geonames.org/ontology and wiki.dbpedia.org 6 http://lod-cloud.net/ 7 https://www.w3.org/wiki/TaskForces/CommunityProjects/ LinkingOpenData/DataSets/LinkStatistics 8 https://open-data.europa.eu/fr/data Uniprot Alexandria Digital Library Gazetteer lobid Organizations chem2 bio2rdf Multimedia Lab University Ghent Open Data Ecuador Geo Ecuador Serendipity UTPL LOD GovAgriBus Denmark DBpedia live URI Burner Social Networking Life Sciences Cross-Domain Government User-Generated Content Publications Media RDF data which has obviously motivated some research work on the design of adapted and efficient database systems. These systems are frequently referred Linguistics Geographic Identi ers Eionet RDF lobid Resources Wiktionary DBpedia Viaf Umthes RKB Explorer Courseware Opencyc Olia Gem. Thesaurus Audiovisuele Archieven Diseasome FU-Berlin Eurovoc in SKOS DNB GND Cornetto Bio2RDF Pubmed Bio2RDF NDC Bio2RDF Mesh IDS Ontos News Portal AEMET ineverycrea Linked User Feedback Museos Espania GNOSS Europeana Nomenclator Asturias Red Uno Internacional GNOSS Geo Wordnet Bio2RDF HGNC Ctic Public Dataset Bio2RDF Homologene Bio2RDF A ymetrix Muninn World War I CKAN Government Web Integration for Linked Data Universidad de Cuenca Linkeddata Freebase Linklion Ariadne Organic Edunet Gene Expression Atlas RDF Chembl RDF Biosamples RDF Identi ers Org Biomodels RDF Reactome RDF Disgenet Semantic Quran IATI as Linked Data Dutch Ships and Sailors Verrijktkoninkrijk IServe Arago-dbpedia Linked TCGA ABS 270a.info RDF License Environmental Applications Reference Thesaurus Thist JudaicaLink BPR OCD Shoah Victims Names Reload Data for Tourists in Castilla y Leon 2001 Spanish Census to RDF RKB Explorer Webscience RKB Explorer Eprints Harvest NVS EU Agencies Bodies EPO Linked NUTS RKB Explorer Epsrc Open Mobile Network RKB Explorer Lisbon RKB Explorer Italy CE4R Environment Agency Bathing Water Quality RKB Explorer Kaunas Open Data Thesaurus RKB Explorer Wordnet RKB Explorer ECS Austrian Ski Racers Social-semweb Thesaurus Data Open Ac Uk RKB Explorer IEEE RKB Explorer LAAS RKB Explorer Wiki RKB Explorer JISC RKB Explorer Eprints RKB Explorer Pisa RKB Explorer Darmstadt RKB Explorer unlocode RKB Explorer Newcastle RKB Explorer OS RKB Explorer Curriculum RKB Explorer Resex RKB Explorer Roma RKB Explorer Eurecom RKB Explorer IBM RKB Explorer NSF RKB Explorer kisti RKB Explorer DBLP RKB Explorer ACM RKB Explorer Citeseer RKB Explorer Southampton RKB Explorer Deepblue RKB Explorer Deploy RKB Explorer Risks RKB Explorer ERA RKB Explorer OAI RKB Explorer FT RKB Explorer Ulm RKB Explorer Irit RKB Explorer RAE2001 RKB Explorer Dotac RKB Explorer Budapest Swedish Open Cultural Heritage Radatana Courts Thesaurus German Labor Law Thesaurus GovUK Transport Data GovUK Education Data Enakting Mortality Enakting Energy Enakting Crime Enakting Population Enakting CO2Emission Enakting NHS RKB Explorer Crime RKB Explorer cordis Govtrack Geological Survey of Austria Thesaurus Geo Linked Data Gesis Thesoz Bio2RDF Pharmgkb Bio2RDF Sabiork Bio2RDF Ncbigene Bio2RDF Ire ndex Bio2RDF Iproclass Bio2RDF GOA Bio2RDF Drugbank Bio2RDF CTD Bio2RDF Biomodels Bio2RDF DBSNP Bio2RDF Clinicaltrials Bio2RDF LSR Bio2RDF Orphanet Bio2RDF Wormbase BIS 270a.info DM2E DBpedia PT DBpedia ES DBpedia CS DBnary Alpino RDF YAGO Pdev Lemon Lemonuby Isocat Iet ang Core KUPKB Getty AAT Semantic Web Journal OpenlinkSW Dataspaces MyOpenlink Dataspaces Jugem Typepad Aspire Harper Adams NBN Resolving Worldcat Bio2RDF Bio2RDF ECO Taxon-concept Assets Indymedia GovUK Societal Wellbeing Deprivation imd Employment Rank La 2010 GNU Licenses Greek Wordnet DBpedia CIPFA Yso. Allars Glottolog StatusNet shnoulle Revyu Charging Stations Aspire UCL Didactalia Artenue Vosmedios GNOSS Linked Crunchbase ESD Standards VIVO University of Florida Bio2RDF SGD Resources Product Ontology Datos Bne.es StatusNet Mrblog Bio2RDF Dataset EUNIS GovUK Housing Market LCSH GovUK Transparency Impact ind. Households In temp. Accom. Uniprot KB StatusNet Timttmy Semantic Web Grundlagen GovUK Input ind. Local Authority Funding From Government Grant StatusNet Fcestrada JITA StatusNet Somsants StatusNet Ilikefreedom Drugbank FU-Berlin Semanlink StatusNet Dtdns StatusNet Status.net DCS She eld Athelia RFID StatusNet Tekk Lista Encabeza Mientos Materia StatusNet Fragdev Morelab DBTune John Peel Sessions RDFize last.fm Open Data Euskadi GovUK Transparency Input ind. Local auth. Funding f. Gvmnt. Grant MSC Lexinfo Asn.us GovUK Societal Wellbeing Deprivation Imd Health Rank la 2010 StatusNet Macno Oceandrilling Borehole Aspire Qmul GovUK Impact Indicators Planning Applications Granted Loius Datahub.io StatusNet Maymay Prospects and Trends GNOSS GovUK Transparency Impact Indicators Energy E ciency new Builds DBpedia EU Bio2RDF Taxon StatusNet Tschlotfeldt Jamendo DBTune Aspire NTU GovUK Societal Wellbeing Deprivation Imd Health Score 2010 Lotico GNOSS Uniprot Metadata Linked Eurostat Aspire Sussex Lexvo Linked Geo Data StatusNet Spip SORS GovUK Homeless-ness Accept. per 1000 TWC PlanetData Project Wiki StatusNet Freelish Statistics data.gov.uk StatusNet Enipedia UK Legislation API Linked MDB StatusNet Qth Sider FU-Berlin DBpedia DE GovUK Households Social lettings General Needs Lettings Prp Number Bedrooms Agrovoc Skos My Experiment Proyecto Apadrina GovUK Imd Crime Rank 2010 GovUK Societal Wellbeing Deprivation Imd Housing Rank la 2010 StatusNet Uni Siegen Opendata Scotland Simd Education Rank StatusNet Kaimi GovUK Households Accommodated per 1000 StatusNet Planetlibre DBpedia EL DBpedia Lite Drug Interaction Knowledge Base StatusNet Qdnx Amsterdam Museum AS EDN LOD RDF Ohloh DBTune artists last.fm Hellenic Fire Brigade Bibsonomy Opendata Scotland Simd Income Rank Randomness Guide London Opendata Scotland Simd Health Rank Southampton ECS Eprints FRB 270a.info StatusNet Bka ESD Toolkit Hellenic Police StatusNet Mulestable StatusNet Ced117 Sebseb01 Open Energy Info Wiki StatusNet Lydiastench Open Data RISP Taxon-concept UIS 270a.info NYTimes Linked Open Data GovUK Households Projections Population W3C Opendata Scotland Simd Housing Rank StatusNet 1w6 StatusNet Alexandre Franke StatusNet Status Currency Designators StatusNet Hiico Linked Edgar GovUK Households 2008 StatusNet Pandaid Brazilian Politicians NHS Jargon Semantic Web DogFood UMBEL Openly Local StatusNet Ssweeny Interactive Maps GNOSS OECD 270a.info Green Competitive-ness GNOSS StatusNet Integralblue WOLD Linked Stock Index Apache KDATA Linked Open Piracy GovUK Societal Wellbeing Deprv. Imd Empl. Rank La 2010 BBC Music StatusNet Quitter StatusNet Sco oni Open Election Data Project Reference data.gov.uk StatusNet Jonkman DBTropes StatusNet Spraci ECB GovUK Impact Indicators Housing Starts GovUK Imd Income Rank La 2010 GovUK Transparency Impact Indicators Neighbourhood Plans GovUK Impact Indicators A ordable Housing Starts World Factbook FU-Berlin IMF 270a.info GovUK Households Social Lettings General Needs Lettings Prp Household Composition Opendata Scotland Graph Simd Rank Opendata Scotland Simd Employment Rank GovUK Societal Wellbeing Deprivation Imd Rank 2010 GovUK Imd Score 2010 BFS 270a.info GovUK Transparency Impact Indicators Planning Applications Granted GovUK Imd Opendata Scotland Graph Education Pupils by School and GovUK Societal Wellbeing Deprivation Imd 2010 GovUK Transparency Input indicators Local authorities Working w. tr. Families Education Rank La Datazone GovUK societal wellbeing deprv. imd rank '07 GovUK societal wellbeing deprv. imd rank la '10 GovUK impact indicators tr. families transparency GovUK service expenditure Rank 2010 GovUK Wellbeing Worthwhile GovUK Societal Wellbeing Deprv. imd Score '10 GovUK Households Projections total Houseolds GovUK Societal Wellbeing Deprivation Imd Income Rank La 2010 GovUK Transparency Impact Indicators A ordable Housing Starts ODCL SOA GovUK wellb. happy std. dev. GovUK Transparency Impact Indicators GovUK societal wellbeing deprivation imd employment score 2010 Housing Starts GovUK impact e ciency new builds GovUK Net Add. Dwellings indicators energy yesterday Bizkai Sense Mean GovUK Dev Local Authority Services Eurostat RDF GovUK imd env. rank 2010 Enel Shops Opendata Opendata Scotland Simd Crime Rank Scotland Simd Geographic Access Rank 270a.info StatusNet Thelovebug Icane Greek Administrative Geography StatusNet Orangeseeds DBpedia NL FAO Geopolitical Ontology StatusNet ldnfai StatusNet Keuser StatusNet Russwurm GovUK Societal Wellbeing Deprivation Imd Crime Rank 2010 StatusNet Datenfahrt StatusNet Imirhil Southampton ac.uk LOD2 Project Wiki DBpedia KO WALS DBpedia IT StatusNet Recit StatusNet Exdc Elviajero Aves3D Open Calais Zaragoza Turruta Wordnet (VU) StatusNet David Haberthuer Pre x.cc NALT Vulnera-pedia GovUK Wellbeing lsoa Happy Yesterday Mean Flickr Wrappr StatusNet Gomertronic Tags2con Delicious StatusNet Progval DBpedia JA StatusNet StatusNet Postblue StatusNet Skilledtests Nextweb GNOSS Eurostat FU-Berlin Fcac Clean Energy Data Reegle Chronicling America StatusNet Belfalas StatusNet Legadolibre StatusNet Lebsanft GADM Geovocab Semantic XBRL UK Postcodes Geo Names EEARod Camera Deputati Linked Data City Lich eld StatusNet Atari Frosch StatusNet Soucy Linked Railway Data Project FAO 270a.info Code Haus Ordnance Survey Linked Data Wordpress EEA Transparency 270a.info GovUK Homelessness Households Accommodated Temporary Housing Types StatusNet Mystatus Sat StatusNet Coreyavis GovUK Societal Wellbeing Deprivation Imd Environment Rank 2010 Worldbank 270a.info OSM Deuxpi StatusNet mkuttner StatusNet Zaragoza Datos Abiertos Eurostat Linked Data Acorn GEMET StatusNet 20100 Pokepedia Glou DBTune Magnatune NUTS Geo-vocab BBC Wildlife Finder Miguiad Eviajes GNOSS StatusNet WWW Foundation Web Nmasuno Traveler StatusNet schiessle StatusNet Tekord Linked Datasets as of August 2014 SISVU Livejournal StatusNet StatusNet StatusNet StatusNet Equestriarp Bonifaz Kathryl doomicile StatusNet Johndrink Water StatusNet tl1n StatusNet Kenzoid Ludost StatusNet gegeweb Opensimchat FOAF-Pro les StatusNet Samnoble StatusNet Rainbowdash StatusNet BBC Program-mes StatusNet StatusNet chromic Morphtown Otbm StatusNet Hackerposse DBTune Music-brainz StatusNet piana StatusNet thornton2 Deusto Tech StatusNet Debian Package Tracking System StatusNet Mamalibre StatusNet Ourco s StatusNet chickenkiller StatusNet Cooleysekula DB StatusNet Sweetie Belle Archiveshub Linked Data Semantic-web.org LOV Garnica Plywood Linked Mark Mail Berlios StatusNet linuxwrangling Lingvoj Open Food DBpedia FR ISO 639 Bootsnall Wordnet (W3C) Linked of Ecology Open Data Oasis Taxon concept Geospecies Facts Product Occurences ZDB Dewey Decimal Classi cation Linked Life Data Linked Food Bio2RDF OMIM Uniprot L3S DBLP Dailymed FU-Berlin Testee DWS Group DNB Bluk BNB Nobel Prizes Mis Museos GNOSS STW Thesaurus for Economics Data Bnf.fr LOD linkedct ACBDLS Bio2RDF OMIM Resources Taxonomy Aspire Manchester Yso. YSA Bio2RDF GeneID GNI Bible Ontology Idref.fr Princeton Library Findingaids Colinda Bio2RDF Taxonomy B3Kat Sudoc.fr Pub Bielefeld VIVO Indiana University Bio2RDF SGD Theses.fr IEEEvis Aspire Brunel Sztaki Aspire Aspire Roehampton to as RDF stores or triplestores. Several RDF stores have been developed to Uclan Nottingham Trent Resource Lists DOI Deutsche Biographie Aspire Aspire Portsmouth handle RDF data, among which some are native whereas others use RDBMS Plymouth backend. Native RDF stores are those that are implemented from scratch and LOD Aspire Keele Project Gutenberg FU-Berlin Libris National Diet Library WEB NDL Authorities Open Library Aspire MMU O'Reilly exploit the RDF data model to efficiently store and access the RDF data, such Dev8d Ciard Ring Bibbase British Museum Gutenberg Collection as 4Store 9 ,
	Figure 1.1: Linked Data Diagram (30/08/2014)

  .2.

		Subject	Predicate	Object
	et 1 : hasTumor	rdfs : domain	: Cancerous
	et 2 : Cancerous rdfs : subClassOf	: Patient
	et 3	: onc	rdf : type	: Oncology
	et 4	: alice	: hasTumor	: breastTumor
	et 5	: bob	: service	: onc
	et

Definition 2.1.2 (RDF graph) An RDF graph (or simply "graph", where unambiguous) is a finite set of RDF triples. 6 : bob : treats : alice Figure 2.2: An example of an RDF graph G 0 Example 2.1.3 Figure 2.2 depicts a graph G 0 constituted by triples et 1 to et 6 , both pictorially and textually.

  Example 2.1.15 Consider the following inference rule which states that if a doctor is assigned to a service and treats a patient, then this patient is admitted to the doctor's service. Consider the graph G 0 of Figure2.2, and inference rules RDom and RSc 2 in Table2.1 (more details about these rules can be found in the next section). If we apply the inference rule RDom using triples et 1 and et 4 then we infer it 1 . Afterwards, RSc 2 is applied to et 2 and it 1 to infer it 3 . Thus,Cl {RDom,RSc 2 } (G 0 ) = G 0 ∪ {it 1 , it 3 }.Assume that we add rule RAdm. Referring to the graph G 0 of Figure 2.2, its closure now contains a new inferred triple Cl {RDom,RSc 2 ,RAdm} (G 0 ) = G 0 ∪ {it 1 , it 3 , it 2 }. The new inferred triples are depicted by dashed arrows in Figure 2.4.

	Example 2.1.16 shows the closure computation of a graph using inference rules. Predicate Object et 1 : hasTumor rdfs : domain : Cancerous et 2 : Cancerous rdfs : subClassOf : Patient et 3 : onc rdf : type : Oncology et 4 : alice : hasTumor : breastTumor et 5 : bob : service : onc et 6 : bob : treats : alice it 1 : alice rdf : type : Cancerous it 2 : alice : admitted : onc Example 2.1.16 Subject it 3 : alice rdf : type : Patient

(?d ; : service ; ?s)(?d ; : treats ; ?p) (?p ; : admitted ; ?s) = RAdm The rule is applied on G 0 of Figure 2.2 by replacing the variables with the terms of the graph. (: bob ; : service ; : onc)(bob ; : treats ; alice) (alice ; : admitted ; onc)

Table 2

 2

	.1: Example of RDFS inference rules
	(?p ; rdfs : domain ; ?d) (?x ; ?p ; ?y) (?x ; rdf : type ; ?d)	= RDom
	(?p ; rdfs : range ; ?r) (?x ; ?p ; ?y) (?y ; rdf : type ; ?r)	= RRan
	(?c 1 ; rdfs : subClassOf ; ?c 2 ) (?c 2 ; rdfs : subClassOf ; ?c 3 ) (?c 1 ; rdfs : subClassOf ; ?c 3 )	= RSc 1
	(?a ; rdf : subClassOf ; ?b) (?x ; rdf : type ; ?a) (?x ; rdf : type ; ?b)	= RSc 2

(?p 1 ; rdfs : subPropertyOf ; ?p 2 ) (?p 2 ; rdfs : subPropertyOf ; ?p 3 ) (?p 1 ; rdfs : subPropertyOf ; ?p 3 ) = RSp 1 (?p ; rdfs : subPropertyOf ; ?q) (?x ; ?p ; ?y) (?x ; ?q ; ?y) = RSp 2 and is itself a resource (therefore identified by an IRI) belonging to the class rdfs : Class. An instance of a class is a resource belonging to that class. The rdf : type property states the relationship between instances and classes. Literals are defined by rdfs : Literal. For any given RDF triple, its subject and object are instances of rdfs : Resource, while its predicate is an instance of rdf : Property. The RDFS properties rdfs : range and rdfs : domain allow us to state the subject and the object class of a given rdf : Property respectively.

Example 2.1.17 For instance (: hasTumor ; rdfs : domain ; :Patient) states that the domain of the property : hasTumor is the class : Patient, in other words the subject of any triple with predicate : hasTumor is an instance of : Patient.

RDFS allows us to define classes and properties hierarchies by

the properties rdfs : subClassOf and rdfs : subPropertyOf respectively. rdfs : subClassOf allows to say that the class extension of a class description is a subset of the class extension of another class description. For instance (: Patient; rdfs : subClassOf; :Person) means that any instance of : Patient is an instance of : Person. Similarly, rdfs : subPropertyOf states that the property extension of a given property is a subset of another property extension. For instance (: hasTumor ; rdfs : subPropertyOf ; :hasDisease) means that any two resources related with : hasTumor are related with : hasDisease.

Table 2

 2

	.2: Comparison of the approaches	Approaches	Farkas Reddivari Flouris Abel Costabello Lopes Papakonstantinou
			Criteria	Authorization Triple Pattern	object

Table 3

 3

	.1: Example of authorizations
	a 1 = GRANT(?p ; :hasTumor ; ?t)
	a 2 = DENY (?p ; rdf : type ; :Cancerous)
	a 3 = GRANT(?d ; :service ; ?s)
	a 4 = GRANT(?d ; :treats ; ?p)
	a 5 = DENY (?p ; :admitted ; ?s)
	WHERE {(?s ; rdf : type ; :Oncology)}
	a 6 = GRANT(?p ; :admitted ; ?s)
	a 7 = GRANT(?p ; rdfs : domain ; ?s)
	a

8 = DENY (?s ; ?p ; :Cancerous) a 9 = DENY (?s ; ?p ; ?o)

  .1 and its effect is -, we deduce that it 2 ∈ Cl(G 0 ) + {et 1 , et 4 , et 5 , et 6 }.

	Algorithm 1 Algorithm for constructing positive sugbraph
	Input: a base graph G ∈ BGP , an authorization policy P = (A, ch), a set
		of inference rules R.
	Output: a positive subgraph G + P .
	1: function getGpos(G, P , R)
	2:	Let G + P ← ∅
	3:	for all t ∈ Cl R (G) do
	4:	Let ar ← ∅
	5:	for all a ∈ A do
	6:	if ∃θ s.t. t = head(a) then
	7:	let B = head(a)θ ∪ hb(a)θ
	8:	if B Cl R (G) = ∅ then
	9:	ar ← ar ∪ {a}
	10:	end if
	11:	end if
	12:	end for
	13:	if (effect • ch)(ar) = + then
	14:	G + P ← G + P ∪ {t}
	15:	end if
	16:	end for
	17:	return G +
		Table 3.2: Example of positive subgraph constitution
		P . By

P 18: end function applying a similar reasoning on all triples in Cl(G 0 ), we obtain Cl(G 0 ) + P =

  t MSTP , formally, ch = min MSTP . MSTP property (see Definition 3.1.16). ∀B ⊆ A. By definition min MSTP returns the smallest authorization with respect to min MSTP . Since min MSTP is a linear extension of MSTP then ∀a ∈ B. a MSTP min

	Lemma 3.2.16 (MSTP strategy application) Given a policy P	=
	(A, min

MSTP ), the function min MSTP applies the MSTP strategy. Proof We prove that min MSTP satisfies the MSTP ⇒ a MSTP min MSTP hence the satisfaction of the MSTP property.

Table 3 .

 3 3: S and L values at the end of each iteration

  Note that one can define other operations such as "SubStringOf, IsPrefix, . RH , . . . ". Atom is the building block of targets. It allows to make operations over keys and values using operators. Let k, k 1 , k 2 ∈ Key, v ∈ Value, and op a binary predicate in OP. The Atom component is defined as either : (i) k op v which compares a Key with a Value, or (ii) k 1 op k 2 which compares a Key with a Key. The following are examples of atoms: age ≥ . 18: applies to users whose age is greater than or equal to 18. role = . nurse: applies to users in role nurse. role . RH doctor: applies to role doctor and all its senior roles, in case of role hierarchy (2.2.1.3 (P. 28)). Here . RH is interpreted by RH , the hierarchical relation between roles. The policy of Example 5.0.1 is interpreted in Table 5.2, built using the formal language shown in Table 5.1. The global policy P has two childs : a universal authorization authorization a u and another policy P 0 . P 0 ,

	Policies Example 5.2.2 Example 5.2.3 Table 5.2: Example of a global policy P P = [( , P 0

Table 3

 3

.2 (P. 51) containing the applicable authorizations w.r.t policy P = (A, ch) defined in Example 3.

1.8 (P. 50)

. authToBs({a 1 , a 9

3

  Example 6.1.3 Consider the Table3.2 (P. 51) containing the applicable authorizations w.r.t policy P = (A, ch) defined in Example 3.1.8 (P. 50). The dataset representing the annotated graph is illustrated by Table6.1. Definition 6.1.2 defines how to annotate the base graph G given the policy authorizations set. The following lemma ensures that G A forms a partition of the base graph G. Given an annotated graph G

	Table 6.1: Example of a dataset representing an annotated graph
	u	G
	000000111	{et 1 }
	000000001 {et 2 , et 3 , it 3 }
	100000001	{et 4 }
	001000001	{et 5 }
	000100001	{et 6 }
	010000011	{it 1 }
	000011001	{it 2 }
	Lemma 6.1.4

Table 6

 6

		.3: Summary of notations
	in |G|	Size of the LUBM dataset
	in |A|	Number of authorizations
	in |G + | |G| Positive subgraph size w.r.t raw dataset size
	in |A s |	Number of authorizations assigned to the user
	in Q s	LUBM test Query
	out t A	Time to build G A in memory
	out t W	Time to write G A to disk
	out t G +	Time to evaluate Q on materialized G +
	out t G A	Time to evaluate Q on G A
	out t

G Time to evaluate Q on (raw) G

  Table6.3. The base graphs are synthetic graphs generated by the Lehigh University Benchmark (LUBM) 4 . Their sizes (|G|) vary from 126k to 1,591k triples. The access control policies are randomly generated using the LUBM vocabulary (about universities and people therein), with three control parameters. The first control parameter is the number of authorizations (|A|) and varies from 50 to 200 authorizations. The second control parameter is the scope average of the policy with respect to the G. In other words, the percentage of triples in G which are under the influence of the policy authorizations. The last control parameter is the size of the body of each (atomic) authorization a ∈ A. The results we report here are for fixed scope (about 4% by authorization) and fixed sizes of bodies (set to 2 for each authorization). The size of positive subgraph parameter |G + | |G| varies from 10 to 100% of |G| and the number of user authorizations |A s | from 50 to 200. Regarding the user's query parameter Q s , we used a subset of LUBM test queries. We analyze both the static (creation time) and the dynamic (evaluation time) performance of our solution. Each experiment is run 6 times on 2 cores and 4 GB virtual machines running on OpenStack.

https://ctovision.com/2015/12/big-data-unlocks-valuableinformation-across-organizations-but-only-if-you-can-protect-it/

www.4store.com

http://franz.com/agraph/allegrograph/

http://www.stardog.com/

https://jena.apache.org/documentation/tdb/index.html

http://www.rdf4j.org/

http://virtuoso.openlinksw.com/

https://jena.apache.org/documentation/sdb/

https://ctovision.com/2015/12/big-data-unlocks-valuableinformation-across-organizations-but-only-if-you-can-protect-it/

http://liris.cnrs.fr/ ~tsayah/AC4RDF/

https://jena.apache.org/documentation/tdb/

https://jena.apache.org/documentation/query/

http://jena.apache.org/documentation/tdb/quadfilter.html

Remerciements

∀B ⊆ A.ch(B) = a u ⇒ B \ {a u } = ∅, the structure P -= (A, ch -) is a well-formed policy.

Proof Firstly, we remark that B -\{a u } = (B \ {a u }) -and that B -∪B + = B. Secondly, we note that function ch -is properly defined because pairwise conjunctions of conditions (1), ( 2) and (3) are unsatisfiable and the disjunction of these formulas is a tautology. We show that P = (A, ch -) satisfies the wellformedness conditions.

Totality By assumption 3.2.3, there exists a universal rule a u ∈ A.

Closedness

Otherwise, we have B -\ {a u } = ∅. Assumption a = a u implies that case (3) is ruled out, so a has to be positive by case (2). By the Closedness property of ch, a ∈ B -\ {a u } so a is negative, a contradiction.

The following lemma ensures that ch -applies the DTP strategy.

Let ns i and S i be the values of ns and S respectively at the beginning of the i th iteration of the loop between lines 4 and 15.

The following holds: For each iteration i, authorization a = min LEX (ns i ) has no incoming edges, and it is the next authorization that will be inserted into L, i.e. L[i] = min LEX (ns i ).

Proof First we prove that a = min LEX (ns i ) has no incoming edges. Suppose that a has an incoming edge from b. b is not in L, otherwise the edge b → a would have been removed by Line 10 during some previous iteration. Hence b ∈ ns i . Since there is an edge b → a then b a , thus b LEX a since LEX is a linear extension of . Since we do not consider atomic loops, then a = b. Since b LEX a then a = min LEX (ns i ) which contradicts the hypothesis.

We prove that the next authorization that will be inserted into L is a = min LEX (ns i ). Suppose that a is not the next authorization to be inserted to L, hence ∃b ∈ S i ⊆ ns i s. Note that if the total order LEX is already a linear extension of the partial order , then Algortithm 2 will generate a total order that is equal to LEX , which is showed by the following lemma. Lemma 3.2.15 If LEX is a linear extension of MSTP then LEX = A Proof We show that at the end of Algorithm 2 :

. Since i ≤ j then at the beginning of iteration i both b and c were in ns. Hence at iteration i, and by Lemma 3.2.14, b = min LEX (ns i ) and since c counterexamples of the consistency property have to arise this way. Theorems 4.3.1 and 4.3.2 formally state the correctness of the algorithm: P is not consistent w.r.t. R if and only if Algorithm 3 returns a non empty collection. We rely on the usual definitions of unifiers and most general unifiers (mgu) as stated by Martelli and Montanari for instance, [START_REF] Martelli | [END_REF]]. (See Appendix A, Section A.2).

Theorem 4.3.1 (Soundness of Algorithm 3) If Algorithm 3 returns a non empty collection then

Theorem 4.3.1 holds by construction: Line 9 of Algorithm 3 ensures that B is a counterexample. Next, we prove Theorem 4.3.2 and discuss counterexample usage.

Proof of completeness

To show that Theorem 4.3.2 holds, we first introduce two lemmas. Intuitively, Lemma 4.3.3 ensures that the Definition 3.1.3 (P. 47) of applicable authorizations behaves well according to graphs inclusion. Lemma 4.3.4 is its counterpart for the closure of a graph according to a set of inference rules. Proof First, we prove that for any

. By definition 2.1.13 (P. 21) there exists a rule r = (tp ← tp 1 , . . . , tp k ) ∈ R and a substitution σ such that {(tp 1 )σ, . . . , (tp k )σ} ⊆ B and t = (tp)σ. Thus {(tp 1 )ση, . . . , (tp k )ση} ⊆ (B )η ⊆ G and t = (tp)ση. Thus, by definition 2.1.13 (P. 21), (t

as in definition 2.1.13 (P. 21). We prove, by induction on i, that for all

As previously proved and since, by induction hypothesis,

Lemma 4.3.5 Let P = (A, ch) be a policy, a ∈ A be an authorization, G a basic graph pattern and t ∈ G. If a ∈ ar(G, A)(t), then for any renaming substitution ρ of a, there exists a substitution θ such that (head(a)ρ)θ = t and θ ∈ hb(a)ρ G .

Proof By definition 3.1.3 (P. 47), there exists a substitution θ such that t = (head(a))θ and θ ∈ hb(a) G , i.e. hb(a)θ ∈ G. Since ρ is a renaming substitution, it is bijective and (hb(a)ρ)ρ -1 = hb(a) and (head(a)ρ)ρ -1 = head(a).

Thus ((hb(a)ρ)ρ -1 )θ ∈ G and t = ((head(a)ρ)ρ -1 )θ . It is sufficient to take θ = ρ -1 θ . Lemma 4.3.6 Let P = (A, ch) be an authorization policy, R a set of inferences rules, B, G ∈ BGP basic graph patterns, and η a substitution such that Bη ⊆ G. For any t ∈ B, ar(Cl R (B), A)(t) ⊆ ar(Cl R (G), A)((t)η).

Proof By Lemma 4.3.4, (Cl R (B))η ⊆ Cl R (G). By applying Lemma 4.3.3 on Cl R (B) and Cl R (G), we conclude that for any t ∈ B ⊆ Cl R (B), ar(Cl R (B), A)(t) ⊆ ar(Cl R (G), A)((t)η).

Once the subject's positive subgraph is computed with filter function, the subject's query Q is then evaluated over it returning Q filter(G A )(ubs) to the subject.

Implementation

Our system is implemented using the Jena Java API on top of the Jena TDB 1 (quad) store. Apache Jena is an open source Java framework which provides an API to manage RDF data. ARQ 2 is a SPARQL query engine for Jena which allows querying and updating RDF models through the SPARQL standards. ARQ supports custom aggregation and GROUP BY, FILTER functions and path queries.

Appendix

In this appendix, we provide additional technical definitions and lemmas and the LUBM Queries used for experiments.

A.1 Results from Section 2.1.1.3

Lemma A.1.1 (Closure property) Cl is a closure operator that satisfies the following properties for all G ∈ BGP :

Proof of Lemma A.1.1 First, let k the smallest natural number that exists according to Lemma 2.1.14, so we can express Cl(G) as a finite union of graphs

Increasing By induction, we show first that G i ⊆ H i . For i = 0, the result holds by hypothesis

we're done by the induction hypothesis. Otherwise, it is the case that x ∈ φ(G i ) and there exists a rule r such that x ∈ φ r (G i ), but r can be applied on H i as well because G i ⊆ H i , so x ∈ φ r (H i ) ⊆ H i+1 and we're done again. There exists some l ∈ N such that Cl(H) = H 0 ∪H 1 ∪. . .∪H l with k ≤ l, by the previous result G i ⊆ H i hold for all i ∈ 0 . . . k thus Cl(G) ⊆ Cl(H) by piecewise union.

Appendix A. Appendix

Idempotent By Lemma 2.1.14 we can write Cl(Cl(G)) = Cl(G) 0 ∪ Cl(G) 1 ∪ . . . ∪ Cl(G) k for some k , we have to show that Cl(G) i = Cl(G) 0 so the union collapses at Cl(G) 0 = Cl(G). The proof amounts to show that Cl(G) = Cl(G) ∪ φ(Cl(G)), or equivalently that φ(Cl(G)) ⊆ Cl(G). For the sake of the contradiction, assume that there is some x ∈ φ(Cl(G)) with x / ∈ Cl(G), by Definition 2.1.13, there is a rule r = (tp ← tp 1 , . . . , tp n ) and a mapping σ ∈ {tp 1 , . . . , tp n } Cl(G) such that x = (tp)σ. Because ({tp 1 , . . . , tp n })σ ⊆ Cl(G) from Definition 2.1.8, we can can build a function ι : {1 . . . n} →{1 . . . k} that maps the index i of each tp i to the index j of some subgraph G j of Cl(G). Let m be the largest natural number in the set {ι( 1

and k is not the smallest natural number that stabilizes Cl(G) according to Lemma 2.1.14, a contradiction again.

A.2 Results from Section 4.3 A.2.1 Additional Definitions

Definition A.2.1 (Renaming Substitution) A renaming substitution for a basic graph pattern B is a substitution ρ : var(B) → V associating each variable of B to a fresh variable. A renaming substitution for an authorization a is a renaming substitution for hb(a).

Definition A.2.2 (Unifier, Most General Unifier [Martelli 1982])

A substitution μ is a unifier for two triple patterns tp 1 and tp 2 if tp 1 μ = tp 2 μ. A substitution μ is a unifier for two tuples of triple patterns T P = (tp 1 , . . . , tp k ) and T P = (tp 1 , . . . , tp k ) of the same size k, if for all i ∈ {1, . . . , k}, μ is a unifier for tp i and tp i .

Two triples patterns tp 1 and tp 2 (resp. two tuples of triple patterns T P and T P ) are unifiable if there exists a unifier μ for tp 1 and tp 2 (resp. T P and T P ).

A substitution μ is a most general unifier for two triple patterns tp 1 and tp 2 (resp. two tuples of triple patterns T P and T P ) if for any unifier μ of tp 1 A.3. LUBM Queries 123 and tp 2 (resp. T P and T P ), there exists a substitution η such that μ = μη.

Lemma A.2.3 (Computable Most General Unifier [Martelli 1982])

If T P and T P are unifiable, then there exists a most general unifier μ for T P and T P . Given two unifiable tuples of triple patterns T P and T P , the function mgu(T P, T P ) returns one of the most general unifiers of T P and T P . Moreover, this most general unifier is unique up to a renaming of variables.

A.3 LUBM Queries