FR2935058A1 - Outil de verification informatique - Google Patents

Abstract

Un outil de vérification informatique, propre à traiter répétitivement une pluralité de jeux de données qui comprennent des données réparties selon une loi statistique. L'outil comprend un estimateur (8), capable d'établir pour un jeu de données une valeur caractérisant la reproduction, d'un critère relatif aux données qu'il contient, un pilote (6), agencé pour appeler l'estimateur (8) avec une pluralité de jeux pour déterminer une pluralité de valeurs, et pour établir une nouvelle pluralité de jeux à partir de la pluralité de valeurs, et pour répéter l'appel de l'estimateur (8) avec une nouvelle pluralité de jeux établie précédemment, jusqu'à vérifier une condition qui fait intervenir un extremum de ladite pluralité de valeurs et/ou du nombre de répétitions. L'outil comprend également un mélangeur (10), capable d'établir un nouveau jeu de données, sur la base d'un jeu de données existant, en maintenant la répartition selon la loi statistique, et le pilote (6) est agencé pour appeler le mélangeur (10) avec certains au moins des jeux de données en fonction d'une règle basée sur la pluralité de valeurs associée à ces jeux.

Description

INRIA91 0 5 8 Outil de vérification informatique L'invention concerne un outil de vérification informatique pour la détermination d'évènements rares. Le domaine de la gestion des droits numériques a connu un essor considérable avec le développement de l'Internet. En effet, ce développement a permis d'augmenter les volumes d'échanges entre personnes éloignées, et a été accompagné par le besoin de mettre en place des mesures de protection des droits d'auteurs. Plusieurs systèmes existent qui permettent de gérer les droits numériques. Certains systèmes sont basés sur l'adjonction de "verrous numériques" aux fichiers concernés, par le biais de certificats numériques. Ces solutions sont assez intrusives et posent des problèmes d'interopérabilité. D'autres systèmes reposent sur une analyse des fichiers pour trouver un marquage particulier appelé filigrane ("watermark" en anglais) qui permet d'obtenir des informations insérées dans les données du fichier lui-même.

En ce qui concerne les fichiers multimédia, du type film, musique et autre, les algorithmes de marquage par filigrane ont connu un remarquable essor car ils sont moins contraignants pour l'utilisateur final, sont complexes à contourner, et offrent une bonne interopérabilité. Cependant, ces algorithmes ne sont pas imperméables, et il est crucial avant de les adopter de connaître leurs taux d'erreur, c'est-à-dire la probabilité d'un faux positif (un fichier est considéré comme marqué/protégé alors qu'il ne l'est pas), et d'un faux négatif (un fichier considéré comme non marqué/protégé alors qu'il l'est). La détermination de la probabilité des faux positifs est particulièrement cruciale, car il relève là de la crédibilité de la société qui met en place l'algorithme de marquage, comme les utilisateurs apprécient très peu d'être accusés à tort et de ne pas pouvoir accéder à des contenus qu'ils ont obtenus légalement. 1 2 2935058 Il n'existe actuellement aucune méthode réellement fiable et n'ayant pas un coût prohibitif qui permette de tester ces algorithmes pour déterminer la probabilité de faux positif car celle-ci est très petite. L'invention vient améliorer la situation. 5 À cet effet, l'invention propose un outil de vérification infottttatique, propre à traiter répétitivement une pluralité de jeux de données, chaque jeu de données comprenant des données réparties selon une loi statistique choisie. L'outil comprend un estimateur, capable d'établir pour un jeu de données une valeur caractérisant la reproduction, par ce jeu de données, d'un critère relatif aux données qu'il 10 contient, et un mélangeur, capable d'établir un nouveau jeu de données, sur la base d'un jeu de données existant, en maintenant la répartition selon la loi statistique choisie. L'outil comprend en outre un pilote, agencé pour appeler l'estimateur à partir d'une pluralité de jeux de données pour déterminer une pluralité de valeurs, pour appeler le mélangeur avec certains au moins des jeux de données sur la base d'une règle basée sur 15 ladite pluralité de valeurs, et pour répéter l'appel de l'estimateur et du mélangeur à chaque fois avec une pluralité de nouveaux jeux de données établis précédemment, jusqu'à vérifier une condition qui fait intervenir un extremum de ladite pluralité de valeurs et/ou du nombre de répétitions. Cet outil est extrêmement avantageux car il permet de calculer la probabilité d'un faux 20 positif de manière rapide et fiable. L'invention concerne également un procédé de vérification informatique, propre à traiter répétitivement une pluralité de jeux de données, comprenant les étapes suivantes, a) prévoir une fonction d'estimation d'un jeu de données, caractérisant la reproduction, par ce jeu de données, d'un critère relatif aux données qu'il contient, 25 b) prévoir une fonction de génération de jeu de donnée aléatoire, chaque jeu de données comprenant des données réparties selon une loi statistique en entrée, c) produire une pluralité de jeux de données d'entrée en appelant répétitivement la fonction de génération, 3 2935058 d) appliquer la fonction d'estimation à certains au moins de la pluralité de jeux de données d'entrée, ce qui donne une pluralité de valeurs, e) sélectionner une sous pluralité de jeux de données à partir de ladite pluralité de valeurs, en fonction d'une règle basée sur la pluralité de valeurs associée à ces jeux, 5 f) établir une nouvelle pluralité de jeux de données par perturbations des jeux de données de ladite sous pluralité, g) répéter sélectivement les étapes d) à g) avec à chaque fois la nouvelle pluralité de jeux de données, jusqu'à vérifier une condition de fin d'itération, qui fait intervenir un extremum de la valeur et/ou du nombre d'itérations. 10 D'autres caractéristiques et avantages de l'invention apparaîtront mieux à la lecture de la description qui suit, tirée d'exemples donnés à titre illustratif et non limitatif, tirés des dessins sur lesquels : - la figure 1 représente une vue schématique d'un outil selon l'invention ; la figure 2 représente un diagramme général de fonctionnement de l'outil de la 15 figure l ; les figures 3 à 6 représentent des exemples de mises en oeuvre particulières de fonctions des opérations de la figure 2 et ; la figure 7 représente un autre mode de réalisation d'une opération de la figure 2. Les dessins et la description ci-après contiennent, pour l'essentiel, des éléments de 20 caractère certain. Ils pourront donc non seulement servir à mieux faire comprendre la présente invention, mais aussi contribuer à sa définition, le cas échéant. La présente description est de nature à faire intervenir des éléments susceptibles de protection par le droit d'auteur et/ou le copyright. Le titulaire des droits n'a pas d'objection à la reproduction à l'identique par quiconque du présent document de brevet 25 ou de sa description, telle qu'elle apparaît dans les dossiers officiels. Pour le reste, il réserve intégralement ses droits. 4 Les algorithmes de marquage par filigrane trouvent de nombreuses applications de nos jours. Un exemple d'application de ces algorithmes est la protection contre la copie. Dans cette application, l'algorithme est installé sur un dispositif numérique, par exemple un 5 caméscope. Le caméscope est agencé pour appeler l'algorithme à chaque fois qu'un contenu auquel il accède doit être copié/enregistré. L'algorithme analyse le flux de données du contenu et détermine si celui-ci est protégé ou pas. Si le contenu est protégé, le caméscope bloque tout enregistrement de ce contenu. 10 Dans cette application, la présence d'un faux positif est particulièrement gênante, car un utilisateur qui filme ses vacances ne tolèrera jamais de perdre ce contenu parce que son caméscope s'est "trompé". Un autre exemple d'application de ces algorithmes est le traçage. Lorsqu'un utilisateur achète un contenu, il est intéressant pour le vendeur de marquer la copie vendue pour 15 être capable de l'identifier plus tard. Ainsi, si cette copie se retrouve sur Internet, c'est-à-dire si l'utilisateur l'ayant acheté décide de la partager illégalement sur un réseau P2P par exemple, il est possible pour le vendeur de confondre l'utilisateur indélicat. Là encore, la présence d'un faux positif est particulièrement gênante, car les utilisateurs 20 n'aiment pas non plus être accusés à tort. Les algorithmes de marquage à filigrane doivent être aussi fiables que possible. Pour cela, les industriels se réunissent pour définir des standards permettant de qualifier la fiabilité de ces algorithmes. Ainsi, le Copy Protection Working Group du consortium DVD Forum a établi que, dans 25 le cadre de la protection contre la copie, un algorithme de marquage est fiable tant qu'un faux positif n'est détecté que toutes les 400 heures de vidéos. 2935058 Dans le cadre de ces travaux, les détections sont réalisées toutes les 10 secondes environs. Cette exigence définit donc une probabilité de faux positif de l'ordre de 10-5 environ. Une expérience fiable pour valider cette probabilité demanderait donc l'analyse de plus 5 de 40 000 heures de film non marqué, soit plus de 4 années complètes. Cela n'est pas réalisable. Les applications de traçage exigent une fiabilité comparable, et posent donc les mêmes problèmes. Le problème qui se pose est donc la capacité de déterminer des probabilités d'évènements rares (la présence d'un faux positif) avec un coût raisonnable. Des travaux existent dans plusieurs domaines, notamment la physique des particules (Kahn et Harris 1951), les télécommunications (Bayes 1970, Villén-Altamirano et Villén-Altamirano 1994), et le contrôle aérien (Krystul et Blom, 2005). Cependant, ces travaux reposent sur des hypothèses qui ne sont pas applicables au domaine du marquage et/ou traçage par filigrane : ils supposent un modèle intrinsèque d'évolution en temps qui n'est pas valable pour l'application recherchée. Une autre méthode est de mettre en oeuvre la méthode de Monte Carlo. Cependant, cette méthode n'est pas applicable dans ce cas, car elle présente un coût de calcul prohibitif au vu des probabilités recherchées.

La figure 1 représente une vue schématique d'un outil 2 selon l'invention. L'outil 2 comprend une mémoire 4, un pilote 6, un estimateur 8 et un mélangeur 10. Dans l'exemple décrit ici, l'outil 2 est un ordinateur. Cependant, l'invention s'applique à tout ensemble d'outils ou de dispositifs propres à mettre en oeuvre les éléments de l'outil 2, comme une puce spécialisée (par exemple de type FPGA), un circuit imprimé générique ou spécialisé (par exemple de type ASIC), une puce à système intégré (par exemple de type SOC) ou autre. Par ailleurs, la mémoire 4 peut être réalisée de toute manière connue de l'homme du métier, par exemple sous la forme d'un disque dur, d'une mémoire optique de type CD 6 ou DVD ou autre, et n'est pas nécessairement rassemblée physiquement avec les autres éléments de l'outil 2. Ainsi, la mémoire 4 peut être accédée par réseau, ou par tout autre moyen que l'homme du métier connaît. En outre, l'estimateur 8 et le mélangeur 10 décrits ici sont des éléments logiciels qui sont physiquement stockés sur la mémoire 4 et qui sont appelés et mis en oeuvre par le pilote 8. En tant que tels, ces éléments peuvent être paramétrés et ou mis à jour en fonction des besoins. Cependant, ces éléments pourraient être des fonctions gravées dans une puce formant l'outil 2, ou présenter des verrous physiques et/ou logiques pour empêcher leur modification. L'outil 2 fonctionne en appliquant un algorithme qualifié de méthode Monte-Carlo multi-niveaux. Cet algorithme repose sur le principe général de : déterminer les scores d'une population par rapport à une fonction de mesure ; sélectionner les éléments de la population qui ont un score supérieur à une valeur donnée ; et remplacer les autres éléments par des éléments aléatoires, et recommencer. Comme cela apparaîtra mieux dans la suite, des modifications et autres subtilités sont apportées à ce principe général. Ainsi, l'outil 2 opère en divisant un problème principal (trouver des évènements extrêmement rares de manière fiable et en peu de temps) en une multitude de problèmes plus simples mais corrélés (trouver des évènements moins rares, et trier parmi ceux-là les plus favorables), comme cela est expliqué par la formule suivante : P(AN) = P(ANIAN-1)*P(AN4 IAN-2)*. ..* P(A2IA1)*P(A1) où les A, sont des évènements imbriqués. À ce jour, la méthode de Monte Carlo multi-niveaux adaptative n'a pas connu d'application dans le domaine de la détection/génération d'évènements rares. Le seul article connu qui s'y rapporte est un article théorique : "Adaptative multilevel splitting 7 2935058 for rare event analysis" par Cérou et Guyader, 2007, Stochastic Analysis and Applications, Vol 25, Issue 2, pp 417-443. Dans cet article, une approche adaptative est proposée pour définir progressivement les niveaux de la méthode de Monte Carlo multi-niveaux, qui est appliquée à un cas où les 5 jeux de données ou éléments sont dynamiques. Par dynamique, on entend le fait que ces éléments sont des trajectoires qui évoluent de manière continue dans le temps selon un modèle intrinsèque d'évolution donné par la nature physique du problème étudié. Les trajectoires sont simulées et répétitivement sélectionnées pour choisir celles offrant 10 le meilleur score, c'est-à-dire les séquences atteignant un état maximal sur la période d'observation. L'étape de remplacement consiste à remplacer les éléments de score inférieur par le minimum des éléments de score supérieur. Cet article est principalement une démonstration mathématique de la faisabilité et de la fiabilité de la méthode de Monte Carlo multi-niveaux adaptative dans le cadre restreint 15 où les éléments ont une dynamique fixée par la nature du problème étudié. Comme les travaux plus anciens mentionnés plus haut, cet article suppose la présence d'un modèle intrinsèque d'évolution en temps que nous n'avons pas ici, et ne peut donc être appliqué tel quel. Le problème de l'application de cet algorithme aux problèmes décrits ci-dessus est qu'il 20 est complexe de remplacer les éléments dont le score est insuffisant de manière satisfaisante. Cela est principalement dû au fait que les populations associées aux problèmes décrits plus haut présentent des caractéristiques statistiques différentes. En fait, dans ce cadre, la méthode de Monte Carlo multi-niveaux semble a priori peu appropriée, et difficile à 25 mettre en oeuvre. En effet, l'étape de remplacement avec des nouveaux éléments qui, d'une part respectent les caractéristiques statistiques particulières, et qui, d'autre part forment des points de 8 2935058 départ favorables pour trouver d'autres évènements rares conditionnés par les évènements de score élevé, est particulièrement complexe à mettre en oeuvre. La figure 2 représente une vue schématique du fonctionnement de l'outil 2. Comme on peut le voir sur cette figure, l'outil part d'une opération d'initialisation 30. Ensuite, il 5 effectue une boucle qui comprend une opération de sélection 40, une opération de mélange 50, et qui se termine par une condition de fin de boucle 52. Enfin, en sortie de la boucle, une opération 60 renvoie la probabilité d'évènement rare qui vient d'être calculée. L'événement rare recherché est défini comme étant le fait qu'un élément distribué 10 suivant une loi de répartition imposée par le problème étudié possède un score supérieur à un certain seuil. Les opérations 30 à 60 vont maintenant être décrites plus en détail avec des exemples de mise en oeuvre représentés sur les figures 3 à 6. La figure 3 représente un exemple de mise en oeuvre de l'opération 30 de la figure 2. 15 Cette opération a pour fonction l'initialisation des éléments qui vont servir à la détermination de probabilité d'évènement rare, ainsi que l'initialisation du premier niveau adaptatif. Dans une étape 300, un compteur i est initialisé à 1. Une boucle commence alors, qui comprend la répétition d'une opération 310 de génération d'élément, et une opération 20 320 de calcul de score de l'élément généré dans l'opération 310. Une condition de fin de boucle 330 détermine si le compteur i a atteint le nombre d'éléments n que l'on souhaite simuler simultanément ou pas. Lorsque ça n'est pas le cas, le compteur i est incrémenté en 340 et la boucle reprend. Dans l'opération 310, une fonction gen() reçoit en argument une loi statistique px pour 25 générer un élément x[i]. Dans l'opération 320, l'élément x[i] qui vient d'être généré est transmis comme argument à une fonction sc() qui détermine le score de cet élément. Ce score est stocké dans un élément dx[i].

Dans une réalisation particulière de l'invention, un élément x[i] est un pointeur vers un contenu numérique ou une sous-partie d'un contenu numérique telle que une sélection rectangulaire d'une image fixe, une portion de bande sonore entre deux instants donnés, une image extrait d'un film vidéo.

La fonction gen() de l'opération 310 tire au hasard un contenu numérique de ce type, parmi un grand ensemble de contenus mis à la disposition de l'invention, ainsi qu'une portion choisie au hasard de ce contenu.

Dans cette réalisation, la fonction sc() de l'opération 320 est une mesure de vraisemblance du fait que le-contenu numérique indiqué par le pointeur x[i] contient le filigrane recherché.

Dans une autre réalisation particulière de l'invention, un élément x[i] est un mot binaire de plusieurs bits identifiant des utilisateurs d'un service de vente de contenus. La fonction gen() est l'algorithme utilisé par ce service pour créer et attribuer ces identifiants. Dans cette réalisation, la fonction gen() assure qu'un identifiant donné n'est attribué qu'à un seul utilisateur du service.

La fonction sc() est une mesure de la vraisemblance du fait que l'identifiant x[i] a servi à créer une copie illégalement re-distribuée sur un réseau d'échange de données. Dans l'exemple décrit ici, x[] est un tableau qui reçoit les éléments successifs utilisés pour déterminer/générer un élément qui respecte la loi statistique px et qui est un évènement rare par rapport à la loi de mesure que représente la fonction scO.

De même que x[], dx[] est un tableau qui stocke tous les scores des éléments de x[] dans une itération de simulation donnée.

De nombreuses mises en oeuvre sont possibles pour x[] et dx[] autre que des tableaux, et l'homme du métier saura les reconnaître. On citera juste en exemple les piles, ou les listes, ou encore les variables à convention de nommage.

En outre, bien que les opérations 310 et 320 aient été décrites dans la même boucle, elles pourraient être exécutées dans des boucles séparées. À la sortie de cette boucle d'initialisation, un compteur N d'itérations de simulation est initialisé à 1 dans une opération 350. Ensuite, le premier niveau S[N] (N=1) est établi par une fonction max() dans une opération 360.

La fonction max( reçoit en argument le tableau des scores courant dx[] et un paramètre 5 de sélection k, et renvoie le k-ième score le plus élevé du tableau dx[]. Comme on le

verra plus bas, le paramètre k est le nombre d'éléments qui sont conservés pour

l'itération suivante, les n-k autres éléments étant retirés.

La fonction max( peut être mise en oeuvre de diverses manières. Un exemple efficace de mise en oeuvre est de trier le tableau dx[] par ordre de valeurs décroissantes, et de 10 récupérer la valeur du k-ième élément.

D'autres mises en oeuvre sont possibles, comme l'utilisation d'un tableau dx[] directement trié, ou l'utilisation d'un algorithme ne triant pas le tableau dx[] et déterminant directement le k-ième score le plus élevé.

Une fois la fonction max() terminée, l'opération d'initialisation 30 se termine en 370.

15 La figure 4 représente un exemple de mise en oeuvre de l'opération 40 de la figure 2. Cette opération réalise la première partie de chaque itération, c'est-à-dire la sélection des k meilleurs éléments qui serviront de base au mélange de l'opération 50.

L'opération 40 part donc d'une opération 400 dans laquelle un compteur i et un compteur m sont initialisés à 1. Ensuite, dans une opération 410, un test détermine si

20 l'élément x[i] a un score correspondant dx[i] supérieur au seuil du niveau courant S[N]. Si c'est le cas, dans une opération 420, cet élément est recopié dans un tableau y[] en tant qu'élément y[t]. De même, dans une opération 430, le score dx[i] de cet élément est

recopié dans un tableau dy[] en tant qu'élément dy[t]. Enfin, en 440, le compteur t est incrémenté.

25 Ensuite, ou lorsque le score de l'élément dx[i] de l'élément x[i] est strictement inférieur au seuil S[N] courant, un test 450 détermine si tous les éléments x[i] ont été parcourus. Lorsque ça n'est pas le cas, le compteur i est incrémenté en 460. Sinon, l'opération se termine en 470. 11 2935058 On notera que, de par la définition du seuil S[N] comme k-ième score le plus élevé de dx[], le tableau y[] contient exactement k éléments. Ces k éléments vont servir de base dans l'opération 50 au mélange et à la convergence de l'algorithme. La figure 5 représente un exemple de mise en oeuvre de l'opération 50 de la figure 2.

L'opération 50 est une boucle qui part des éléments sélectionnés du tableau y[], et qui va mélanger ou perturber chacun de ses éléments un nombre de fois de l'ordre de nlk. Ce mélange a pour but de "déplacer" les éléments de manière à converger vers un élément plus rare. Pour s'assurer de cette convergence, une partie de cette opération s'assure que le score des éléments "mélangés" progresse, et on ne garde à nouveau que les éléments mélangés qui ont un score favorable. Sinon, on les remplace par l'élément non perturbé correspondant. Par ailleurs, la mise en oeuvre décrite ici suppose que k divise n, c'est-à-dire que n!k est un nombre entier. La figure 7 montre une variante qui s'affranchit de cette limite.

L'opération 50 comprend ici deux boucles principales : une première boucle qui fait croître un compteur i pour mélanger successivement les éléments du tableau y[] ; une deuxième boucle, qui est interne à la première boucle, pour mélanger n/k fois chaque élément de y[i], et pour conserver les meilleurs éléments mélangés.

L'opération 50 commence donc en 500 par la mise à 1 du compteur i. Elle est suivie en 502 par la mise à 1 du compteur j. La deuxième boucle commence alors avec une première perturbation de l'élément y[i] en 510. Cette perturbation est réalisée au moyen d'une fonction mel() qui reçoit y[i] comme argument et appelle le mélangeur 10 avec cet argument ainsi qu'avec un paramètre contrôlant la force de la perturbation. En retour, le mélangeur 10 renvoie un nouvel élément z, qui est une perturbation de manière aléatoire de l'élément y[i], qui conserve néanmoins la même loi statistique px 12 2935058 que les x[i]. De fait, l'élément z se situe, dans l'espace des possibles, dans un voisinage de l'élément y[i]. La taille de ce voisinage est fonction de la force de la perturbation, et peut donc être contrôlée avec le paramètre p,. Un exemple de cette perturbation peut aisément être donné avec une population de base 5 dont la répartition est selon la loi gaussienne. Alors, le mélangeur peut être un générateur de bruit gaussien, d'intensité donnée par le paramètre 1.1 pour assurer un déplacement suffisant pour explorer l'espace des possibles, mais non excessif pour rester utile. Dans cet exemple, ce bruit gaussien est ajouté à l'élément y[i], la somme étant ensuite normalisée pour retrouver une loi gaussienne de 10 même variance que les élément x[i]. Pour d'autres lois statistiques, d'autres mises en oeuvre sont possibles. Il peut également être possible d'utiliser un mélangeur générique qui repose sur l'algorithme de Metropolis-Hastings (voir par exemple l'ouvrage "Monte Carlo : concept, algorithms and applications" par G. Fishman, Springer-Verlag, New-York, 1996), ce qui le rend 15 alors compatible avec la plupart des lois statistiques respectée par les éléments x[i]. Dans le cas d'une réalisation de l'invention basée sur des contenus numériques, le mélangeur modifie le contenu numérique de manière aléatoire mais contrôlée. Par exemple, le mélangeur peut être un des processus décrits dans l'article scientifique Stochastic Image Warping for Improved Watermark Desynchronization , de Angela 20 D'Angelo, Mauro Barni, et Neri Merhav, parue dans la revue EURASIP Journal on Information Security, Volume 2008 (2008), Article ID 345184, doi:10.1155/2008/345184. Plus simplement, si y[i] est un pointeur vers une portion d'un contenu numérique, le mélangeur modifie de façon aléatoire la sélection du contenu : par exemple, sur une 25 bande sonore, le passage sélectionné par le nouveau pointeur z est décalé de p. micro-secondes, aléatoirement vers le passé ou vers le futur par rapport au passage sélectionné par y[i]. Une fois l'élément y[i] ainsi mélangé, la valeur du score de l'élément z, sc(z), est calculée et comparée au seuil du niveau courant S [N] dans une opération 520.

Si sc(z) est supérieur à S[N], alors l'élément mélangé est plus performant que l'élément y[i] original, c'est-à-dire plus rare.

Alors, dans une opération 530, l'élément de x[] d'indice j+(i-1)*n/k, ce qui correspond à l'indice global de la j-ième itération de la deuxième boucle dans la i-ième itération de la première boucle, est remplacé par z. Dans une opération 532, l'élément de dx[] de même indice est également remplacé par sc(z).

Si sc(z) est inférieur à S[N], alors l'élément mélangé est moins performant que l'élément y[i] original, c'est-à-dire moins rare.

Alors, dans une opération 540, l'élément de x[] d'indice j+(i-1)*n/k, ce qui correspond à l'indice global de la j-ième itération de la deuxième boucle dans la i-ième itération de la première boucle, est remplacé par y[i], c'est-à-dire que y[i] est dupliqué. Dans une opération 542, l'élément de dx[] de même indice est également remplacé par dy[i].

Ensuite, dans une opération 550, on vérifie si la deuxième boucle est terminée, c'est-à-dire si l'élément y[i] de la i-ième itération de la première boucle a été répliqué n/k fois.

Si ce n'est pas le cas, le compteur j est incrémenté en 552, et la deuxième boucle reprend en 510, avec le mélange à nouveau de l'élément y[i] courant.

Si la deuxième boucle est finie, on vérifie dans une opération 560 si tous les éléments de y[] ont été parcourus, c'est-à-dire si c'est la fin de la première boucle. Lorsque cela n'est pas le cas, le compteur i est incrémenté dans une opération 562, et la première boucle recommence avec le nouveau compteur i en 502.

Si tous les éléments de y[] ont été parcourus, alors dans une opération 570 on incrémente le compteur de niveau N, et en 572 on définit le seuil du niveau courant de manière identique à l'opération 360.

Enfin, l'opération 50 se termine en 580, avec l'appel de la condition 52 de fin d'itération. 25 Cette condition est ici double :

si le seuil du niveau courant S[N] est supérieur au seuil d'arrêt S, c'est-à-dire que l'on a détecté l'évènement rare recherché ; ou si le compteur de niveau N est supérieur à un nombre d'itérations maximal.

La deuxième condition permet d'éviter à l'algorithme de boucler indéfiniment en cas de non convergence due à un paramétrage incorrect. À ce jour, la Demanderesse n'a néanmoins pas constaté de non convergence de l'algorithme mis en oeuvre par l'outil 2.

Si on analyse bien l'opération 50, on voit donc que l'outil 2 présente une adaptation très particulière aux problèmes posés par les évènements rares liés au marquage et au traçage.

En effet, comme on l'a déjà mentionné plus haut, contrairement au contexte de l'article

"Adaptative multilevel splitting for rare event analysis", les évènements étudiés ne sont 10 pas caractérisés par une quelconque évolution dynamique qui favorise la convergence de l'algorithme.

L'outil 2 vient pallier ce manque de plusieurs manières :

chaque élément favorable d'une itération donnée est perturbé n/k fois à l'itération suivante, ce qui permet de tenir compte du fait que les faux positifs recherchés sont 15 assez spécifiques ;

cette perturbation est spécifique à la loi statistique observée par les éléments ;

la valeur du paramètre contrôlant la force de perturbation lors de la mise en oeuvre du mélangeur ainsi que la taille du voisinage dans lequel se situe l'élément en sortie du mélangeur par rapport à l'élément en entrée du mélangeur

20 est ou bien choisie par l'utilisateur de l'invention, ou bien fixée de manière adaptative pour chaque itération de l'invention ;

- seuls les éléments mélangés les plus performants sont conservés ù sinon ils sont remplacés par l'élément de y[] dont ils sont issus - ce qui accélère la convergence ; et

- tous les éléments sont mélangés, y compris les y[i] de l'itération précédente, ce

25 qui permet de créer la dynamique qui n'existe pas dans les phénomènes observés du fait de leur nature même. 15 En outre, la valeur du paramètre 1.t peut être modifiée de façon automatique au fur et à mesure des itérations, ce qui rend alors la dynamique ainsi créée variable. Une fois les itérations de convergence vers l'évènement rare terminées, l'opération 60 vient retourner la probabilité exacte associée aux itérations concernées, qui est donc un 5 estimateur de la probabilité cherchée. L'opération 60 part ainsi en 600 par l'initialisation d'un compteur 1, et se poursuit en 610 par l'initialisation d'un autre compteur i. Le principe est de parcourir les x[i] établis à la dernière itération pour déterminer le nombre d'entre eux qui est supérieur au seuil S qui est une des deux conditions d'arrêt 10 des itérations. Ainsi, pour chaque x[i] tel que dx[i] est supérieur à s, le compteur 1 est incrémenté en 630, et en 640 on teste si tous les x[i] ont été parcourus. Si ce n'est pas le cas, alors le compteur i est incrémenté en 650 et l'opération 620 répétée avec l'élément x[i] suivant. Ainsi, lorsque tous les x[i] ont été parcourus, on sait si les itérations ce sont arrêtées 15 pour non convergence ou pas selon la valeur de 1. En effet, si à la fin de cette boucle, 1 est inférieur à k, alors on a trouvé un certain nombre d'évènements rares, mais pas tous avec un score supérieur à t avec la probabilité (k/n)^N. On retourne donc la probabilité Res =1*k^(N-1)/n^N. En effet, comme on l'a vu avec la 20 formule de la méthode de Monte Carlo multi-niveaux, la probabilité Res associée au (N-1)-ième niveau est le produit des probabilités conditionnelles des niveaux précédents, soit (k/n)^(N-1), par la probabilité conditionnelle du N-ième niveau, soit 1/N. Enfin l'opération 60 se termine en 680. Comme on vient de le voir, on a donc construit séquentiellement des évènements de 25 plus en plus rares par rapport à la fonction de mesure se(), chaque évènement respectant la loi statistique px de base. 16 En outre, on notera que les éléments de x[] de la dernière itération donnent des exemples de tels évènements. La figure 7 montre un autre exemple de réalisation de l'opération 50. Dans ce mode de réalisation, k ne divise pas n, et l'opération 50 n'est plus réalisée par l'imbrication de deux boucles, mais suit le même raisonnement de mélange des y[i] avec sélection des meilleurs éléments. Ainsi, l'opération commence en 701 pas' la génération d'un tableau de permutation des entiers entre 1 et k. Ce tableau est le résultat d'une fonction Permut() qui reçoit l'entier k en entrée, et génère de manière aléatoire un tableau dont chaque élément comprend un entier entre 1 et k, chaque élément étant présent une unique fois dans Perm[]. Ensuite, une boucle commence dans laquelle le tableau aléatoire Perm[] est utilisé pour remplir un tableau d'indices Ind[] qui va servir au mélange des y[i]. Plus précisément, la boucle commence par l'initialisation d'un compteur 1 à 1 en 702, et se poursuit en 703 avec le remplissage de l'élément Ind[l] avec la valeur de Perm[mod(l, 15 k)], où mod(l,k) est la fonction modulo, qui retourne le reste de la division de 1 par k. Ensuite, en 704, on teste si tout le tableau d'indice Ind[] a été rempli. Si ce n'est pas le cas, 1 est incrémenté en 705 et la boucle de remplissage reprend en 703. Sinon, on commence alors le mélange des y[i] avec l'initialisation en 707 d'un compteur j à 1. Une boucle est alors lancée pour mélanger les y[i] et sélectionner les meilleurs 20 éléments, avec en 708, l'indice i qui reçoit la valeur de Ind[j]. Ensuite, les opérations 710, 720, 730, 732, 740 et 742 sont effectuées de manière identique aux opérations 510, 520, 530, 532, 540 et 542, à cela près que l'indice j remplace l'indice j+(i-1)n/k du fait de la nouvelle manière de mélanger. Cette boucle est conditionnée par un test 760 sur j pour voir s'il reste des éléments à 25 mélanger. Dans ce cas, le compteur j est incrémenté en 762 et la boucle reprend en 707. Dans le cas contraire, l'opération 50 se termine avec des opérations 770, 772 et 780 identiques aux opérations 570, 572 et 580.

Cette mise en oeuvre est particulièrement intéressante, car il n'est plus nécessaire que k divise n, et on maintient le même état d'esprit que l'opération 50 de la figure 5, comme les y[i] sont répliqués en moyenne n/k fois au moyen des opérations 701 à 707.

Cela permet donc de mieux paramétrer l'outil 2 en choisissant un nombre n et un nombre k de manière judicieuse.

Les expériences de la Demanderesse ont démontré qu'un nombre d'éléments relativement faible, par exemple n=12800 permettait de fournir des résultats extrêmement satisfaisants.

Deux autres paramètres outre n commandent la convergence et sa qualité:

- le paramètre k qui détermine le nombre d'éléments rejetés à chaque itération ;

le paramètre g, qui détermine l'exploration qui est faite de l'espace des possibles. Ainsi, plus k est proche de n, et plus la précision de l'outil est élevée, mais en même temps plus la convergence est lente, comme on rejette peu d'éléments.

La Demanderesse a observé les faits suivants :

- un rapport k/n = 9/10 est très précis mais lent ;

un rapport k/n = 1/2 est relativement moins précis mais très rapide ; et

- un rapport k/n = 3/4 est un bon compromis qui donne une bonne qualité et une convergence assez rapide, mais avec quelques variations dans le nombre d'itérations nécessaires pour converger.

Parallèlement, la Demanderesse a également observé que :

un g faible n'est pas bon pour la convergence, car l'espace des éléments n'est pas correctement exploré dans les premières itérations de l'invention ;

- un g élevé tend à faire diverger l'algorithme car il mélange "trop" les y[i] dans les dernières itérations.

En variante, l'invention prévoit une méthode pour fixer la valeur du paramètre de manière automatique. Une valeur trop grande a pour effet de rejeter beaucoup d'éléments z lors de l'opération 520 (ou 720).

L'invention passe alors trop souvent par les opérations 540 et 542 (respectivement 740 et 742) aux dépens des opérations 530 et 532 (respectivement 730 et 732).

Dans cette variante, un compteur calcule combien de fois l'invention est passée en 540 (respectivement 740) au cours de l'opération 50. A la fin de l'opération 50, si ce compteur est supérieur à une certaine fraction de n (par exemple 0,7*n), alors l'opération 50 est annulée car cela est interprété comme une indication que le paramètre est trop fort.

Le paramètre N n'est alors pas incrémenté, les tableaux x[] et dx[] ainsi que tous les compteurs de l'opération 50 sont remis à zéro. Le paramètre est diminué d'un pourcentage choisi, par exemple 10 %.

L'opération 50 recommence alors avec cette nouvelle valeur de . Ceci est fait jusqu'à ce que le compteur soit inférieur à la fraction de n mentionné plus haut, assurant ainsi que les perturbations sont réalisées, c'est à dire les opérations 530 et 532 (respectivement 730 et 732) un nombre confortable de fois.

Enfin, le nombre maximal d'itérations a été limité à N=100. En pratique, très peu de cas ont généré un arrêt à cause de cette limite.

Les probabilités recherchées dans le cadre des problématiques de traçage sont de l'ordre de 10^-12.

Cela signifie qu'une simulation par la méthode de Monte Carlo classique nécessiterait un nombre de l'ordre de 101'12 tirages dans le meilleur des cas pour obtenir des résultats fiables.

À titre de comparaison, pour n=12800 et k=9600, l'outil 2 converge vers une solution avec environ 10''6 tirages. Les résultats sont donc exceptionnels.

Afin de s'assurer de la fiabilité de l'opération effectuée par l'outil 2, et grâce aux gains considérables obtenus grâce à celui-ci, il est même possible d'effectuer une centaine de fois l'outil 2 avec les mêmes paramètres.

On constate alors que celui-ci est extrêmement stable, et qu'il converge avec un nombre relativement constant, à une ou deux itérations près. Cela permet donc d'établir en plus un intervalle de confiance pour l'outil 2.

D'autre part, les seuils intermédiaires stockés dans le tableau S[] peuvent être utilisés. Ils donnent une estimation de la courbe qui associe un seuil à une probabilité d'événement rare, en donnant des points approximatifs sur cette courbe : seuil S [i] pour une probabilité (k/n)^i.

Lors de la création du détecteur de marquage, il est important de donner le seuil à partir duquel une mesure de vraisemblance supérieure à celui-ci force le détecteur à décider de la présence du marquage.

De même, lors de la création d'un traceur d'utilisateurs malhonnêtes, il est important de donner le seuil à partir duquel une mesure de vraisemblance supérieure entraînera le traceur à accuser le client suspecté.

Dans les deux cas, les seuils sont à fixer de telle sorte que la probabilité de faux positif (détecter un marquage alors qu'il n'y en a pas, ou accuser un innocent) soit inférieure à une certaine donnée du cahier des charges.

Le tableau S[] permet de trouver une première approximation du seuil recherché. Dans cette utilisation de l'invention, le seuil S définissant l'événement rare est volontairement défini avec une valeur très importante, afin qu'un nombre maximum d'itérations soient réalisées, ce qui donne un maximum de données.

Dans ce type d'application, on peut par exemple choisir d'abord un rapport k/n égal à 1/2 pour obtenir rapidement une approximation du seuil, et ensuite recommencer avec un rapport k/n de 3/4 et avec cette approximation du seuil, pour confirmer de manière sûre la probabilité de fausse alarme.

Un exemple de mise en oeuvre de l'outil décrit plus haut est de l'embarquer sur un dispositif de détection de marquage ou de traçage, pour permettre de vérifier son bon fonctionnement.

Un tel dispositif peut opérer en retournant une valeur scalaire dont la grandeur qualifie la suspicion de présence de marquage ou de traçage. D'autres dispositifs pourront retourner une valeur binaire, indiquant la suspicion de présence de marquage ou traçage. D'autres dispositifs opéreront avec d'autres types de valeurs.

Il serait également possible de rendre l'outil accessible à distance ou par une liaison physique à ce type de dispositif, au lieu de l'embarquer. 21

Claims (14)

1. Revendications1. Outil de vérification informatique, propre à traiter répétitivement une pluralité de jeux de données (x[]), chaque jeu de données comprenant des données réparties selon une loi statistique choisie (px), l'outil comprenant : * un estimateur (8), capable d'établir pour un jeu de données (x[i]) une valeur (dx[i]) caractérisant la reproduction, par ce jeu de données, d'un critère relatif aux données qu'il contient, * un pilote (6), agencé pour appeler l'estimateur (8) avec une pluralité de jeux de données (x[]) pour déterminer une pluralité de valeurs (dx[]), et pour établir une nouvelle pluralité de jeux de données (x[]) sur la base de ladite pluralité de valeurs, et pour répéter l'appel de l'estimateur (8) à chaque fois avec une nouvelle pluralité de jeux de données (x[]) établie précédemment, jusqu'à vérifier une condition qui fait intervenir un extremum de ladite pluralité de valeurs (S) et/ou du nombre de répétitions (N), caractérisé en ce qu'il comprend un mélangeur (10), capable d'établir un nouveau jeu de données (z), sur la base d'un jeu de données existant (y[i]), en maintenant la répartition selon la loi statistique choisie (pz), et en ce que le pilote (6) est agencé pour appeler le mélangeur (10) avec certains au moins des jeux de données (y[i]), en fonction d'une règle basée sur la pluralité de valeurs associée à ces jeux.
2. 2. Outil selon la revendication 1, caractérisé en ce que ladite règle comprend la sélection des jeux de données (y[]) de valeur associée la plus élevée.
3. 3. Outil selon la revendication 2, caractérisé en ce que ledit mélangeur (10) comprend une fonction de perturbation (mel()) des jeux de données sélectionnés (y[i]).
4. 4. Outil selon la revendication 3, caractérisé en ce que ledit mélangeur (10) est agencé 25 pour appeler répétitivement certains au moins des jeux de données sélectionnés (Y[i])•
5. 5. Outil selon la revendication 4, caractérisé en ce que le mélangeur (10) est agencé pour appeler l'estimateur (8) avec le nouveau jeu de données (z), et pour remplacerle nouveau jeu de données (z) par le jeu de données dont il est tiré (y[i]) en fonction d'une règle basée sur les valeurs associées à ces jeux de données.
6. 6. Outil selon la revendication 5, caractérisé en ce que ladite règle comprend le remplacement du nouveau jeu de données (z) par le jeu de données dont il est tiré (y[i]) lorsque la valeur associée à ce jeu (dy[i]) est supérieure à la valeur associée au nouveau jeu de données (sc(z)).
7. 7. Outil selon l'une des revendications précédentes, caractérisé en ce que le critère de l'estimateur (8) est relatif à la présence d'un marquage ou d'un traçage dans le jeu de données.
8. 8. Procédé de vérification informatique, propre à traiter répétitivement une pluralité de jeux de données, comprenant les étapes suivantes, a) prévoir une fonction d'estimation (sc() d'un jeu de données, caractérisant la reproduction, par ce jeu de données, d'un critère relatif aux données qu'il contient, b) prévoir une fonction de génération (genO) de jeu de donnée aléatoire, chaque jeu de données comprenant des données réparties selon une loi statistique en entrée, c) produire (30) une pluralité (x[]) de jeux de données d'entrée en appelant répétitivement la fonction de génération (gen(), d) appliquer la fonction d'estimation (scO) à certains au moins de la pluralité (x[]) jeux de données d'entrée, ce qui donne une pluralité de valeurs (dx[]), e) sélectionner (40) une sous pluralité (y[]) de jeux de données à partir de ladite pluralité de valeurs (dx[]), en fonction d'une règle basée sur la pluralité de valeurs associée à ces jeux, f) établir (50) une nouvelle pluralité (x[]) de jeux de données par perturbations des jeux de données de ladite sous pluralité (y[]), g) répéter (52) sélectivement les étapes d) à g) avec à chaque fois la nouvelle pluralité (x[]) de jeux de données, jusqu'à vérifier une condition de find'itération, qui fait intervenir un extremum de la valeur (S) et/ou du nombre d'itérations (N).
9. 9. Procédé selon la revendication 8, caractérisé en ce que l'étape f) comprend : fl) appeler une fonction de perturbation (mel()) avec certains au moins des jeux de données de ladite sous pluralité (y[]), pour produire des jeux de données perturbés (z) reproduisant la répartition des données selon la loi statistique choisie.
10. 10. Procédé selon la revendication 9, caractérisé en ce que l'étape f) comprend : f2) appeler la fonction d'estimation (scO) avec certains au moins des jeux de données perturbés (z), et établir la nouvelle pluralité (x[]) de jeux de données à partir d'une règle basée sur la comparaison des valeurs associées aux jeux de données de la sous-pluralité (y[]) et aux jeux de données perturbés (z).
11. 11. Procédé selon la revendication 10, caractérisé en ce que la règle de l'étape f2) comprend la sélection, entre un jeu de données (y[i]) de ladite sous-pluralité et un jeu de données perturbé (z) tiré de ce jeu de données (y[i]), du jeu de données dont la valeur associée est la plus élevée.
12. 12. Procédé selon l'une des revendications 8 à 11, caractérisé en ce que l'étape f) est répétée plusieurs fois pour certains au moins des jeux de données de ladite sous pluralité (y[]).
13. 13. Procédé selon l'une des revendications 8 à 12, caractérisé en ce que la règle de 20 l'étape e) comprend la sélection des jeux de données (y[]) de valeur associée la plus élevée.
14. 14. Procédé selon l'une des revendications 8 à 13, caractérisé en ce que le critère de l'étape a) est relatif à la présence d'un marquage ou d'un traçage dans le jeu de données.