Brevet FR3059446A1 — publié le 20180601

Procédé d'insertion de données à la volée dans une base de données tatouées et dispositif associé 1. Domaine de l'invention Le domaine de l'invention est celui de la sécurité informatique et plus particulièrement de la protection des bases de données. 2. Art antérieur Par la suite, on parlera de base de données en tant que forme particulière de structuration d'un ou plusieurs jeux de données. Le reste de la description s'appliquera indifféremment à tout type de bases de données susceptibles d'être tatouées et en particulier à des bases de données relationnelles. Il est connu de tatouer le contenu des bases de données afin d'assurer la traçabilité des données extraites et de certifier l'authenticité de l'utilisateur ayant extrait ces données. Par définition, le tatouage de données fait référence à une technique consistant à insérer dans les données à protéger une marque (watermark en anglais). La marque est un message contenant des attributs de sécurité, tels qu'une signature ou un code d'authentification, permettant au propriétaire d'une base de données de tracer les utilisateurs qui accèdent à ces données, ou de vérifier l'intégrité de ces dernières. Le tatouage laisse l'utilisateur accéder à l'information tout en la maintenant protégée par la marque insérée. Les données dans lesquelles la marque a été insérée sont dites tatouées. La propriété de réversibilité est une caractéristique propre à certaines modulations de tatouage offrant la possibilité d'enlever la marque des données tatouées et de récupérer les données originales, i.e. avant l'application du tatouage. Des méthodes de tatouage robuste et réversible de données ont été présentées par J. Franco-Contreras, G. Coatrieux, F. Cuppens, N. Cuppens-Boulahia, E. Chazard et C. Roux dans « Tatouage Robuste et Réversible pour la Traçabilité de Bases de Données Relationnelles en Santé », au congrès Recherche en Imagerie et Technologies pour la 30 Santé (RITS) en Avril 2013 à Bordeaux en France. Ce document est référencé Dl. De manière classique, l'insertion de données dans une base de données nécessite de détatouer l'intégralité de la base. Compte-tenu des capacités de traitement limitées 3059446 2 des systèmes de gestion de bases de données actuels (e.g. processeurs et mémoires), ce traitement est particulièrement contraignant pour l'insertion de données. Un problème auquel est confronté l'homme du métier lors de la mise à jour d'une base de données tatouées est que l'insertion de nouveaux tuples ou enregistrement 5 de données dans la base de données ne peut pas se faire « à la volée », c'est-à-dire qu'il n'est pas possible d'insérer de nouveaux tuples sans avoir à détatouer préalablement l'intégralité de la base. Dès lors que les nouvelles données ont été insérées, l'intégralité des données contenues dans la base sont tatouées en tenant compte des nouvelles données insérées. 10 Ces opérations de détatouage/tatouage sont particulièrement désavantageuses car elles nécessitent des temps de traitement non négligeables alors que la taille des données à insérer est en général relativement faible (quelques kilo-octets) en comparaison avec la capacité de données contenues dans la base (plusieurs Téraoctets). Par ailleurs, le détatouage intégral de la base de données, même s'il est temporaire, doit être évité pour 15 des raisons de sécurité. Par conséquent, il existe un réel besoin d'insérer, en un minimum de temps et de manière sécurisée, des données contenues dans une base de données tatouées selon un mécanisme de tatouage réversible sans avoir à effectuer de traitement sur l'intégralité de la base de données. 20 3. Objet et résumé de l'invention La présente invention offre une solution qui répond au problème technique mentionné ci-dessus en proposant un procédé d'insertion d'au moins un tuple dans une base de données préalablement tatouée selon un mécanisme de tatouage réversible, 25 selon lequel les tuples contenus dans ladite base de données sont répartis dans un ensemble de groupes ou classes de tuples. Le procédé comprend les étapes suivantes : - stockage de métadonnées de tatouage comprenant : - au moins un attribut sur lequel porte ledit tatouage ; - le type de groupe ou classe sélectionné parmi « porteur » ou « non porteur » d'au moins un symbole ou bit à encoder dans ledit groupe ou classe ; 3059446 3 - une règle définissant une modification de la valeur dudit au moins un attribut en fonction d'un paramètre de force d'insertion a prédéfini ; - sur réception d'une première requête d'insertion comprenant ledit au 5 moins un tuple, identification du groupe ou de la classe dans lequel ledit au moins un tuple est destiné à être inséré, parmi ledit ensemble de groupes ou classes ; - tatouage dudit au moins un tuple lors de laquelle, la valeur dudit au moins un attribut est modifiée selon ladite règle en fonction du type 10 de groupe ou classe identifié, de manière à obtenir au moins un tuple modifié ; et - envoi d'une deuxième requête d'insertion comprenant ledit au moins un tuple modifié, ladite règle étant définie de manière à préserver le type du groupe ou classe suite à l'insertion dudit au moins un tuple 15 modifié dans la base de données tatouée. Le stockage préalable des métadonnées de tatouage permet avantageusement de tatouer à la volée les nouveaux tuples à insérer dans la base de données, sans avoir à détatouer l'intégralité de la base de données à chaque insertion de tuples. En effet, les métadonnées de tatouage définissent la manière de modifier la 20 valeur des attributs dans les tuples à tatouer, en fonction de leur appartenant à un groupe donné. Grâce à ces données préalablement stockées, l'insertion de nouveaux tuples peut être réalisée à la volée, en un temps réduit par rapport au cas classique où un traitement sur l'intégralité de la base est nécessaire pour connaître la façon de modifier les tuples 25 lors de leur insertion dans la base. Selon une caractéristique de l'invention, la distribution des valeurs dudit au moins un attribut dans le groupe est modifiée selon ladite règle, de telle sorte que la distribution des valeurs obtenue suite à l'insertion dudit au moins un tuple modifié est modifiée d'une quantité prédéfinie 3, en fonction de la force d'insertion a, sans modifier 30 le type du groupe identifié. Ainsi, la distribution des valeurs de l'attribut est modifiée sans dénaturer le groupe, c'est-à-dire sans changer le type des groupes porteurs et non-porteurs. 3059446 4 Selon une autre caractéristique de l'invention, si le groupe identifié lors de l'étape d'identification est un groupe porteur d'au moins un bit ou symbole à insérer dans ledit groupe, la valeur dudit au moins un attribut dudit au moins un tuple à insérer est modifiée selon au moins une règle de codage pour dissimuler ledit au moins un bit 5 ou symbole dans ledit groupe, ladite règle de codage étant préalablement définie et stockée dans les métadonnées de tatouage. Ainsi, en appliquant systématiquement la même règle de codage, ledit au moins un bit ou symbole est inséré dans le groupe porteur identifié tout en préservant le caractère porteur de ce groupe (i.e. même type). De ce manière, on assure la modification à réaliser sur la valeur de l'attribut dans le 10 tuple à insérer correspond à celle qui a été originalement réalisée sur les précédents tuples pour coder ledit au moins un bit ou symbole dans le groupe. Par conséquent, de nouveaux tuples peuvent être insérés en évitant les erreurs de lecture lors de l'extraction de tuples. Selon une autre caractéristique de l'invention, le procédé comprend une étape 15 préalable de configuration, lors de laquelle on définit une clé secrète et des paramètres de tatouage sélectionnés parmi ledit au moins attribut à tatouer, une force d'insertion, un ou plusieurs nombres de groupe de tuples à générer, une séquence de symboles à dissimuler dans ladite base de données. Selon une autre caractéristique de l'invention, le procédé comprend une étape 20 préalable de tatouage intégral de la base de données en fonction des métadonnées de tatouage. Lors de l'opération de tatouage intégral de la base de données, la création des différents groupes est réalisée de manière à obtenir une distribution uniforme de tuples. Selon une autre caractéristique de l'invention, l'accès aux métadonnées de tatouage et l'accès à la base de données sont respectivement protégés par des données 25 d'authentification et/ou d'identification distinctes. Selon une autre caractéristique de l'invention, les droits de lecture et d'écriture associés aux métadonnées de tatouage ne sont pas accordés à un utilisateur de la base de données. Dans un mode particulier de réalisation, des étapes du procédé précité sont 30 déterminées par des instructions de programmes d'ordinateurs. 3059446 5 En conséquence, l'invention vise aussi un programme d'ordinateur sur un support d'informations. Ce programme susceptible d'être mis en oeuvre par un microprocesseur comprend des instructions adaptées à la mise en oeuvre des étapes du procédé selon l'invention. 5 Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable. L'invention vise aussi un support d'informations lisible par un microprocesseur, 10 et comprenant des instructions de code d'un programme d'ordinateur tel que mentionné ci-dessus. Ce support d'informations est un moyen de stockage d'informations, amovible ou non, partiellement ou totalement lisible par un ordinateur ou un microprocesseur Le support d'informations peut être n'importe quelle entité ou dispositif capable 15 de stocker le programme. Par exemple, le support peut comprendre un moyen de stockage, tel qu'une ROM, par exemple une ROM de microcircuit, ou encore un moyen d'enregistrement magnétique, par exemple un disque dur, ou encore une mémoire flash. D'autre part, le support d'informations peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou 20 optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur une plateforme de stockage d'un réseau de type Internet. Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question. 25 L'invention concerne également un serveur adapté pour exécuter les instructions pour la mise en oeuvre des étapes du procédé selon l'invention, les instructions pouvant être stockées sur un support d'informations inclus dans le serveur ou accessible par ce dernier. Le support d'informations, le programme d'ordinateur et le serveur précités 30 présentent des caractéristiques et avantages analogues au procédé qu'ils mettent en oeuvre. 3059446 6 D'autres particularités et avantages de l'invention apparaîtront encore dans la description ci-après en relation avec les dessins annexés, donnés à titre d'exemples non limitatifs : la figure 1 illustre schématiquement les étapes du procédé selon un mode de 5 réalisation l'invention, et la figure 2 illustre schématiquement un exemple de système client-serveur adapté à mettre en oeuvre le procédé selon l'invention. Définitions Par la suite, on désignera par base de données relationnelle toute structure de 10 données composée d'un nombre fini de relations ou tables. Chaque table ou relation est une structure de base, regroupant des données sur un sujet précis, tel que le séjour des patients dans un hôpital. Chaque table ou relation comprend un ensemble de N tuples non ordonnés {tu} avec N et u désignant un entier naturel, où 1 Ns. Cette séquence S peut être stockée dans les métadonnées de tatouage M. De manière plus générale, une information indiquant la valeur dudit au moins un symbole ou bit S, à insérer dans chaque groupe porteur G, est enregistrée en association avec un identifiant du groupe considéré. Par exemple, on enregistre dans les métadonnées de 20 tatouage M, le bit « 1 » en association avec l'identifiant du groupe porteur G, pour indiquer que le bit « 1 » est encodé au sein du groupe G1. Selon un autre exemple, on enregistre le signe + pour désigner le bit « 1 » (respectivement le signe - pour désigner le bit « 0 ») en association avec l'identifiant du groupe porteur G. Dans le cas de la modulation par histogramme circulaire considéré, pour chaque 25 groupe G' chacun des tuples tu est également réparti dans un sous-groupe sélectionné parmi un ensemble de deux sous-groupes notés GA4 et GB4. Ce sous-groupe est secrètement déterminé en utilisant la clé secrète de tatouage Kw enregistrée dans les données de tatouage, selon la formule suivante : nu=H(KwIH(Kwltu.PK))mod(2). Par exemple, le tuple tu est associé au groupe GA4 si H(Kwltu.PK))mod(2)=0 ou au groupe 30 GB4 si H(KwItu.PK))mod(2)=1. 3059446 12 On suppose que A' désigne un attribut de type numérique, sur lequel porte le tatouage, i.e. dont la valeur est modifié selon la règle prédéfinie en fonction du type de groupe auquel appartient le tuple. Comme décrit dans le document D2, pour chaque groupe G' la distribution des 5 valeurs de l'attribut A' est calculée et représentée sous forme d'histogrammes projetés sur un même cercle, pour chacun des deux sous-groupes GA4 et GB,i. Le premier sous-groupe GA4 (respectivement deuxième sous-groupe GB,i) est caractérisé par son centre de masse CA4 (respectivement C13,1) auquel est associé le vecteur VA,i (respectivement VB,i) comme illustré sur la figure 2 dans le document D2. 10 Groupes porteurs Dans le cas où le groupe Gi est porteur d'au moins un bit ou symbole à insérer dans le groupe (encodage), le processus d'insertion consiste à moduler l'angle (3, formé par les deux vecteurs VA,i et VB,i pour insérer (ou encoder) le bit Si =0 ou Si =1, selon la règle de codage exprimée en fonction de la force d'insertion a comme suit : 15 (3,w= (3,-2a pour insérer le bit Si =0 ou (3iw= (31+2a pour insérer le bit Si =1. De manière équivalente, la modulation de l'angle (3, par ±2a correspond à une modification de valeur de l'attribut A' de ±A, tel que A = a.L/(2n) où L désigne le nombre de valeurs distinctes que peut prendre l'attribut A' sur l'histogramme. Le signe 20 est défini en fonction du sous-groupe auquel appartient le tuple comme résumé dans le tableau 2 ci-dessous : Si G, GA,i GB,i pi w= pi-2a.(25i-1) A'+2(5,-1)A An-F(1-25,)A 0 (3,w= I3,-2a (Piw 0) An+A An-A Tableau 2. Règle de codage pour un groupe porteur Cette règle de codage s'applique aux groupes porteurs vérifiant la relation 25 1(3,1 0 dans le cas où Si=1. 3059446 13 Selon une particularité de l'invention, on stocke lors d'une étape de stockage El dans les métadonnées de tatouage M, pour chaque groupe porteur, une information indiquant la valeur dudit au moins un bit ou symbole Si à insérer, cette information étant stockée en association avec l'identifiant du groupe ou de la classe de type porteur. 5 Ainsi, dans l'exemple présent, on stocke pour chaque groupe porteur G' le signe de l'angle modulé (3,w . La règle de codage est également stockée dans les métadonnées de tatouage lors de l'étape de stockage El. En stockant préalablement lors de l'étape de stockage El dans les métadonnées de tatouage M, les identifiants des groupes porteurs et le signe associé à chaque groupe 10 pour encoder un bit, il est possible de tatouer à la volée un nouveau tuple destiné à être inséré dans la base de données. Groupes non porteurs Dans le cas où 43,1 >2a, le groupe G, est un groupe non porteur dans le sens où la valeur de a est trop faible pour faire changer de signe (3,w de manière à encoder un ou 15 plusieurs bits ou symboles Si. En fonction du signe de l'angle (3' on distingue les groupes non porteurs positifs pour lesquels (3,>0 et les groupes non porteurs négatifs pour lesquels (3, ° piw= (3i-E2a Aii+3, An-3, (3, n-2a, le groupe est de type overflow. Pour ce type de groupe, aucune modification n'est appliquée à l'attribut A' des tuples appartenant à ce type de goupe. Seul un « overhead » est ajouté pour distinguer le groupe de type overflow des autres types de groupes. 10 L'enregistrement préalable (étape El) dans les métadonnées de tatouage, du type de groupe (i.e. porteur, non porteur positif/négatif) et d'une règle de modification ou de codage associée à ce type de groupe pour modifier la valeur de l'attribut à tatouer, permet avantageusement d'insérer tout nouveau tuple à la volée, sans avoir à effectuer un traitement sur l'intégralité de la base de données. 15 Dans le présent mode de réalisation, la règle prévue pour modifier la valeur de l'attribut A' consiste à ajouter ou à soustraire 3,=a.L/(2n) aux valeurs que peut prendre l'attribut A' dans un groupe (ou sous-groupe) en fonction de l'appartenant du tuple à ce groupe (ou sous-groupe). Cette modification est conçue de telle sorte qu'elle permet de préserver le type de groupe auquel est associé un tuple lors de son insertion dans la 20 base. Cette règle de modification est donnée à titre d'exemple illustratif. Bien évidemment, l'homme du métier pourra envisager d'autres règles ayant la propriété. On suppose que la base de données est tatouée intégralement lors d'une étape préalable de tatouage intégral E02 selon les métadonnées de tatouage (M). A l'issue de cette étape, les tuples sont répartis de manière uniforme dans un ensemble de groupes, 25 parmi lesquels certains sont porteurs d'un bit du message dissimulé. On suppose qu'un utilisateur ayant les droits d'écriture sur la base de données 3 émet, au moyen de son terminal client, une première requête d'insertion I, pour insérer un nouveau tuple tu dans ladite base. Par exemple, ce tuple est constitué par les trois attributs suivant : id sejour =Id4 ; Age=12 ; duree sejour=4 que l'on désignera {4 ; 12 ; 30 4} par la suite. 3059446 15 Sur réception de cette première requête d'insertion Il, le serveur 2 détermine en consultant les métadonnées de tatouage M si le tuple comprend au moins un attribut sur lequel doit porter le tatouage. Dans le présent exemple, le serveur 2 identifie que les attributs age et 5 duree sejour sont des attributs tatoués respectivement avec une force d'insertion ±3 et ±2 et que trois groupes sont formés : un premier groupe porteur encodant un bit `1' (groupe 1), un deuxième groupe porteur encodant un bit '0' (groupe 2) et un troisième groupe porteur encodant un bit '1' (groupe 3). Lors d'une étape d'identification E3, le serveur 2 identifie le groupe dans lequel 10 le tuple est destiné à être inséré parmi l'ensemble des groupes identifiés dans les métadonnées de tatouage. L'identifiant du groupe dans lequel le nouveau tuple doit être inséré déterminé à partir de la clé primaire du tuple tu et de la clé de tatouage, au moyen d'une fonction cryptographique de hachage comme décrit précédemment. D'après cet identifiant, le serveur détermine le type de groupe et la règle correspondante pour 15 modifier la valeur de l'attribut à tatouer An. Dans le présent exemple, le serveur identifie lors de l'étape d'identification E3 que le groupe 1 est un groupe porteur encodant un bit '1', le groupe 2 est un groupe porteur encodant un bit '0' et le groupe 3 est un groupe porteur encodant un bit '1'). Le tuple à insérer {4 ; 12 ; 4} appartient au deuxième groupe Gi=2 et au sous-groupe A de 20 ce deuxième groupe (GA') où i=2. Lors d'une étape de tatouage E5, le serveur 2 détermine en fonction du type de groupe identifié la règle à appliquer pour le tuple à insérer. Plusieurs cas de figures se présentent en fonction du type de groupes. Si le groupe identifié est un groupe porteur (I(3,1 2a), le serveur 2 identifie en fonction du signe de l'angle (3' si le groupe est non porteur positif ((3,>0) ou si le 15 groupe est non porteur négatif ((3,>0). La distribution des valeurs de l'attribut A' est modifiée de -±3, en fonction du caractère positif/négatif du groupe, selon la règle définie dans les métadonnées de tatouage. Dans le cas d'un groupe non-porteur positif ((3,>0), la distribution des valeurs de l'attribut A' dans le sous-groupe GA4 est modifiée de +3, et la distribution des valeurs de 20 l'attribut A' dans le sous-groupe GB,1 est modifiée de -3' comme indiqué dans le tableau 3. Cette modification correspond à une modulation de l'angle (3, de +2a, de sorte que la valeur de l'angle tatoué (i.e. modifié par le tatouage) est (3,w, (31+2a. Au contraire, le cas d'un groupe non-porteur négatif 03, REVENDICATIONS1. Procédé d'insertion d'au moins un tuple (tu) dans une base de données (3) préalablement tatouée selon un mécanisme de tatouage réversible, selon lequel les tuples contenus dans ladite base de données sont répartis dans un ensemble de groupes (G,) ou classes (C,) de tuples, ledit procédé étant caractérisé en ce qu'il comprend les étapes suivantes : - stockage (El) de métadonnées de tatouage (M) comprenant : - au moins un attribut (An) sur lequel porte ledit tatouage ; - le type de groupe ou classe sélectionné parmi « porteur » ou « non porteur » d'au moins un symbole ou bit à encoder dans ledit groupe ou classe ; - une règle (R) définissant une modification de la valeur dudit au moins un attribut en fonction d'un paramètre de force d'insertion a prédéfini ; - sur réception d'une première requête d'insertion (Ii) comprenant ledit au moins un tuple (tu), identification (E3) du groupe (Gu) ou classe (Cu) dans lequel ledit au moins un tuple (tu) est destiné à être inséré, parmi ledit ensemble de groupes ou classes ; - tatouage (E5) dudit au moins un tuple (tu) lors de laquelle, la valeur dudit au moins un attribut (An) est modifiée selon ladite règle en fonction du type de groupe ou classe identifié, de manière à obtenir au moins un tuple modifié (tu') ; et - envoi (E7) d'une deuxième requête d'insertion (12) comprenant ledit au moins un tuple modifié (tu'), ladite règle étant définie de manière à préserver le type du groupe ou classe suite à l'insertion dudit au moins un tuple modifié (tu') dans la base de données tatouée (3). 2. Procédé selon la revendication précédente, caractérisé en ce que la distribution des valeurs dudit au moins un attribut dans le groupe est modifiée selon ladite règle, de telle sorte que la distribution des valeurs obtenue suite à l'insertion dudit au moins un tuple modifié (tu') est modifiée 3059446 20 d'une quantité prédéfinie 4 en fonction de la force d'insertion a, sans modifier le type du groupe identifié. 3. Procédé selon la revendication précédente, caractérisé en ce que, si le groupe 5 identifié lors de l'étape d'identification (E3) est un groupe porteur d'au moins un bit ou symbole (si) à insérer dans ledit groupe (G,), la valeur dudit au moins un attribut (An) dudit au moins un tuple à insérer (tu) est modifiée selon au moins une règle de codage pour dissimuler ledit au moins un bit ou symbole dans ledit groupe, ladite règle de codage étant préalablement définie 10 et stockée dans les métadonnées de tatouage (M). 4. Procédé selon l'une quelconque des revendications précédentes, caractérisé qu'il comprend une étape préalable de configuration (E01), lors de laquelle on définit une clé secrète et des paramètres de tatouage sélectionnés parmi 15 ledit au moins attribut à tatouer, une force d'insertion, un ou plusieurs nombres de groupe de tuples à générer, une séquence de symboles à dissimuler dans ladite base de données. 5. Procédé selon la revendication 1, caractérisé en ce qu'il comprend une étape 20 préalable de tatouage intégral (E02) de la base de données (3) en fonction des métadonnées de tatouage (M). 6. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'accès aux métadonnées de tatouage (M) et l'accès à la base de 25 données (3) sont respectivement protégés par des données d'authentification et/ou d'identification distinctes. 7. Procédé selon la revendication précédente, caractérisé en ce que les droits de lecture et d'écriture associés aux métadonnées de tatouage (M) ne sont pas 30 accordés à un utilisateur de la base de données (3). 3059446 21 8. Programme d'ordinateur (P) comprenant les instructions adaptées à la mise en oeuvre des étapes du procédé selon l'une quelconque des revendications précédentes, lorsque ledit programme est exécuté sur un ordinateur. 5 9. Moyen de stockage d'informations (24), amovible ou non, partiellement ou totalement lisible par un ordinateur ou un microprocesseur comportant les instructions de code d'un programme d'ordinateur pour l'exécution des étapes du procédé selon l'une quelconque des revendications 1 à 7. 10 10. Serveur (2) adapté pour exécuter les instructions adaptées pour la mise en oeuvre des étapes du procédé selon l'une quelconque des revendications 1 à 7.