[go: up one dir, main page]

EP2318961A1 - Outil de vérification informatique - Google Patents

Outil de vérification informatique

Info

Publication number
EP2318961A1
EP2318961A1 EP09806494A EP09806494A EP2318961A1 EP 2318961 A1 EP2318961 A1 EP 2318961A1 EP 09806494 A EP09806494 A EP 09806494A EP 09806494 A EP09806494 A EP 09806494A EP 2318961 A1 EP2318961 A1 EP 2318961A1
Authority
EP
European Patent Office
Prior art keywords
data
data sets
new
sets
values
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
EP09806494A
Other languages
German (de)
English (en)
Inventor
Frédéric CEROU
Teddy Furon
Arnaud Guyader
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Universite De Rennes 2 - Haute Bretagne
Institut National de Recherche en Informatique et en Automatique INRIA
Original Assignee
Universite De Rennes 2 - Haute Bretagne
Institut National de Recherche en Informatique et en Automatique INRIA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Universite De Rennes 2 - Haute Bretagne, Institut National de Recherche en Informatique et en Automatique INRIA filed Critical Universite De Rennes 2 - Haute Bretagne
Publication of EP2318961A1 publication Critical patent/EP2318961A1/fr
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/10—Protecting distributed programs or content, e.g. vending or licensing of copyrighted material ; Digital rights management [DRM]

Definitions

  • the invention relates to a computer verification tool for the determination of rare events.
  • watermark in English
  • the watermark marking algorithms have experienced a remarkable increase because they are less restrictive for the end user, are complex to work around, and offer good interoperability.
  • Determining the likelihood of false positives is particularly crucial because it is the credibility of the company implementing the tagging algorithm, as users very little value being falsely accused and unable to access to contents that they obtained legally. There is currently no really reliable and inexpensive method that can test these algorithms to determine the probability of false positive because it is very small.
  • the invention improves the situation.
  • the invention proposes a computer verification tool capable of repetitively processing a plurality of data sets, each data set comprising data distributed according to a chosen statistical law.
  • the tool includes an estimator, able to establish for a dataset a value characterizing the reproduction, by this dataset, of a criterion relating to the data it contains, and a mixer, capable of establishing a new dataset, based on an existing dataset, maintaining the distribution according to the chosen statistical law.
  • the tool further comprises a driver, arranged to call the estimator from a plurality of data sets to determine a plurality of values, to call the mixer with at least some of the data sets on the basis of a rule based on said plurality of values, and to repeat the call of the estimator and the mixer each time with a plurality of new sets of data previously established, until a condition which involves an extremum of said plurality of values and / or the number of repetitions.
  • a driver arranged to call the estimator from a plurality of data sets to determine a plurality of values, to call the mixer with at least some of the data sets on the basis of a rule based on said plurality of values, and to repeat the call of the estimator and the mixer each time with a plurality of new sets of data previously established, until a condition which involves an extremum of said plurality of values and / or the number of repetitions.
  • This tool is extremely advantageous because it makes it possible to calculate the probability of a false positive quickly and reliably.
  • the invention also relates to a computer verification method, capable of repetitively processing a plurality of data sets, comprising the following steps,
  • steps d) to g) selectively repeating steps d) to g) with each time the new plurality of data sets, until verifying an end-of-iteration condition, which involves an extremum of the value and / or the number of iterations.
  • FIG. 1 represents a schematic view of a tool according to the invention
  • FIG. 2 represents a general operating diagram of the tool of FIG. 1;
  • FIGS 3 to 6 show examples of particular implementations of functions of the operations of Figure 2 and;
  • FIG. 7 represents another embodiment of an operation of FIG. 2.
  • the algorithm is installed on a digital device, for example a camcorder.
  • the camcorder is arranged to call the algorithm whenever a content to which it accesses is to be copied / recorded.
  • the algorithm analyzes the data flow of the content and determines whether it is protected or not. If the content is protected, the camcorder blocks any recording of that content.
  • Filigree marking algorithms must be as reliable as possible. For this, manufacturers meet to define standards to qualify the reliability of these algorithms.
  • the problem is therefore the ability to determine the probability of rare events (the presence of a false positive) with a reasonable cost.
  • Another method is to implement the Monte Carlo method. However, this method is not applicable in this case because it has a prohibitive calculation cost in view of the probabilities sought.
  • FIG. 1 represents a schematic view of a tool 2 according to the invention.
  • the tool 2 comprises a memory 4, a driver 6, an estimator 8 and a mixer 10.
  • the tool 2 is a computer.
  • the invention applies to any set of tools or devices suitable for implementing the elements of the tool 2, such as a specialized chip (for example of the FPGA type), a generic or specialized printed circuit (for example: example ASIC type), an integrated system chip (for example SOC type) or other.
  • a specialized chip for example of the FPGA type
  • a generic or specialized printed circuit for example: example ASIC type
  • an integrated system chip for example SOC type
  • the memory 4 can be made in any manner known to those skilled in the art, for example in the form of a hard disk, a CD type optical memory. or DVD or other, and is not necessarily physically assembled with the other elements of the tool 2.
  • the memory 4 can be accessed by network, or by any other means known to those skilled in the art.
  • estimator 8 and the mixer 10 described herein are software elements that are physically stored on the memory 4 and which are called and implemented by the driver 8. As such, these elements can be parameterized and or updated as needed.
  • these elements could be functions engraved in a chip forming the tool 2, or have physical and / or logical locks to prevent their modification.
  • Tool 2 works by applying an algorithm qualified as a multi-level Monte-Carlo method. This algorithm is based on the general principle of:
  • Tool 2 operates by dividing a main problem (finding extremely rare events reliably and in a short time) into a multitude of simpler but interrelated problems (finding less rare events, and sorting out those among them). more favorable), as explained by the following formula:
  • dynamics we mean the fact that these elements are trajectories that evolve continuously in time according to an intrinsic model of evolution given by the physical nature of the problem studied.
  • the trajectories are simulated and repetitively selected to choose those offering the best score, that is to say the sequences reaching a maximum state over the period of observation.
  • the replacement step is to replace the lower score items with the minimum of the top score items.
  • This article is mainly a mathematical demonstration of the feasibility and reliability of the adaptive multilevel Monte Carlo method in the restricted framework where the elements have a dynamic set by the nature of the problem studied.
  • the replacement stage with new elements which, on the one hand respect the particular statistical characteristics, and which on the other hand form points of favorable start to find other rare events conditioned by high score events, is particularly complex to implement.
  • FIG. 2 represents a schematic view of the operation of the tool 2.
  • the tool starts from an initialization operation 30.
  • it performs a loop which comprises a selection operation 40 , a mixing operation 50, and which ends with a loop end condition 52.
  • an operation 60 returns the rare event probability that has just been calculated.
  • the rare event sought is defined as the fact that an element distributed according to a distribution law imposed by the studied problem has a score greater than a certain threshold.
  • FIG. 3 represents an exemplary implementation of the operation 30 of FIG. 2.
  • This operation has for function the initialization of the elements which will be used for the determination of probability of rare event, as well as the initialization of the first adaptive level.
  • a counter i is initialized to 1.
  • a loop then begins, which comprises the repetition of an element generation operation 310, and a score calculating operation 320 of the element generated in the operation. 310.
  • An end of loop condition 330 determines whether the counter ia reaches the number of elements n that it is desired to simulate simultaneously or not. When that is not the case, the counter i is incremented at 340 and the loop resumes.
  • a function gen () receives as argument a statistical law px to generate an element x [i].
  • the element x [i] which has just been generated is transmitted as an argument to a function sc () which determines the score of this element. This score is stored in a dx [i] element.
  • an element x [i] is a pointer to a digital content or a sub-part of a digital content such as a rectangular selection of a still image, a portion of a soundtrack between two given moments, an image extracted from a video film.
  • the function gen () of the operation 310 randomly draws digital content of this type from among a large set of contents made available to the invention, as well as a randomly selected portion of this content.
  • the function sc () of the operation 320 is a likelihood measure because the "digital content indicated by the pointer x [i] contains the desired watermark.
  • an element x [i] is a binary word of several bits identifying users of a content sales service.
  • the function gen () is the algorithm used by this service to create and assign these identifiers. In this embodiment, the function gen () ensures that a given identifier is assigned to only one user of the service.
  • the sc () function is a measure of the likelihood that the identifier x [i] was used to create an illegally re-distributed copy on a data exchange network.
  • x [] is a table which receives the successive elements used to determine / generate an element which respects the statistical law px and which is a rare event compared to the law of measurement which represents the function sc ( ).
  • dx [] is an array that stores all the scores of elements of x [] in a given simulation iteration.
  • the function max () receives as argument the current score table dx [] and a selection parameter k, and returns the k-th highest score in the array dx [].
  • the parameter k is the number of elements that are kept for the next iteration, the n-k other elements being removed.
  • the max () function can be implemented in various ways.
  • An effective example of implementation is to sort the array dx [] in order of decreasing values, and to retrieve the value of the kth element.
  • the initialization operation 30 ends at 370.
  • FIG. 4 represents an exemplary implementation of the operation 40 of FIG. 2.
  • This operation carries out the first part of each iteration, that is to say the selection of the best elements which will serve as a basis for the mixing of the operation 50.
  • the operation 40 therefore starts from an operation 400 in which a counter i and a counter m are initialized to 1. Then, in an operation 410, a test determines whether the element x [i] has a corresponding score dx [i ] greater than the threshold of the current level S [N].
  • this element is copied into an array y [] as element y [t].
  • the score dx [i] of this element is copied into an array dy [] as element dy [t].
  • the counter t is incremented.
  • a test 450 determines whether all the elements x [i] have been traveled. When this is not the case, the counter i is incremented to 460. Otherwise, the operation ends in 470. It should be noted that, by defining the threshold S [N] as the kth highest score of dx [], the array y [] contains exactly k elements. These k elements will serve as a basis in the operation 50 mixing and convergence of the algorithm.
  • FIG. 5 represents an exemplary implementation of operation 50 of FIG. 2.
  • the operation 50 is a loop which starts from the selected elements of the array y [], and which will mix or disturb each of its elements a number of times of the order of n / k. This mixture aims to "move" the elements so as to converge to a rarer element.
  • part of this operation ensures that the score of the "mixed" elements progresses, and we keep only the mixed elements that have a favorable score. Otherwise, they are replaced by the corresponding undisturbed element.
  • the operation 50 here comprises two main loops:
  • a second loop which is internal to the first loop, to mix n / k times each element of y [i], and to keep the best mixed elements.
  • the operation 50 therefore starts in 500 by setting the counter i to 1. It is followed in 502 by setting the counter j to 1.
  • the second loop then begins with a first perturbation of the element y [i] at 510.
  • This perturbation is carried out by means of a function mel () which receives y [i] as argument and calls the mixer 10 with this argument as well. only with a parameter ⁇ controlling the strength of the disturbance.
  • the mixer 10 returns a new element z, which is a random perturbation of the element y [i], which nevertheless retains the same statistical law px that the x [i].
  • the element z is, in the space of possibilities, in a neighborhood of the element y [i].
  • the size of this neighborhood is a function of the strength of the disturbance, and can therefore be controlled with the parameter ⁇ .
  • the mixer can be a Gaussian noise generator of intensity given by the parameter ⁇ to ensure sufficient displacement to explore the space of possibilities, but not excessive to remain useful.
  • this Gaussian noise is added to the element y [i], the sum being then normalized to find a Gaussian law with the same variance as the elements x [i].
  • the mixer modifies the digital content in a random but controlled manner.
  • the mixer may be one of the processes described in the scientific article "Stochastic Image Warping for Improved Watermark Desynchronization" by Angela D'Angelo, Mauro Barni, and Neri Merhav, published in EURASIP Journal on Information Security, Volume 2008 (2008), Article ID 345184, doi: l 0.1155 / 2008/345184.
  • the mixer randomly modifies the selection of the content: for example, on a soundtrack, the passage selected by the new pointer z is shifted by ⁇ microseconds, randomly to the past or the future with respect to the passage selected by yfi].
  • the score value of the element z, sc (z), is calculated and compared with the threshold of the current level S [N] in an operation 520. If sc (z) is greater than S [N], then the mixed element is more efficient than the original element y [i], that is to say rarer.
  • the counter j is incremented at 552, and the second loop resumes at 510, with the mixing again of the element y [i] current.
  • the level counter N is incremented, and in 572 the threshold of the current level is defined in the same way as the operation 360.
  • the threshold of the current level S [N] is greater than the stop threshold S, that is to say that the rare event sought has been detected; or if the N level counter is greater than a maximum number of iterations.
  • the second condition prevents the algorithm from looping indefinitely in case of non-convergence due to incorrect parameterization. To date, the Applicant has nevertheless not found any non-convergence of the algorithm implemented by the tool 2.
  • the tool 2 has a very particular adaptation to the problems posed by the rare events related to marking and tracing.
  • the value of the parameter ⁇ controlling the disturbance force during the implementation of the mixer as well as the size of the neighborhood in which the element at the output of the mixer is located with respect to the input element of the mixer is either chosen by the user of the invention, or adaptively fixed for each iteration of the invention;
  • the operation 60 returns the exact probability associated with the iterations concerned, which is therefore an estimator of the probability sought.
  • Operation 60 thus starts at 600 by the initialization of a counter 1, and continues at 610 by the initialization of another counter i.
  • the principle is to traverse the x [i] established at the last iteration to determine the number of them which is greater than the threshold S which is one of the two iteration stop conditions.
  • counter 1 is incremented to 630, and in 640 we test if all x [i] have been traversed. If this is not the case, then the counter i is incremented to 650 and the operation 620 repeated with the next element x [i].
  • FIG. 7 shows another embodiment of operation 50.
  • k does not divide n, and operation 50 is no longer performed by nesting two loops, but follows the same reasoning. mixing of y [i] with selection of the best elements.
  • the operation starts in 701 pa * generating a table of permutation of the integers between 1 and k.
  • This array is the result of a function Permut () which receives the integer k as input, and randomly generates an array of which each element has an integer between 1 and k, each element being present only once in Perm [] .
  • the loop starts with the initialization of a counter 1 to 1 at 702, and continues at 703 with the filling of the element Ind [l] with the value of Perm [mod (l, k)], where mod (l, k) is the modulo function, which returns the remainder of the division of 1 by k.
  • a loop is then started to mix y [i] and select the best elements, with in 708, the index i which receives the value of Ind [j].
  • the operations 710, 720, 730, 732, 740 and 742 are performed identically to the operations 510, 520, 530, 532, 540 and 542, except that the index j replaces the index j + (il) n / k because of the new way of mixing.
  • This loop is conditioned by a test 760 on j to see if there are elements to mix. In this case, the counter j is incremented at 762 and the loop resumes at 707.
  • operation 50 ends with operations 770, 772 and 780 identical to operations 570, 572 and 580.
  • This implementation is particularly interesting because it is no longer necessary for k to divide n, and to maintain the same state of mind as the operation 50 of FIG. 5, as the [i] are replicated on average n / k times using operations 701 to 707.
  • the invention provides a method for setting the value of the parameter ⁇ automatically. Too large a value results in many z elements being rejected during operation 520 (or 720).
  • the invention then passes too often by the operations 540 and 542 (respectively 740 and 742) at the expense of the operations 530 and 532 (respectively 730 and 732).
  • a counter calculates how many times the invention has passed through 540 (respectively 740) during the operation 50. At the end of the operation 50, if this counter is greater than a certain fraction of n (for example 0.7 * n), then the operation 50 is canceled because this is interpreted as an indication that the parameter ⁇ is too strong.
  • the parameter N is then not incremented, the tables x [] and dxQ as well as all the counters of the operation 50 are reset.
  • the parameter ⁇ is decreased by a chosen percentage, for example 10%.
  • Operation 50 begins again with this new value of ⁇ . This is done until the counter is less than the fraction of n mentioned above, thus ensuring that the disturbances are realized, ie operations 530 and 532 (respectively 730 and 732) a comfortable number of times .
  • the probabilities sought in the context of tracing problems are of the order of 10 ⁇ -12.
  • the intermediate thresholds stored in the table S [] can be used. They give an estimate of the curve that associates a threshold with a probability of a rare event, giving approximate points on this curve: threshold S [i] for a probability (k / n) ⁇ i.
  • the thresholds must be set in such a way that the probability of a false positive (detecting a marking when there is none, or accusing an innocent person) is less than a given given in the specifications.
  • the table S [] makes it possible to find a first approximation of the threshold sought.
  • the threshold S defining the rare event is deliberately defined with a very important value, so that a maximum number of iterations are performed, which gives a maximum of data.
  • Such a device can operate by returning a scalar value the magnitude of which qualifies the presence of presence of marking or tracing.
  • Other devices may return a binary value indicating the suspected presence of marking or tracing.
  • Other devices will operate with other types of values.

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Multimedia (AREA)
  • Technology Law (AREA)
  • Computer Hardware Design (AREA)
  • Computer Security & Cryptography (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Complex Calculations (AREA)

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

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 cnxcial 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. II 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.
À cet effet, l'invention propose un outil de vérification informatique, 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 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 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 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,
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, 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,
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.
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 figure 1 ;
les figures 3 à 6 représentent des exemples de mises en œuvre 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 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 ou de sa description, telle qu'elle apparaît dans les dossiers officiels. Pour le reste, il réserve intégralement ses droits. 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 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.
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 ê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 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 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. 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 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 œuvre 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 œuvre 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 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 œuvre 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(AN|AN-I)*P(AN-1|AN.2)*... * P(A2|A1)*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 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 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 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 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 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 à mettre en œuvre.
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 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 œuvre.
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 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é 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 œuvre représentés sur les figures 3 à 6.
La figure 3 représente un exemple de mise en œuvre de l'opération 30 de la figure 2.
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 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 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 sc().
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 œuvre 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=I) 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 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 œuvre de diverses manières. Un exemple efficace de mise en œuvre est de trier le tableau dx[] par ordre de valeurs décroissantes, et de récupérer la valeur du k-ième élément.
D'autres mises en œuvre 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.
La figure 4 représente un exemple de mise en œuvre 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 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é.
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. 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 œuvre 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 n/k. 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 œuvre 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 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 μ.
Un exemple de cette perturbation peut aisément être donné avec une population de base 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 μ 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 même variance que les élément x[i] .
Pour d'autres lois statistiques, d'autres mises en œuvre 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 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 Warpingfor Improved Watermark Desynchronization », de Angela D'Angelo, Mauro Barni, et Neri Merhav, parue dans la revue EURASIP Journal on Information Security, Volume 2008 (2008), Article ID 345184, doi:l 0.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 bande sonore, le passage sélectionné par le nouveau pointeur z est décalé de μ microsecondes, aléatoirement vers le passé ou vers le futur par rapport au passage sélectionné par yfi].
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-l)*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-l)*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émenté 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. 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 œuvre 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 splittingfor rare event analysis", les événements étudiés ne sont 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 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 œuvre 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 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 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. En outre, la valeur du paramètre μ 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 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 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 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 = l*kΛ(N-l)/nAN. En effet, comme on l'a vu avec la formule de la méthode de Monte Carlo multi-niveaux, la probabilité Res associée au (N- l)-ième niveau est le produit des probabilités conditionnelles des niveaux précédents, soit (k/n)A(N-l), par la probabilité conditionnelle duN-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 plus en plus rares par rapport à la fonction de mesure sc(), chaque événement respectant la loi statistique px de base. 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 pa* 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, 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 é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-l)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 à 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 œuvre 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 μ, 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 μ 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 μ é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 dxQ 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=IOO. 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 10Λ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 10A6 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 œuvre 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.

Claims

Revendications
1. Outil de vérification informatique, propre à traiter répétitivement une pluralité de jeux de données (x[])5 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])5 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])5 en fonction d'une règle basée sur la pluralité de valeurs associée à ces jeux.
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. 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. Outil selon la revendication 3, caractérisé en ce que ledit mélangeur (10) est agencé pour appeler répétitivement certains au moins des jeux de données sélectionnés
(yW).
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 remplacer le 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. 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. 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. 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 (gen()) 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 (sc()) à 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[])5
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 fin d'itération, qui fait intervenir un extremum de la valeur (S) et/ou du nombre d'itérations (N).
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. Procédé selon la revendication 9, caractérisé en ce que l'étape f) comprend :
f2) appeler la fonction d'estimation (sc()) 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é (yQ) et aux jeux de données perturbés (z).
11. Procédé selon la revendication 10, caractérisé en ce que la règle de l'étape fl) 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])3 du jeu de données dont la valeur associée est la plus élevée.
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. Procédé selon l'une des revendications 8 à 12, caractérisé en ce que la règle de l'étape e) comprend la sélection des jeux de données (y[]) de valeur associée la plus élevée.
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.
EP09806494A 2008-08-13 2009-07-10 Outil de vérification informatique Ceased EP2318961A1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0804584A FR2935058A1 (fr) 2008-08-13 2008-08-13 Outil de verification informatique
PCT/FR2009/000860 WO2010018313A1 (fr) 2008-08-13 2009-07-10 Outil de vérification informatique

Publications (1)

Publication Number Publication Date
EP2318961A1 true EP2318961A1 (fr) 2011-05-11

Family

ID=40548039

Family Applications (1)

Application Number Title Priority Date Filing Date
EP09806494A Ceased EP2318961A1 (fr) 2008-08-13 2009-07-10 Outil de vérification informatique

Country Status (4)

Country Link
US (1) US8583941B2 (fr)
EP (1) EP2318961A1 (fr)
FR (1) FR2935058A1 (fr)
WO (1) WO2010018313A1 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN110968888A (zh) * 2018-09-30 2020-04-07 北京国双科技有限公司 一种数据处理方法及装置

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2935058A1 (fr) 2008-08-13 2010-02-19 Inst Nat Rech Inf Automat Outil de verification informatique
CN103150454B (zh) * 2013-03-27 2015-06-17 山东大学 基于样本推荐标注的动态机器学习建模方法

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7809138B2 (en) * 1999-03-16 2010-10-05 Intertrust Technologies Corporation Methods and apparatus for persistent control and protection of content
JP4842417B2 (ja) * 1999-12-16 2011-12-21 ソニー株式会社 記録装置
US7403904B2 (en) * 2002-07-19 2008-07-22 International Business Machines Corporation System and method for sequential decision making for customer relationship management
US8055910B2 (en) * 2003-07-07 2011-11-08 Rovi Solutions Corporation Reprogrammable security for controlling piracy and enabling interactive content
CN1914850B (zh) * 2004-01-29 2010-07-21 索尼株式会社 信息处理设备和方法
JP2006011682A (ja) * 2004-06-24 2006-01-12 Sony Corp 情報記録媒体検証装置、および情報記録媒体検証方法、並びにコンピュータ・プログラム
US8018609B2 (en) * 2005-09-13 2011-09-13 Sony Corporation Information processing device, information recording medium manufacturing device, information recording medium, methods therefore, and computer program
WO2009068822A2 (fr) * 2007-11-16 2009-06-04 France Telecom Procede et dispositif de tri de paquets
FR2935058A1 (fr) 2008-08-13 2010-02-19 Inst Nat Rech Inf Automat Outil de verification informatique

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
None *
See also references of WO2010018313A1 *

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN110968888A (zh) * 2018-09-30 2020-04-07 北京国双科技有限公司 一种数据处理方法及装置
CN110968888B (zh) * 2018-09-30 2022-03-08 北京国双科技有限公司 一种数据处理方法及装置

Also Published As

Publication number Publication date
US8583941B2 (en) 2013-11-12
FR2935058A1 (fr) 2010-02-19
US20120060061A1 (en) 2012-03-08
WO2010018313A1 (fr) 2010-02-18

Similar Documents

Publication Publication Date Title
EP1570648B1 (fr) Méthode de sécurisation des mises à jour de logiciels
EP1483673B1 (fr) Methode de stockage de blocs de donnees dans une memoire
EP1977365B1 (fr) Procede de gestion de documents electroniques
WO2010018313A1 (fr) Outil de vérification informatique
EP1449067A2 (fr) Securisation d'un generateur pseudo-aleatoire
EP3857810B1 (fr) Procédé cryptographique de comparaison sécurisée de deux données secrètes x et y
FR3110268A1 (fr) Procédés d’utilisation sécurisée d’un premier réseau de neurones sur une donnée d’entrée, et d’apprentissage de paramètres d’un deuxième réseau de neurones
EP1034476B1 (fr) Procede de verification du fonctionnement d'un systeme
WO2019122241A1 (fr) Procédé de construction automatique de scénarios d'attaques informatiques, produit programme d'ordinateur et système de construction associés
EP2153575A2 (fr) Obtention de valeurs dérivées dépendant d'une valeur maîtresse secrète
WO2017060495A1 (fr) Procédé et système de sauvegarde répartie dynamique
WO2009095616A1 (fr) Procede d'identification d'un document multimedia dans une base de reference, programme d'ordinateur, et dispositif d'identification correspondants
EP2274869A2 (fr) Protection en boite-blanche d'algorithmes cryptographiques comprenant le calcul d'une forme quadratique
EP4443412A1 (fr) Procédé de tatouage numérique d'un réseau de neurones, dispositif et programme d ordinateur correspondant
FR2872373A1 (fr) Procede et dispositif de detection et preuve pour le tatouage d'entites multimedia
WO2025012147A1 (fr) Méthode de tatouage numérique d'une image, méthode d'extraction d'un tatouage numérique et méthode de détection de falsification d'une image tatouée
WO2022229563A1 (fr) Caracterisation d'un utilisateur par association d'un son a un element interactif
FR3053862A1 (fr) Procede de generation des parametres caracterisant un protocole cryptographique
EP4280560A1 (fr) Procédé pour détecter des anomalies de routage entre systèmes autonomes
FR3122753A1 (fr) Procédé d'exécution d'un code binaire par un microprocesseur
EP3614617A1 (fr) Procédé et dispositif de génération de paramètre(s) d'un protocole cryptographique asymétrique à partir d'une blockchain, procédé et appareil de cryptage ou de décryptage et programme d'ordinateur associés
FR3146741A1 (fr) procédé utilisant des distances inter-crêtes en pixels se rapportant à des empreintes digitales
WO2009103872A1 (fr) Moniteur de système de communication par messages amélioré
EP2153359A1 (fr) Procede de classification d'un ensemble de documents electroniques
FR3000332A1 (fr) Procede de reconstruction d'une mesure de reference d'une donnee confidentielle a partir d'une mesure bruitee de cette donnee

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

17P Request for examination filed

Effective date: 20110210

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HR HU IE IS IT LI LT LU LV MC MK MT NL NO PL PT RO SE SI SK SM TR

AX Request for extension of the european patent

Extension state: AL BA RS

DAX Request for extension of the european patent (deleted)
STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: EXAMINATION IS IN PROGRESS

17Q First examination report despatched

Effective date: 20170328

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: EXAMINATION IS IN PROGRESS

APAV Appeal reference deleted

Free format text: ORIGINAL CODE: EPIDOSDREFNE

APAX Date of receipt of notice of appeal deleted

Free format text: ORIGINAL CODE: EPIDOSDNOA2E

APBK Appeal reference recorded

Free format text: ORIGINAL CODE: EPIDOSNREFNE

APBN Date of receipt of notice of appeal recorded

Free format text: ORIGINAL CODE: EPIDOSNNOA2E

APBR Date of receipt of statement of grounds of appeal recorded

Free format text: ORIGINAL CODE: EPIDOSNNOA3E

APAF Appeal reference modified

Free format text: ORIGINAL CODE: EPIDOSCREFNE

P01 Opt-out of the competence of the unified patent court (upc) registered

Effective date: 20230527

REG Reference to a national code

Ref country code: DE

Ref legal event code: R003

APBT Appeal procedure closed

Free format text: ORIGINAL CODE: EPIDOSNNOA9E

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION HAS BEEN REFUSED

18R Application refused

Effective date: 20240704