CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
1
DISPOSITIF ET PROCEDE POUR LA SIGNATURE, LE MARQUAGE ET
L'AUTHENTIFICATION DE PROGRAMMES D'ORDINATEUR.
La présente invention appartient au domaine des dispositifs et
procédés pour prévenir etlou auditer une utilisation d'un programme
d'ordinateur non autorisée par son auteur, son éditeur ou son distributeur.
Relèvent de la prévention les dispositifs et méthodes qui vérifient
que la personne ou l'automate qui cherche à utiliser le programme d'une
certaine manière dispose des droits nécessaires. De nombreux dispositifs et
méthodes de cette catégorie ont été prévus à cet effet. En particulier le
brevet US 6,108,420 divulgue un procédé et un dispositif pour produire une
empreinte cryptographique comportant les données de la licence attribuée à
un utilisateur ou une classe d'utilisateurs puis pour chiffrer cette empreinte
attachée au programme à protéger.
L'inconvénient de ces dispositifs et méthodes est qu'ils supposent
la coopération de l'utilisateur qui ne doit pas communiquer les données de sa
licence à d'autres utilisateurs ni supprimer la partie du programme, aisément
~5 repérable dans un code source car non fonctionnelle, qui comporte ces
données d'identification.
Relèvent de l'audit les dispositifs et méthodes qui modifient le
programme de manière caractéristique de l'exemplaire du programme, de
manière non aisément décelable par l'utilisateur, sans en altérer les
2o fonctionnalités. En particulier, le brevet US 5,559,884 divulgue une
méthode
et un dispositif pour modifier de manière caractéristique de l'exemplaire du
programme l'ordre d'exécution de blocs dudit programme.
L'inconvénient des dispositifs et méthodes de ce type est qu'ils
supposent l'insertion dans les dits blocs d'instructioris d'appel et de retour
qui
25 sont aisément repérables de manière automatique et affectent les
performances du programme à protéger.
La présente invention a pour but de remédier aux inconvénients
de ce deuxième type en divulguant un dispositif et une méthode pour calculer
une signature du logiciel à protéger, caractéristique dudit programme,
3o résistant aux méthodes de repérage sans affecter les performances du
programme à protéger et permettant de marquer le logiciél de manière
secrète, les détenteurs du secret pouvant identifier la marque et la
signature.
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
2
A ces fins, l'invention divulgue un produit/programme d'ordinateur
pour traiter les instructions d'un programme d'ordinateur en code source,
caractérisé en ce qu'il comprend un module pour choisir en fonction de
critères prédéfinis les instructions dudit logiciel auxquelles un programme de
transcodage sera appliqué et un module pour choisir parmi plusieurs la
méthode secrète de transcodage à appliquer aux dites instructions.
Parmi les modes de réalisation préférés, l'invention divulgue
également un produit/programme d'ordinateur du type ci-dessus dont la
méthode secrète de transcodage produit une signature sëmantique du
logiciel.
Selon une variante de l'invention, le produit/programme
d'ordinateur du type ci-dessus comprend un module pour insérer les
instructions transcodées dans le logiciel.
L'invention divulgue également un procédé pour traiter les
~5 instructions d'un logiciel en code source comprenant une étape pour choisir
en fonction de critères prédéfinis les instructions dudit programme auxquelles
un programme de transcodage est appliqué et une étape pour choisir parmi
plusieurs la méthode secrète de transcodage à appliquer aux dites
instructions ainsi qu'un mode de réalisation préféré du procédé où la
2o méthode secrète de transcodage produit par une signature sémantique du
logiciel ainsi qu'une variante de l'invention où le procédé comprend en outre
une étape pour insérer les instructions transcodëes dans le logiciel.
L'invention sera mieux comprise et ses différentes caractéristiques
et avantages ressortiront de la description qui suit et d'exemples de
25 réalisation, et de ses figures annéxées dont
- la figure 1 montre un schéma de principe du dispositif et du
procédé pour choisir la méthode de transcodage et instructions
transcodées dans le programme ;
- la figure 2 montre le schéma du dispositif et du procédé dans
3o une de ses variantes de réalisation ;
- la figure 3 montre le schéma de principe du dispositif et du
procédé pour décoder un programme modifié selon le principe
de la figure 1 ;
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
3
- la figure 4 montre le schéma du dispositif et du procédé pour
décoder un programme modifié selon le dispositif et le procédë
de la figure 2.
L'invention divulgue enfin un produitlprogramme d'ordinateur et
un procédé pour reconnaître la signature du logiciel.
Dans les revendications, la description et les dessins, les
expressions ci-dessous sont utilisées avec la signification indiquée
~ Un procédé de protection/prévention de logiciel, est un ensemble de
techniques qui rendent plus difficiles la copie et l'utilisation frauduleuse
des
logiciels.
~ La compilation d'un programme est sa traduction dans un autre
langage.
~ Un programme informatique est un programme interprétable ou
compilable en un programme interprétable.
~5 ~ Un programme est écrit dans un certain langage de programmation
appelé langage informatique du programme.
~ L'interprétation d'un programme est la traduction de la suite de mots le
composant en une suite d'actions.
~ L'étiquetage d'un document ou d'un code consiste à inclure des
2o marques visibles ou invisibles, séparëes du contenu de l'objet, qui
identifient
par des champs l'objet logiciel (désignation, nom de l'auteur, nom du
destinataire, termes de la licence d'utilisation) et un dernier champ de
signature numérique qui lie complètement l'étiquette au contenu de l'objet et
du même coup garantit l'intégrité de l'objet.
25 ~ Le tatouage consiste à insérer des marques visibles ou invisibles
incrustées dans le corps de l'objet. Ces marques réparties dans le corps de
l'objet sont sinon indécelables du moins indélébiles pour qui ne connaît pas
la clé secrète qui a engendré le motif sous-jacent. Un tatouage est de
l'information cachée dans des données numériques et qui n'en modifient pas
30 le sens.
~ Tatouer un code consiste à le transformer en un code
équivalent sans modifier sa sémantique, en ajoutant de l'information cachée
et récupérable grâce à un secret appelé clef. .
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
4
~ Deux codes logiciels sont sémantiquement équivalents s'ils ont
le même comportement observable, c'est à dire par exemple, si pour toute
entrée possible, les sorties du programme sont les mêmes.
~ Un procédé de signature consiste à joindre à un objet un
segment de données caractéristique (résumé), obtenu à l'aide d'une
méthode secrète.
~ Une technique de lessivage est une tentative d'effacement de
la marque sans changer la sémantique.
~ Un programme, écrit dans un langage particulier (par exemple
o Java), représente une suite d'instructions opérant sur l'état du système
informatique.
~ L'état du système à un instant t est constitué par la valeur des
variables du programme et des variables systèmes (files d'attente de flux
entrée/sortie).
~ 5 ~ On appelle état du système associé, un ensemble de variables
composé des variables existantes ou/et d'autres variables supplémentaires.
~ Une sémantique est un modèle mathématique définissant
l'ensemble des comportements possibles d'un programme à l'exécution à un
certain niveau d'observation.
20 ~ L' « obfuscation » est la transformation d'un programme en un
programme sémantiquement équivalent sous une forme difficile à
comprendre par un informaticien.
~ L' Analyse Statique Sémantique . est la détermination
automatique de propriétés sémantiques des programmes.
25 Pour assurer la sécurité d'un document numérique quelconque
(image, son, texte, programme, etc.), on peut utiliser les techniques
classiques de cryptologie (signatures électroniques, etc). On adjoint au
contenu à sécuriser, les règles de sécurité (par exemple les données
relatives à la licence du logiciel, mais ces règles peuvent être plus
3o personnalisées et plus complexes) relatives au document pour l'utilisateur
autorisé. Ces règles sont écrites dans un autre document numérique (en
général à part, comme par exemple un entête, une étiquette, etc).
Le document est protégé (ou non) par des méthodes de
cryptographie (chiffrement du contenu, par exemple). L'étiquette est protégée
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
par les techniques cryptographiques. Le tout est en général soudé par des
mécanismes cryptographiques (signature électronique, par exemple).
L'inconvénient de ces dispositifs ou méthodes est qu'ils
supposent, dans la chaîne de confiance de distribution, une coopération de
5 tous les acteurs.
Aucun ne doit divulguer le contenu de l'étiquette ou modifier ou
supprimer l'éfiiquette, si celle-ci est à l'extérieur ou à l'intérieur du
programme. Personne ne doit usurper l'identité d'un utilisateur licite.
Les données d'identification d'un programme, même si celles-ci
dépendent de l'heure, du üeu et du contexte peuvent être déviées de leur
contexte propre.
Ces méthodes sont universelles et fonctionnent quelle que soit la
nature du document (texte, signal, image ou programme, ...).
Elles ont un défaut majeur. Elles garantissent un contenu "bit à
bit"
- elles ne font pas la différence entre des modifications infimes ou
profondes.
- elles ne font pas la différence entre une modification qui altère le
contenu sémantique ou esthétique du document original et une modification
2o qui change le "sens" de ce document.
Les techniques cryptographiques traditionnelles se contentent de
broyer tout contenu en une "farine" numérique. La méthode de broyage n'est
pas dépendante de la nature, du format, de la syntaxe, ni de la sémantique
de l'image ou du texte.
La sécurité d'un logiciel dépend de la politique de sécurité mise en
vigueur par le propriétaire du logiciel. II s'agit en général de garantir
- la disponibilité du logiciel : éviter la copie par des pirates (pour
une revente ou une utilisation illicite) ; éviter l'utilisation non autorisée
à partir
d'un support physique original (CDROM) ; ' .
- la confidentialité du logiciel : éviter la compréhension du logiciel
(confidentialité des algorithmes du logiciel source, afin de ne pas divulguer
le
secret du contenu du programme, la connaissance des algorithmes
permettant une compréhension, une réécriture similaire, une modification,
etc.) ;
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
6
- l'intégrité du logiciel : éviter la modification du logiciel, soit en ne
changeant pas le contenu sémantique, mais en changeant seulement la
syntaxe (en modifiant le nom des variables, en rajoutant des instructions
inutiles, etc comme dans les "obfuscateurs" pour les programmes Java par
exemple), soit en changeant son contenu (ajout d'un virus, ajout ou retrait
d'un "patch", modification classique, emprunt d'un morceau, ...) ;
- l'authentification pour garantir l'origine et le contenu du logiciel
(sceau à une certaine date) : pour assurer l'antériorité d'un tatouage par
rapport à un autre, on a recours à une infrastructure de sécurité (Tierce
1o Partie de Confiance à Valeur Ajoutée).
Les méthodes de tatouage logiciel s'inspirant des méthodes de
tatouage d'autres types d'objets (images et sons) sont vouées à l'échec. En
effet, un code informatique, par nature, est complètement différent des
objets audio, vidéo et des images. Pour ces derniers, une légère perte
~5 d'information ne modifie pas le sens : nos capteurs sensoriels sont
imparfaits. Ce n'est pas le cas du code informatique. II ne supporie que les
compressions sans perte d'information. Une modification, aussi infime soit-
elle, peut le rendre non fonctionnel. Seules les modifications qui prennent en
compte la sémantique sont valides, par exemple les opérations
2o d'optimisation de code machine effectuées par les compilateurs ou
l'obfuscation.
L'ïnconvénient des méthodes et dispositifs de tatouage de
logiciel est qu'ils considèrent le code en tant qu'objet syntaxique et
n'exploitent .pas sa sémantique. Pour cette raison, il est facile de retrouver
la
25 marque de tatouage par analyse syntaxique du programme, et d'enlever la
marque par transformation syntaxique.
De plus les méthodes générales de tatouage de logiciel
développées jusqu'à présent induisent des modifications du programme
facilement repérables. L'insertion des instructions de saut et de retour sont
3o par exemple repérables de manière automatique. En ce qui concerne l'ajout
de structures de graphes, ces structures sont également facilement
identifiables dans les codes non complètement compilés. Elles alourdissent
aussi le fonctionnement du programme de façon significative.
Pour la sécurité des logiciels, relèvent de 1â prévention les
35 dispositifs et méthodes qui vérifient que la personne ou l'automate qui
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
7
cherche à utiliser le programme d'une certaine manière dispose des droits
nécessaires. De nombreux dispositifs et méthodes de cette catégorie ont êté
prévus à cet effet. Il s'agit de dispositifs de protection de logiciels (leur
utilisation dépend généralement d'un dispositif matériel: carte à puce,
"dongle") ou de dissuasion d'utilisation frauduleuse de logiciels (étiquette,
bannière, marque à l'extérieur ou à l'intérieur d'un programme source,
instructions en langage machine dans le programme exécutable pour
identifier un contexte d'utilisation).
Avec l'avancëe des nouvelles technologies et l'accroissement
o du nombre d'utilisateurs d'Internet, la protection de la propriétë
intellectuelle
devient une priorité pour les producteurs et les vendeurs de logiciels. De
nombreux dispositifs et méthodes de protectïon ont été prëvus à cet effet. On
notera la famille des dispositifs qui fonctionnent avec un matériel
spécialisé.
Parmi les méthodes de protection logicielles, on distingue le tatouage de
logiciel et !'obfuscation. Les méthodes de tatouage qui en font partie se
répartissent en deux familles
~ les méthodes dites dynamiques, qui prennenfi en compte (a dimension
temporelle de l'exécution du programme. La marque insérée peut être
obtenue
- en lisant la sortie du programme pour une entrée donnée.
- en lisant le contenu d'une variable pendant l'exécution, pour
une entrée donnée.
- en notant !'ordre d'exécutïon des blocs d'instructions. En
particulier, le brevet 5,559,884 divulgue une méthode et un dispositif pour
modifier de manière caractéristique l'ordre d'exécution de blocs dudit
programme, par insertion d'instructions d'appel et de retour.
~ (es méthodes dites syntaxiques statïques, grâce auxquelles on insère
et on lit la marque sans l'exécution du programme. La marque peut être
obtenue
3o - en étudiant l'ordre des instructions
- en examinant les données utilisées par le programme (texte,
photos, sons)
Un descriptif de l'ensemble des méthodes existantes est
présenté dans l'article de Coalberg et Thomborson, Softwarè Watermarking
Models and Dynamic Embeddinas (1998).
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
8
L'invention appartient à une troisième catégorie, celle des
dispositifs et méthodes statiques sémantiques.
Dans cette catégorie, on peut trouver des signatures qui auront
un sens arbitraire mais qui resteront néanmoins cachées car le logiciel
comporte lui-même une part importante de texte non structuré.
Mais dans son mode de réalisation préféré, le dispositif
proposé s'applique de manière spécifüque aux programmes logiciels qui ont
une sémantique donnée, c'est à dire les programmes écrits dans un langage
de programmation (« programming languages ») : il est particulièrement
o applicable aux programmes interprétés (Java, PostScript, etc) car ces
programmes, une fois écrits en langages machines, sont facilement
déchiffrables par de la rétro-ingénierie dans leur forme originelle,
compréhensible par un informaticien. Mais il est bien entendu que ce
dispositif est aussi applicable aux programmes écrits en langages
~5 compilables (C, C++, Basic, Ada, Pascal, VHDL, Estérel, ...) pour
authentifier
et contrôler l'origine, le contenu ou la destination.
Le dispositif dans son mode de réalisation préféré dépend de la
sémantique du langage. Ainsi, les tatoueurs Java, VHDL, etc sont différents.
Ils peuvent avoir des parties similaires (pour la sëmantique de leurs
20 opérations arithmétiques) mais parfois spécifiques (Les pointeurs en
langage
C). Le dispositif est applicable aux langages à balises pour les parties qui
contiennent des programmes (« des scripts »). Pour XML, les autres parties
relèvent des procédés de tatouages d'images (modifications imperceptibles
de ta présentation sur écran ou papier). Le dispositif est également
25 applicable aux parties qui comportent des opérations (programmes
« macros » pour « centrer », « justifier », etc).
Dans son mode de réalisation préféré, l'invention s'appuie sur
les principes de l'analyse sémantique.
L'analyse sémantique a été appliquée avec succès à la
3o certification des programmes à exigence draconienne de fiabilité.
(référence
1 : Abstract Interpretation : a unified lattice modal for static analysis of
programs by construction or approximations of fixpoints, P.Cousot & R.
Cousot January 17-19, 1977 référence 2 : P.Lacari, J.N. Montfort, Le Vinh
Quy Ribal, A. Deutsch, and F. Gouthin. The software reliability verification
35 process : The Ariane 5 example. In Proceedings DA/A 98 - Data Systems in
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
9
Aerospace, Athènes, Grèce. ESA Publications, SP-422,25-28 mai 1998).
Pour prouver qu'un programme s'exécute sans défaillance en contexte
opérationnel, il faut en théorie étudier toutes les exécutions possibles dudit
programme. Les travaux ci-dessus, ont montré que l'on pouvait élargir à
l'ensemble de toutes les exécutions possibles la preuve du bon
fonctionnement. On considère qu'un programme est construit à partir d'un
ensemble de naeuds liés entre eux. Les instructions relient les naeuds entre
eux et provoquent ainsi des transitions d'états matérialisées par un
changement d'une ou plusieurs variables ou/et un changement de noeud.
Lorsque l'on fait une analyse sémantique d'un programme par
interprétation abstraite, on calcule par itération [cf. « Abstract
Interpretation
A unified lattice model for static analysis of programs by construction or
approximation of fixpoints, P.Cousot & R.Cousot January 17-19, 1977], pour
chaque variable et pour chaque noeud, un sur-ensemble de l'ensemble des
~5 valeurs que pourra prendre une variable à un noeud donné.
Trouver ces sur-ensembles revient à résoudre une équation de
point-fixe, dont on obtient une approximation par itération. Les exemples
montreront des méthodes d'itération dans des cas précis.
Le problème que l'inventeur se propose de résoudre relève de
20 la même approche : si les instructions ajoutées au programme à protéger
appartiennent à un sous-ensemble des invariants dudit programme, alors les
dites instructions s'exécuteront sans erreur et ne modifieront pas les
fonctionnalités dudit programme. II existe plusieurs sous-ensembles
pertinents. II est judicieux de choisir un sous-ensemble particulièrement
25 représentatif du type de programmes à protéger.
Bien que d'autres solutions puissent être envisagées, il est
actuellement préféré que la sélection des instructions à transcoder soit
effectuée selon des critères prédéfinis incluant la sélection de sous-
ensemble d'invariants du programme tels que définis ci-dessus.
3o Le module (310) de la figure 1 permet d'effectuer cette sélection
des instructions à transcoder à partir de la définition des caractéristiques
des
dites instructions (opérations sur des entiers, opérations sur les flottants,
initialisation de variables, boucle conditionnelle, branchement...) en
application de critères au moins partiellement prédéfinis. Le ~paramétrage du
35 module (310) du compilateur (30) permet alors la sélection automatique des
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
instructions â transcoder. L'intervention de l'opérateur sera également
possible pour sélectionner une partie autonome du programme à signer
sémantiquement. En java par exemple, un programme est assimilé à
plusieurs classes composées de plusieurs méthodes, elles-mêmes pouvant
5 faire appel à des méthodes d'autres classes et d'autres packages. C'est pour
cette raison que dans ce cas particulier nous préférerons signer la plus
petite
entité autonome d'un programme java : la méthode.
Les parties du programme à signer doivent être les parties
innovantes et/ou sensibles du programme. En général elles concernent la
partie algorithmique du programme.
II s'agit ensuite de choisir parmi plusieurs la méthode de
transcodage en application de critères au moins partiellement prédéfinis. Ce
choix dépendra du caractère sensible des informations à protéger. Le
transcodage sera donc plus ou moins complexe, étant entendu qu'il devra
~5 respecter la sémantique des instructions à transcoder, c'est-à-dire
utiliser le
même vocabulaire et la même grammaire. Le module (320) contient les
méthodes de transcodage possibles pour chaque langage. Une méthode de
transcodage peut avoir un degré de sophistication correspondant au niveau
de protection souhaité. Pour un niveau donné de protection, un nombre
2o alloué de paramètres possibles seront attribuables à des utilisateurs ou
des
classes d'utilisateurs.
Dans cette liste, chaque méthode de transcodage comporte un
secret à préserver. En effet, sa connaissance permettra le décodage et donc
l'enlèvement des instructions supplémentaires, ce qui supprimera toute
25 preuve d'une copie éventuelle ultérieure non autorisée.
Une table de transcodage est une application qui, à toute
opération effectuée sur l'état du système, associe une autre opération
effectuée sur l'état du système associé. Créer une sémantique secrète
revient donc à créer une analyse statique correspondante, ce qui consiste à
3o définir les variables associées, et la relation entre, les actions opérant
sur
l'état du système et celles opérant sur les variables associées.
On peut par exemple garder les même variables que celles
utilisées par Je programme. Notre table de transcodage donnera une autre
interprétation des instructions du programme, et affecterâ aux variables
35 associées d'autres valeurs que celles qu'auraient prises les variables
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
11
initiales. On peut également considérer une et une seule variable associée V,
quelles que soient les variables initiales. La suite des instructions du
programme sera alors interprétée en une suite d'actions sur la variable V.
L'invention prend en compte toutes les actions opérant sur l'état
du système d'environnement du programme informatique : une telle action
peut affecter la pile d'exécution, modifier le contenu d'une variable système,
appeler une fonction, ordonner la lecture d'une autre variable, effectuer une
opération logique ou mathématique, créer un objet, envoyer ou recevoir un
flux I/O, lire un élément d'un tableau...
1 o Utiliser une table de transcodage secrète renforce les dispositifs
' de signature et de tatouage. Sans ce secret, il est très difficile de
trouver la
même signature (selon l'argument classique en crypto : on ne peut pas
raisonnablement essayer toutes les combinaisons possibles) de même qu'il
est quasiment impossible de retrouver une marque.
~ 5 La signature sémantique proposée caractérise l'algorithme
développé en tant que tel, et permet de trouver les programmes qui ont une
sémantique équivalente.
La marque de tatouage est obtenue par analyse statique (après
transcodage) du programme, qui constitue la clef de notre secret. II y a peu
2o de bruit ajouté, et la marque est donc plus résistante.
La table de transcodage secrète rend plus difficïle la détection de
la marque.
A ce stade, il est possible de déposer la signature du logiciel (10)
telle que produite en sortie du module (320) chez une Tierce Partie de
25 Confiance (TPC). Elle n'a donc pas à être insérée dans le logiciel (10).
L'authentification du logiciel s'effectuera alors auprès de la TPC par
comparaison de la signature produite avec le logiciel à analyser avec celle
qui a été déposée. Dans ce cas, le logiciel n'est pas protégé contre ia copie
mais les modifications qu'il a éventuellement subies sont détectables.
30 Dans une variante de l'invention, la signature est insérée dans le
logiciel (10) sous forme de marque.
Le module (330) réalise d'une part le transcodage des instructions
classées avec la méthode choisie et d'autre part l'insertion des instructions
transcodées dans le programme à protéger. L'algorithme principal du module
35 (330) a pour but d'optimiser le placement des instructions transcodées.
Elle
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
12
doit être adaptée à la typologie des instructions et des méthodes de
transcodage. Les compilateurs contiennent normalement des outils
d'optimisation de code et de vérification de la propagation des constantes.
L'insertion des instructions transcodées dans le programme à protéger devra
donc respecter un certain nombre de règles minimales de robustesse : il faut
s'assurer que les variables contenant les marques de tatouage aient une
influence sur les sorties du programme. En d'autrés termes, pour éviter la
suppression pure et simple par un optimiseur, il faut s'assurer que le contenu
de la variable sera repris par une instruction du programme initial. II faut
1o également dissimuler les constantes. II faut pour cela éviter les
initialisations
de variable v par une valeur constante IC, suivies par une instruction du type
w=f(v), au début du programme, car il est alors facile pour un optimiseur de
calculer directement w. On pourrait par contre privilégier les boucles : dans
une boucle, il est naturel d'initialiser une variable (souvent à 1 ),et de
~5 l'incrémenter à chaque exécution de boucle. Supposons que dans la boucle,
i prenne des valeurs de a à b. On pourrait insérer l'instruction w=f(i) dans
la
boucle et calculer f de telle sorte que w prenne la valeur de la clef pour une
valeur de i comprise entre a et b.
Une fois les propriétés sémantiques du programme conjugué
2o déterminées, on calcule par la table de transcodage inverse, les
instructions
à ajouter au programme initial. Les instructions ajoutées doivent s'exécuter
sans erreur et ne pas modifier les fonctionnalités dudit programmé. Ces
transformations seront iso-sémantiques : pour toute entrée identique, les
programmes initiaux et tatoués produiront la même sortie. Mais par contre,
25 les environnements internes d'exécution ne seront pas identiques.
La marque est donc un ensemble de propriétés sémantiques du
programme transcodé. Notre dispositif de tatouage consiste donc à calculer
les instructions à ajouter dans le programme initial qui permettront d'obtenir
ces nouvelles propriétés dans l'espace caché.
3o L'insertion des instructions transcodées dans le programme à
protéger devra respecter un certain nombre de règles minimales de
robustesse : il faut s'assurer que les variables et les opérations contenant
les
marques de tatouage donnent l'impression qu'ils aient une influence sur les
sorties du programme. Par exemple, pour éviter la suppression pure et
35 simple par un optimiseur, il faut s'assurer que le contenu de la variable
sera
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
13
repris par une instruction du programme initial.(allocation dynamique de
valeur)
II est important de noter que l'observation des valeurs prises par
les variables lors de l'exécution ne permet pas de retrouver la marque. D'une
part il faut connaître la table secrète pour établir notre programme conjugué.
D'autre part, le calcul de propriétés sémantiques ne pourra se faire dans la
plupart des cas que par analyse statique, et non pas par une exécution pas à
pas.
La figure 2 expose un exemple de réalisation.
o La méthode (310) de la figure 2 sera donc appliquée à chaque
méthode du programme (ou au moins à celles qui ont un contenu
algorithmique que l'on souhaite protéger). La sélection des instructions à
transcoder tient compte de la dynamique d'exécution du code Java
l'allocation des objets s'effectue "sur le tas", c'est-à-dire en fonction du
contexte d'utilisation des ressources des processeurs, de la mémoire et des
entrées/sorties et, le cas échéant, des autres membres du réseau. Les
instructions portant sur les objets ne sont donc pas recommandées pour le
tatouage puisque celui-ci doit être indépendant du contexte.
Le tatouage doit donc porter sur des valeurs scalaires ou des
2o références à des objets qui sont les seuls opérandes à allouer sur la pile
du
programme.
Le critère prédéterminé peut comprendre le choix comme
instructions à transcoder des opérations sur les entiers, les flottants ou les
valeurs booléennes. Pour les programmes standards on choisira les
opérations sur les entiers. Pour les programmes de conception assistée sur
ordinateur, de simulation ou de modelage en trois dimensions où les
opérations sur scalaires flottants dominent, on choisira plutôt ces
opérations.
Le module (310) de la figure 2 est alors uniquement utilisé pour
sélectionner les instructions (110), (130), (150) des méthodes du programme
(10) qui comportent des opérations sur les entiers.
Un transcodage qui respecte la sémantique de l'instruction
consiste alors à effectuer la même opération modulo à un entier quelconque
Nk inférieur à 232. Une alternative consiste à effectuer une opération
différente choisie dans une table de permutation, encore en algèbre
modulaire. Le module (320) a, dans ce cas, pour fonction principale de
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
14
conserver la table des secrets attribués à des classes d'utilisateurs donnés
pour des programmes donnés.
Le module (330) pour calculer et insérer les instructions
transcodées est une suite d'instructions du compilateur (30) du type décrit ci
après.
On veut insérer p marques dans chaque méthode sélectionnée.
Soient p nombres n1, n2, ....,nP et p valeurs de marques ci<n1 ; c2 <n2 ; ....
Cp<np constituant l'ensemble secret.
On répétera la suite des macro-instructions de l'annexe 1 pour
1o chaque méthode à tatouer.
II est bien entendu possible de répéter plusieurs fois le processus
avec des valeurs différentes de marques.
II est également possible d'améliorer la robustesse du tatouage en
utilisant différentes techniques de l'algèbre modulaire.
~5 La technique la plus forte pour lier le tatouage au programme est de
faire interférer les variables de tatouage avec la méthode originale. II faut
pour cela pouvoir utiliser des propriétés de la variable de tatouage qui
soient
transposables en arithmétique signée sur 32 bits. C'est possible lorsque la
clef K est une puissance de 2. En effet, supposons.que K = 2k. Alors on a
2o X = v + a. 2k dans Z
Nous savons, toujours dans Z, que, pour tout j < k
X% 2' = v% 2'
Où x%y désigne l'opération qui renvoie le reste de la division
euclidienne de x par y. On remarque que cette propriëté reste trivialement
25 vraie dans Z/232 qui est le domaine des entiers Java. Nous pouvons donc
utiliser des propriétés arithmétiques du tatouage pour modifier des calculs de
la méthode. Par exemple, supposons que K = 216 et que v = 18. Alors quelle
que soit la valeur de x, on a toujours x% 4 = 2.
Si on a par exemple une constante explicite 1 dans le programme
30 original, on peut la remplacer par x% 4-1. Si maintenant on a rajouté une
dynamique à x, on a une variable qui prend en apparence des valeurs
stochastiques mais dont on utilise un invariant caché. Le programme ainsi
modifié est dégradé de manière irréversible tout en conservant sa
sémantique originale. Un pirate qui chercherait .à éliminér la variable de
35 tatouage x rendrait alors le programme inutilisable. II faut une étude
poussée
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
du comportement de x pour pouvoir retrouver l'information ainsi dissimulée.
Notons que cette technique de dissimulation de constantes peut se faire
simplement de manière automatique et aléatoire.
La méthode générique de la lecture du tatouage est présentée sur
5 la figure 3. Elle suppose la connaissance d'une partie au moins des
paramètres de tatouage. II est ainsi possible d'affecter à plusieurs niveaux
d'une chaîne de distribution de logiciel (acheteur, grossiste, distributeur,
détaillant) des marques qui leur seront propres.
Dans l'exemple de réalisation de la figure 4, la connaissance du
10 ou des nombres secrets Nk permet de retrouver par une exécution pas à pas
du programme dans le compilateur les variables qui comportent une
congruence modulo Nk à un instant donné puis de tracer cette variable
jusqu'à son initiaüsation.
La table des secrets peut être aisément contenue sur une carte à
~5 microprocesseur qui sera connectée à l'ordinateur comportant
l'interpréteur.
L'utilisateur habilité n'a à connaître qu'une clé publique qui activera le
programme de lecture des secrets correspondant à son identification
d'utilisateur. Les clés privées qui définissent la table des secrets n'ont
donc
pas à être divulguées.
2o Deux exemples donnés en annexes 2 et 3 permettent d'illustrer
l'application de l'analyse statique sémantique à l'authentification de la
signature du logiciel avec deux cas simples de calcul des points fixes des
variables cachées.
Ces dispositifs et procédés peuvent être mis en oeuvre sans
difficulté sur des ordinateurs de commerce. En fonction de la complexité du
logiciel et de la signature, les temps d'exécution seront plus ou moins longs,
notamment pour le calcul des variables cachées par la méthode du point fixe.
Pour limiter ces temps de calcul, on appliquera les méthodes d'élargissement
et de rétrécissement connues de l'homme du métier.
3o On peut tatouer autant de fois que l'on veut un logiciel
(superposition de tatouages), contrairement aux tatouages de sons ou
d'images qui subissent une certaine saturation du canal subliminal (selon le
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
16
modèle de perception choisi). On n'altèrera pas le logiciel, on le
surchargera,
les ressources mémoire et temporelles seront affectées.
On peut utiliser pour chacun de ces tatouages des sémantiques
secrètes différentes, si bien que la chaîne de confiance peut avoir des
secrets différents.
Bien entendu, ce dispositif et ce procédé de tatouage peuvent être
combinés avec des dispositifs et procédés de l'art antérieur pour rendre le
programme inutilisable à un utilisateur non autorisé (prévention) pour tracer
la dissémination éventuelle dudit programme par un utilisateur autorisé à des
1o utilisateurs non autorisés (audit). II suffira pour cela de ne pas
communiquer
aux utilisateurs autorisés les clés leur permettant de retrouver le tatouage.
II est également possible d'utiliser le dispositif et le procédé pour
authentifier de manière automatique les codes que l'on va autoriser à
pénétrer sur un réseau ou sur un poste donné. Le tatouage est assimilable à
~5 un certificat d'authentification dont le poste de surveillance du réseau ou
du
poste disposera de la clé de lecture.
L'Annexe 4 présente un glossaire.
L'Annexe 5 présente un mode de réalisation de l'invention avec un
découpage en modules plus fin.
2o L'Annexe 6 et l'Annexe 7 présentent de nouveaux exemples de
réalisations (exemples 3 et 4).
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
17
ANNEXES
ANNEXE 1
1.1 Décomposition de la méthode en 2 blocs A et B de taille
équivalente.
1.2 Pour i variant de 1 à p faire
1.2.a trouver une position aléatoire dans le bloc A
1.2.b faire la liste des variables ayant une valeur
déterminée à ce niveau d'exécution - 2 cas
cas 1 : il n'y en a pas
Créer une variable w initialisée à une valeur x. Insérer
cette initialisation entre le début de la méthode et notre position actuelle.
cas 2 : il y en a au moins une
75 Sélectionner une de ces variables w, soit x sa valeur à
notre position actuelle d'exécution.
1.2.c créer un polynôme P quelconque de degré 2
vérifiant P(x) = c; + k*n; (k entier âléatoire petit)
1.2.d insérer l'instruction d'initialisation suivante : int
2o v;=P(w)
1.2.e trouver une position aléatoire dans le bloc B
1.2.f créer un polynôme Q quelconque de degré 2
vérifiant Q(v;)=v;+1 *n; (1 entier aléatoire petit) '
1.2.g insérer l'instruction v;=Q(v;)
ANNEXE 2
Exemple 1
La méthode tatouée est la méthode principale de la classe
3o Fibonacci, qui calcule la valeur du noème terme de la suite de Fibonacci,
définie par les
un+2 un+1 + un
relations uo = 0
u1 = 1
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
18
Programme initial
public class Fibonacci
public Fibonacci()
public static void main(String[] args)
f
int n=Integer.parselnt(args[0]);
int a=0;
int b=1;
for (int i=1;i<n;i++)
f
2o int c=a+b;
a=b; //a vaut u;
b=c; //b vaut u~+1
..+b);
System.out.println("La valeur de la suite pour n="+n+" est
Choix de tables de correspondances sémantiques
Nous choisissons d'insérer deux valeurs de marque. Pour cela
nous utilisons deux tables de transcodage.
La première permettra d'insérer la valeur cachée 2507, la seconde
3012.
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
19
Nos deux tables associent à chaque opération algébrique sur des
entiers l' opération algébrique identique modulo un nombre N. A tout retour
de valeur entière consécutif à l'appel d'une méthode de type int, on associe
l'initialisation à une valeur V. Pour la première table, N vaut 10000 et V 17.
Pour (a seconde, N vaut 5421 et V vaut 50.
1. Table de transcodage pour 2507
Instruction initiale Instruction transcode
v (entier)= a (entier) + b (entier)v = a + b modulo 10 000
v (entier)= a (entier) * b (entier)v = a * b modulo 10 000
v (entier) est le retour (entier)v = 17
de l'appel une
fonction
l0 2. Table de transcodage pour 3012
Instruction initiale Instruction transcode
v (entier)= a (entier) + b (entier)v = a + b modulo 5421
v (entier)= a (entier) * b (entier)v = a * b modulo 5421
v (entier) est le retour (entier)v = 50
de l'appel une
fonction
Tatouage de la méthode
Le tatouage de notre méthode consiste en l'insertion de deux
variables j et k, prenant respectivement les valeurs 2507 et 3012 dans notre
espace secret.
Le tatouage consiste en deux étapes
- Initialisation de j et k en fonction de n en début de programme. Cette
initialisation nous permet de calculer la valeur de j et k dans notre espace
conjugué, par contre les valeurs de j et k au cours de l'exécution du
2o programme sont inconnues. Cela nous permet d'éviter la transformation de
ces instructions par un optimiseur.
- Ajout d'instructions dans l'algorithme assurant l'invariance de j et k dans
notre espace secret. .
Ces instructions sont des calculs de j et k à l'aide de polynômes
de degré 2.
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
Ancrage de la marque
La marque est ancrée en fin de méthode. En effet, les valeurs de j
et k sont apparemment utilisées pour le calcul du résultat b. Ceci est un
leurre, car la suite des opérations effectuées sur b laissent in fine cette
5 variable invariante.
Programme tatoué
public class Fibonacci
{
publie Fibonacci()
~o {
)
public static void main(String[] args)
{
int n=Integer.parselnt(args[0]);
15 int a=0;
int j=-34*n*n-500*n+833; /l j vaut 2507 dans l'espace conjugué n°1
// (c'est à dire modulo 10000, n->17)
int b=1;
int k=2*n-n*n-9; // k vaut 3012 dans l'espace conjugué n°2
20 (c'est // à dire modulo 5421, n->50)
for (int i=i;i<n;i++)
{
int c=a+b;
a=b; // a vaut u(i)
j=j*5-28; // j vaut toujours 2507 dans l'espace conjugué 1
b=c; // b vaut u(i+1 )
k=k*k+201; // k vaut toujours 3012 dans l'espace conjugué 2
)
b+=k+j;
3o b=b-1-k*j+(1-k)*(1-j); // ancrage de k et j
System.out.println("La valeur de la suite pour n="+n+" est
"+b);
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
21
Analyse de la marque
La marque se retrouve par Analyse Statique, et la méthode
d'approximation du point fixe par itérations.
Le programme conjugué dans l'espace n°1 est le suivant
public static void main(String[] args) ,
int n=17;
int a=0;
int j=(-34*n*n-500*n+833) % 10000;
1 o int b=1;
int k=(2*n-n*n-9) % 10000;
for (int i=1;i<n;i++)
int c=(a+b) % 10000;
a=b;
j=(j*5-28) % 10000;
b=c;
k=(k*k+201 ) % 10000;
o b=(b+k+j) % 10000; .
b=( b-1-k*j+(1-k)*(1-j) ) % 10000;
System.out.println("La valeur de la suite pour n="+n+" est :"+b) ;
}
Transformons tout d'abord le programme en graphe de flux
d'exécution
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
22
Analyse Sémantique Statique : approximation du point iuce
Début
~n=171
tat
(I)
tat
(II)
r:
_
i
~
=.-34
x
raz
-
500
x
n
+
833~10000~!
._._._._._._._._._._._._.J
tat
(III)
~b
~1
i
=
tat
(IV)
ik= 2xn-nz-9~10000~i
tat
(~
l
i
~i
~
.
.
tat
(V1)
!
i (i
< ra)
i sinon
!
s
_._ i._._.~
tat tat
(VII) (X111)
~c =a+b~10000~i
~b=b+k+
j(10000~i
tat tat
(VIII) (XIV)
__ _
~~-bi
ib=_b-1-_kx
j+(1=.k)x(1-
j~10000~i
tat tat
(I~ (XV)
. j =-
j x
5 -
28~10000~!
!.a,
ffichage(b)
i
I L_._._
._._._._._._._._.
tat Fin
(~
~b=~i
tat
(X1)
i k =. 01~10000~~
k z
+ 2
tat
(X11)
i = i 1~10000~ !
+
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
23
ANALYSE STATIQUE SEMANTIQUE
Pour chaque état on étudie l'ensemble des valeurs possibles
prises par les variables, On ne considèrera que les variables
qui ont changé de valeur par rapport à tous les états
précédents possibles.
Etat Variable Valeur initiale
tudie/
Intervalle
I n N=Ql
II a A =O
NI Qs
J =
I b _
B = Q3
k K =O
I i I = QS
II i I =O
III c = f
I a A = !'d
J = f~
I b B =O
II k K =~
III i I = ~
I b B = QS
b B =~
Écriture de l'interdépendance des états
Nr =~17~ Arr =~0~ Jrrr =1j = 34xn2 -500xn+833;nE Nr
Br~, =~1~ Kv =~k=2,xn-nxn-9;nE Nr~ 1~ =~1~U~Ivrr +1~
I~r =Ivr (~ -~;supn
r~Nl
Cvrrr =~~=a+b;aE ~Arr UA~~~bE ~Bn, UB~
A~ = Bn, UB~ Jx = ~,j x5 -28; j E ~Jx U Jrrr ~~ Bxr = wrrr
Kir =~kxk+201;kE ~Kv UKxrr~~ I~rr =Ivr nCinf n;~
rtEN ~~
Bue, _ ~b =b +k + j;b E ~Br~, U Bxr ~~ k E ~Kv U Kxtr ~~ I E ~Jr~r U Jx )~
Bue, =~b=b-1-kx j+~1-k~x~1- j~;bE B~v ~k~ ~Kv UKxrr~~.1 E ~Jrlr UJx
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
24
ANALYSE
STATIQUE
SEMANTIQIE
Pour
chaque
tat,
on
tudie
l'ensemble
des
valeurs
possibles
prises
par
les
variables.
On
ne
considrera
que
les
variables
qui
ont
chang
de
valeur
par
rapport
tous
les
tats
prcdents
possibles.
On
approximera
ces
ensembles
par
des
ntervalles
Numro 0 1 2 3 4
d'itratio
n
N ~ 17 17 17 17
A S 0 0 0 0
J s i~ 2507 2507 2507
B S 1 1 1 1
K O ~ 9736 ' 9736 9736
I s?~ 1 1 i ;2 1 ;2)
I O O 1 1 1 ;2)
C QJ fd 1 1 ;2 (1 ;2)
A S ~ 1 1 1
J Q~ ~ f 2507 2507
B ~ ~ f~ 1 1 ;2
K >~ ~D f 9897 82 ;9930
I
B ~ O gj 2244 2244 ;2405
B P~ S23 s ~ 0 ;9999
Numro 5 6 7 8 35
d'itratio POINT FIXE
n
N 17 17 17 17 17
0 0 0 0 0
J 2507 2507 2507 2507 2507
B 1 1 1 1 1
9736 9736 9736 9736 9736
I (i ;3 (1 ;3) (1 ;4) (1 ;4) (1 ; l 7)
I (1 ;2) (1 ;3) (i ;3) (1 ;4) (1 ;16)
'
(i ;3) (1 ;4) (i ;5) (1 ;7) (0 ;9999)
(1 ;2) (1 ;2) (1 ;3) (1 ;4) (0 ;9999)
J 2507 2507 2507 2507 2507
B (1 ;2) (1 ;3) (1 ;4) (1 ;5) (1 ;9999)
K (2 ;9997) (2 ;9997) (2 ;9997) (2 ;9997) (2 ;9997)
I Ql f QJ ~'Q i 7
B (0 ;9999) (0 ;9999) (0 ;9999) (0 ;9999) (0 ;9999)
B (0 ;9999) (0 ;9999) (0 ;9999) (0 ;9999) (0 ;9999)
On retrouve notre première marque : la variable J garde fioujours la valeur
2507 .
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
Le programme conjugué dans l'espace n°2 est le suivant
5
publïc static void main(String[] args)
int n=50;
int a=0;
10 int j=(-34*n*n-500*n+833) ~ 5421;
ïnt b=1;
int k=(2*n-n*n-9) ~ 5421;
for (int i=1;i<n;i++)
int c=(a+b) ~ 5421;
a=b;
j=(7*5-28) ~ 5421;
b=c;
k=(k*k+201) ~ 5421;
é5 b=(b+k+j) ~ 5421;
b=(b-1-k*j+(1-k)*(1-j)) ~ 5421;
System.out.println("La valeur de la suite pour n="+n+" est .
"+b);
l
Transformons comme précédemment lé programme en graphe de flux
d'exécution
45
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
26
Début
~n = 50i
ötat (I)
i0
État (II)
j =~ -34 x n2-- 500 x n + 833~5421~i
État (III) .
~b= ~li
État (IV)
~~k -- 2x n.-n2.-9~5421~i
État (~
_
ü=.1i
État (V1)
~ i Si(i ~ h) i I I sinon ~
i._._.
État (VII) État (X111)
ic=_a+b~5421~! ib=b+.k+ j~5421~i
. _ . _ . _ . _ ._ . _. J _
État (VIII) État (XIV)
~a=bi ib=b= 1-kx j+(1= k)x(1 _j)~5421~~
État (XV]
j = j x 5 - 28 ~5421~ i ~~affichage(b) i
._._._._._._._: i._._._._._
État (X) Fin
~b-~i
É at (IX) État (X1)
ik =k2.+201~5421~~
État (X11)
_,
_= i + 1~5421~i
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
27
ANALYSE STATIQUE SEMANTIQUE
Pour chaque ëtat, on étudie l'ensemble des valeurs possibles prises par
les variables, On ne considèrera que les variables qui ont changé de
valeur par rapport à tous les états précédents possibles,
Etat Variable Valeur initiale
tudie/
Intervalle
I n N=~
II a A = Q~
III J = O
I b B = P3
k K =O
I i I=O
II i I = ~Zi
III c = Ql
IX a A = f
X J =O
XI b B = Qs
XII k K = 0
XIII i 1 = O
XI b B = Q3
b 8,~, = O
Écriture de l'interdépendance des états
Nr =~50~ Arr =~0~ Jrrr -lJ=-34xn2-SOOxn+833;nE Nr
B~, =~1~ Kv =~k=2Xn-nxn-9;nE Nr~ Ivr =~1~U~Ivrr +1~
I~r =1~ (~ -~;supn
r~ NI
Cvrrr ' ~~ = a + b; a E ~Arr U Arx ~ ~ b E ~Bn, U B~ ~~
Arx = Brv U Bxr Jx = ~j x 5 - 28; j E ~Jx U .l rrr O Bxr = Cvru
Kir = ~k x k + 20I; k E ~Kv U K~1 ~~ I xrrr = I vr n C inf n;-I-~~
ne N~
B~v =~b=b+k+ j;bE ~Br~, UBxr~~kE ~Kv UKxtr~~jE ~Jrrl UJx
Bue, =~b=b-1-kx j+~1-k~x~l- j~;bE Bxr~, ~kE ~Kv UK~r~~ jE ~Jrrr UJx
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
28
ANALYSE STATIQUE
SEMANTIQUE
Pour chaque
tat, on
tudie l'ensemble
des valeurs
possibles
prises par
les variables.
On ne considrera
que les
variables
qui ont
chang de
valeur par
rapport
tous les
tats prcdents
possibles.
On approximera
ces ensembles
par des
intervalles
Numro 0 1 2 3 4
d'itration
N ~ 50 50 50 50
A O 0 0 0 0
J O O 4674 4674 4674
B ~ 1 1 1 1
i5 K ~ O O 3012 3012 3012
I f 1 1 1 ;2 1 ;2)
I O O 1 1 (1 ;2)
C Q3 ~d 1 1 ;2 1 ;2)
A ~ O 1 1 1
J O ~ ~ 1658 0;5420
B Qj O QS 1 1 ;2)
K D O fd 3012 3012
I O ~ ~ O
B s QS Q~ 2266 0 ;4671
B O ~ ~ s~ 0 ;5420)
Numro 5 6 7 8 105
d~itration POINT FIXE
N 50 50 50 50 50
0 0 0 0 0
J 4674 4674 4674 4674 4674
B 1 1 i' i i
3012 3012 3012 3012 3012
I (1 ;3) (1 ;3) (1 ;4) (1 ;4) (1 ;50)
I (i ;2) (1 ;3) (1 ;3) (1 ;4) (i ;49)
C (1 ;3) (1 ;4) (1 ;5) (1 ;7) (0;5421)
(1 ;2) (1 ;2) 1 ;3) (1 ;4) (0;5421)
J (0 ;5420) (0 ;5420) (0 ;5420) (0 ;5420) (0 ;5420)
B (1 ;2) (1 ;3) (1 ;4) (1 ;5) (0 ;5420)
K 3012 3012 3012 3012 3012
I pJ ~1j QS QS 50
B (0 ;5420) (0 ;5420) (0 ;5420) (0 ;5420) (0 ;5420)
B (0 ;5420) (0 ;5420) (0 ;5420) (0 ;5420) (0 ;5420)
Nous retrouvons notre deuxième marque : 3012.
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
29
ANNEXE 3
Exemple 2
La méthode dont on extrait la signature sémantique est une
méthode de tri bulles.
Programme initial
public class Bulle
public statïc voïd main(String[] args)
int[] table=new int[args.length];
for (int i=O;ï<args.length;i++)
table[i]=znteger.parselnt{ares[i]);
print{table);
print(tri(table));
public static void print(int[] table)
System.out.println{"");
for (int i=O;i<table.length;i++)
System.out.print{table[i]+" ");
System.out.println{"");
public static int[] tri(int[] table)
int[] table2=table;
boolean flag=false;
int i=0;
int v=0;
while{!flag)
flag=true;
for (i=O;i<table2.length-1;i++)
if {table2[i]>table2[i+1])
v=table2[ï];
table2[i]=table2[ï+1];
table2[i+1]=v;
flag=false;
return{table2);
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
Choix d'une table de correspondance sémantique
Nous souhaitons obtenir une propriété sémantique après
transcodage. Pour cela nous utilisons une table de transcodage.
Pour les variables de notre espace conjugué, nous ajouterons aux
5 variables de notre espace initial deux nouvelles variables W et W' de type
entier qui sont initialisées avec la valeur 0.
Ensuite nous tâchons de repérer les transpositions effectuées sur
les tableaux du programme, et nous remplacerons ces opérations effectuées
sur le tableau par des opérations sur la variable W. Une analyse statique sur
1o W montrera qu'elle garde une valeur constante égale à 7 dans toutes les
situations.
Table de transcodage
Instruction initiale Instruction transcode
Dbut de programme W vaut 0
W' vaut 0
Squence: Squence:
<suite d'oprations quelconques <suite d'oprations (1)>
(1)>
<suite d'oprations (2)>
<une variable X prend la valeurleau<suite d'oprations (3)>
d'un Tab T
l'indice P> <suite d'oprations (4)>
<suite d'oprations (5)>
<suite d'oprations quelconques(2)
n'afFectant ni X n T ni P> Si W=0 Alors W=1
<une variable Y prend la valeurun - W=W*Valeur Absolue (P -
de T 6~)
indice Q>
W'=min(P,Q)
<suite d'oprations quelconques(3)
n'affectant ni X, ni Y, ni
T, ni P ,ni Q>
<on crit l'indice P de T
la valeur de Y>
<suite d'oprations quelconques(4)
n'affectant ni X ni T ni Q>
<on crit l'indice Q de T
la valeur de X>
<suite d'oprations quelconques
(5)>
T est un tableau, paramtre T est le tableau (5 ; 2 ;
d'entre 4 ; 1 ; 3)
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
31
Signature de la méthode
La signature de la méthode consiste en ('analyse statique
sémantique de la méthode et la détection de propriétés
Analyse du programme
les propriétés se retrouvent par Analyse Statique, et la méthode
d'approximation du point fixe par itérations.
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
32
Le graphe d'exécution du programme conjugué est !e suivant
Dëbut
stable -- [5;2;4;1;3[
État (I)
!~ flag =~ false i
L_._._._._.
État (II)
ii=O; v..=Oi
État (III)
~W --O;W~=0i
i._ ._._._
État (IV)
~ si ( f lag =~ false) ! sinon !
i._._._._._._._.1 i._._.~
État (~
â~=Oi Fin
i._._.
sinon !
État (V1) ~ ''-'-'
~si(i < longueur(table2)) i
i._._._._._._._._._._._
État (VII)
! si(table[i] > table[i +1]) t sinon I
L_._._._._._._._._._.~ i._._.~
État (VIII)
~W --W ~eI i -.(i +1~!
._._._._._
État (IX]
iyy~-~n(i+l;i)~
État (X]
!~ flag =. false i
i._._._._._.
État (X1)
I I ~i=,i+lj
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
33
Écriture de l'interdépendance des états
~ TABLE, _ ~5;2;4;1;3~
FLAGII = ~false~
1O IIII ~~~ WIV ~O
VIII ~~~ W'N
FLAGV = FLAGII n ~ false~
Il
Ivl =~O~U~Imlr ~1J
Ivll =1,,, (~ ~-- ~;longueur(tablell
TABLEVIII = table E (TABLE,I UTABLEvIIr ) tel que ~i E Ivll tel que table(i) ~-
table(i +1)~
Ivlll = ~i E Ivll tel que stable E (TABLEII ~JTABLEVIII ) tel que table(i) ~-
table(i +1)~
W Uf(n'~f : OH~l
rx = x~OH ~xXli-(i+l~;iE IvIrrI
~(WauwN)
W'X = ~min(i +l;i}i E IVIII ~ _
FLAGxI =~f'alse~ .
Itrations 0 1 2
FLAG Q~ false false
I PJ 0 0;1}
I P~ 0 0;1
TABLE Qs (5 ;2 ;4 ;1 ;3) (5 ;2 ;4 ;1 ;3)
I ~ 0 0
W ~ 1 1
W' P~ 0 0
FLAG Qs false false
Itrations 3 4 5 - POINT FIXE
FLAG false false false
I 0;1 ;2 0;1 ;2;3 0;1 ;2;3;4
I 0;1 ;2 0;1 ;2;3 0;1 ;2;3
TABLE (5;2;4;1 ;3) (5;2;4;1 ;3) (5;2;4;1 ;3)
I 0 ;2 0 ;2 0 ;2
W 1 1 ~ 1
W' 0;2 0;2 0;2
FLAG false false false
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
34
Signature
On note la signature de notre méthode de tri bulles
En considérant la table de transcodage secrète, on note que
- « la variable associée W garde une valeur constante égale à
notre variable X' prend les valeurs 0 et 2 ».
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
ANNEXE 4
Glossaire
5 - Un procédé de protection-prévention de logiciel ou matériel est
un ensemble de techniques qui rendent plus difficiles la copie et
l'utilisation
frauduleuse des logiciels ou circuits électroniques.
- Un programme est écrit dans un certain langage de
programmation appelé langage informatique du programme.
10 - L'interprétation d'un programme est la traduction de la suite de
mots le composant en une suite d'actions appelée exécution du programme.
- La compilation d'un programme source, écrit dans un langage de
haut niveau, est sa traduction dans un autre langage ou matérialisation en un
automate, en général langage machine ou circuit électronique.
15 - Un programme informatique logiciel est un programme
interprétable ou compilable en un programme interprétable.
- Un programme informatique matériel est un programme
réalisable par un circuit électronique et spécifié par un langage ~de
description
de circuit.
20 - Un élément d'un programme informatique est une partie non
nécessairement connexe du texte du programme correspondant à une ou
plusieurs instructions, éventuellement composées (comme une commande
de choix conditionnel ou par cas, une boucle, etc.), une déclaration ou
description d'une ou plusieurs structures de données comprenant
25 éventuellement les ou des opérations agissant sur ces structures de
données, une ou plusieurs procédures ou méthodes, un ou plusieurs
modules, etc.
- Une sémantique d'un programme logiciel ou matériel est un
modèle mathématique définissant l'ensemble des comportements possibles
3o d'un programme à l'exécution à un certain niveau d'observation.
- L'analyse statique sémantique est la détermination automatique
de propriétés sémantiques des programmes.
- Deux programmes logiciels sont sémantiquement équivalents
(ou fonctionnellement équivalents) s'ils ont le même ' comportement
35 observable c'est-à-dire qu'ils s'exécutent de manière fonctionnellement
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
36
équivalente, (par exemple, si pour toute entrée possible, les sorties du
programme sont les mêmes).
- Une sémantique abstraite d'un programme logiciel ou matériel
est un modèle mathématique définissant une sur-approximation ou une sous
approximation de l'ensemble des comportements possibles d'un programme
à l'exécution.
- Une sémantique abstraite est secrète si sa spécification pour un
programme logiciel ou matériel nécessite la connaissance d'un secret.
- Une signature est une information caractéristique (étiquette,
vignette ou résumé) associée à un objet (ici, un programme logiciel ou
matériel). Cette information peut dépendre d'une propriété intrinsèque ou
extrinsèque de l'objet. Ces propriétés peuvent authentifier la forme et fond
du
contenu de l'objet (le codage, le format, la syntaxe, l'esthétique, la
sémantique) ou sa traçabilité (l'histoire et/ou le devenir de cet objet).
~ 5 - Une signature secrète est une signature obtenue à l'aide d'une
méthode faisant appel à un secret.
- Une signature sémantique est une . signature spécifiée en
fonction de fa sémantique de l'objet (ici, du programme écrit dans un langage
de programmation, avec une sémantique définie).
20 - Un authentifiant est une preuve secrète de la détention d'une
information ou d'un droit (par exemple désignation de l'objet, nom de
l'auteur,
nom du destinataire, termes de la licence d'utilisation, etc.).
- Une marque est une composante d'un objet qui permet de
l'identifier et qui, dans le contexte de l'invention, permet de retrouver une
25 signature de l'objet.
- L'étiquetage d'un objet ou d'un programme consiste à fabriquer
une étiquette qui est en général séparée du contenu de l'objet ou incrustée
dans l'objet à un endroit facilement repérable.
- Ä la différence, le tatouage consiste à incruster une (ou des)
3o marques) dans le corps de l'objet. Cette marque répartie dans le corps de
l'objet est en général sinon indécelable du moins indélébile. L'objet greffé
avec cette marque s'appelle l'objet tatoué.
- L' obfuscation est la transformation d'un programme en un
programme sémantiquement équivalent sous une forri~e difficile à
35 comprendre par un informaticien mais utilisable par un utilisateur. Ä la
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
37
différence du tatouage, l'obfuscation rend un programme confidentiel (grâce
à la difficulté de le comprendre) mais ne permet pas l'authentification [cf.
Obfuscation techniques for enhancing software security, New Zealand Patent
Application #328057, WO 99/01815, PCT/US98/12017, 9 June 1997].
- Le lessivage de marque est une tentative d'effacement ou de
modification de la marque ou bien une surcharge du programme pour noyer
la marque, sans changer la sémantique du programme.
- Un tatouage de programme est robuste s'il résiste à une
optimisation de compilation, une obfuscation, un étiquetage et à un autre
1o tatouage, toutes ces opérations étant appliquées ultérieurement.
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
38
ANNEXE 5
Description analytigue des modules et arrière-plan théorie~ue
Un procédé A de sémantique abstraite
L'inventeur utilise les principes et techniques de l'analyse statique
sémantique des programmes par interprétation abstraite, cf. [P. Cousot & R.
Cousot, « Abstract Interpretation : A unified lattice model for static
analysis of
programs by construction or approximation of fixpoints », Conférence
internationale « Principles of programming languages, POPL'77 », p. 238
252, ACM Press, Janvier 1977] et [P. Cousot & R. Cousot, « Systematic
design of program analysis frameworks », Conférence internationale
« Principles of programming languages, POPL'77 », p. 269-282, ACM
Press, Janvier 1979].
Le procédé/module A définit une infinité de sémantiques abstraites
secrètes dépendantes
- d'un domaine abstrait D(K) paramétré par une clé secrète K (qui,
2o à une injection près, peut être considérée comme un nombre N = b(K), cette
injection b pouvant elle-même constituer un secret );
- d'une clé secrète K particulière qui définit le domaine abstrait
D(K) utilisé dans la sémantique abstraite secrète SAS.
Cette sémantique abstraite secrète SAS est constituée du
domaine abstrait secret D(N) et des opérations abstraites correspondantes
pour les constructions et primitives de la famille de langages de
programmation considérés, obtenues en utilisant les principes de
l'interprétation abstraite.
Tout domaine abstrait D(K) obtenu par une abstraction, au sens
3o de la théorie de l'interprétation abstraite, cf. [P. Cousot & R. Cousot, «
Abstract Interpretation : A unified lattice model for static analysis of
programs
by construction or approximation of fixpoints », Conférence internationale
« Principles of programming languages, POPL'77 », p. 238-252, ACM
Press, Janvier 1977] et [P. Cousot ~ R. Cousot, « Syster~natic design of
program analysis frameworks », Conférence internationale « Principles of
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
39
programming languages, POPL'77 », p. 269-282, ACM Press, Janvier
1979], paramétré par une clé secrète K est utilisable comme paramètre pour
le module A. Grâce à l'utilisation d'une injection N = b(K), qui peut rester
secrète, tout domaine abstrait D(N), paramétré par un nombre N, est
réutilisable avec des clés quelconques. 1l existe donc une infinité de
domaines abstraits D(K), paramétrés par une clé K, qui sont utilisables.
Cependant, les domaines abstraits publiés dans la littérature scientifique ne
conviennent pas, en ce sens qu'ils ne sont pas paramétrés par une clé K
(méme choisie de manière isomorphe aux entiers ou aux ordinaux).
Fait partie de l'invention, ia transformation d'un domaine abstrait
quelconque utilisable pour l'analyse sémantique statique classique dont la
concrétisation fournit une information sur des valeurs entières (à un codage
injectif près) en un domaine abstrait D(N) paramétré par un entier N
constituant la clé secrète K = N (audit codage près). Le procédé consiste à
~5 abstraire (au sens de l'interprétation abstraite) des opérations concrètes
en
une opération abstraite considérant l'opération concrète réalisée modulo N.
Cette abstraction est ensuite étendue aux éléments de contrôle du
programme selon les principes de l'analyse statique sémantique par
interprétation abstraite, en utilisant éventuellement les techniques
2o d'élargissement et de rétrécissement connues de l'homme de métier.
Des exemples de transformation de tels domaines D en domaines
D(N) sont décrits ci-dessous : '
Pour un programme P écrit en langage algorithmique (avec des
additions, des multiplications, des boucles, des branchemenfis, ...) et dont
25 l'auteur veut sécuriser le contenu algorithmique sensible, on peut définir,
pour le module A, un domaine abstrait D(K) pour les variables entières ou à
virgule fixe ou flottante, voire les réels correspondant à la propagation des
constantes, aux puissances, aux intervalles, aux octogones, aux invariants
d'égalité ou d'inëgalité linéaires, etc. modulo une valeur entière positive N
3o constituant la clé secrète K = N ;
Pour un programme P écrit en langage de programmation avec
des données symboliques (avec des pointeurs, des listes, des tableaux, ...),
et dont l'auteur veut sécuriser le déroulement sensible de manipulation de
variables et de ,tableaux, on peut utiliser un domaine abstrait symbolique
(par
35 exemple un automate ou des domaines d'arbres) paramétré par des entiers
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
(par exemple compteurs de boucles dans l'automate ou une mesure de la
taille des données symboliques) en réutilisant le domaine abstrait précédent
D(N) pour analyser les paramètres entiers, modulo une valeur entière
positive N constituant la clé secrète K, à nouveau à une injection (pouvant
5 être secrète) près.
II existe d'une part une infinité de domaines abstraits Di possibles
et d'autre part une infinité d'instances Di(K) de chaque domaine particulier
en
fonction de la clé secrète K.
Contrairement à la cryptologie classique, si le module A est secret,
o il n'est pas envisageable de le casser par la force brute. En effet il
n'existe
pas d'énumération possible de tous les domaines abstraits paramétrés
utilisables.
Pour un domaine abstrait secret donné Di(N), des clés différentes
conduisent à des sémantiques abstraites secrètes SAS différentes, comme
~5 c'est le cas pour les exemples ci-dessus. Quand le domaine abstrait secret
a
été divulgué ou est public, le secret de la clé doit être géré comme en
cryptographie classique pour limiter les attaques à la force brute (comme
dans le cas de la cryptologie classique basée sur les problèmes NP-complets
ou les mécanismes de chiffrement à clé secrète).
2o La sémantique abstraite secrète SAS doit être invariante pour les
transformations des primitives et constructions de la famille de langages
logiciels ou matériels considérés, qui laissent leur sémantique standard
invariante, comme c'est le cas pour les exemples ci-dessus. Ceci est
important pour éviter les attaques d'obfuscation qui consistent à transformer
25 un programme P en un programme syntaxiquement diffërent mais
sémantiquement équivalent, par exemple, l'expression mathématique (a =
2b) étant changée en (a = b + b).
(Voir Figure 5)
Un Module DA de sémantique abstraite
Parmi les modes préférés de réalisation du procédé ci-dessus,
l'invention divulgue également un dispositif (pouvant être réalisé par un
produit/programme d'ordinateur) incluant
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
41
Un module DA basé sur un domaine abstrait D;(K) paramétré par
une clé secrète K choisie parmi un très grand nombre possible, permettant
d'engendrer un programme implantant la sémantique abstraite secrète SAS
de la famille de langages de programmation logiciel ou matériel considérés ;
(Voir Figure 5A)
Un procédë S de signature
Le procédé/module S utilise une sémantique abstraite secrète
o SAS pour les constructions et primitives de la famille de langages de
programmation considérés, pour faire l'analyse statique sémantique du
programme original P logiciel ou matériel, le résultat de cette analyse
fournissant la signature sémantique secrète SSS du programme P. Pour ce
faire, le module S construit une représentation du système d'équations de
point-fixe dont la solution approchée définit la sémantique abstraite SASP
dudit programme logiciel ou matériel P. Cette sémantique abstraite SASP du
programme logiciel ou matériel P est définie selon les principes de l'analyse
statique par interprétation abstraite de la sémantique concrète du programme
en fonction de la sémantique abstraite secrète SAS pour les constructions et
2o primitives de la famille de langages de programmation considérés. Cette
sémantique abstraite SASP est calculée par élimination, ou par itération avec
accélération de la convergence. La signature sémantique secrète SSS du
programme P est une fonction injective SSS = i(SASP) de la sémantique
abstraite secrète SASP. Cette fonction injective i peut elle-même constituer
un secret.
La signature sémantique secrète SSS d'un programme logiciel ou
matériel P, calculée selon le module S ou par le dispositif DS permet de
vérifier si un programme logiciel ou matériel P' a une signature sémantique
équivalente.
3o Ä ce stade, if est possible de déposer la signature SSS du
programme logiciel ou matériel P telle que produite selon le module S ou en
sortie du dispositif DS chez une Tierce Parue de Confiance (TPC). Elle n'a
donc pas à être insérée dans le programme logiciel ou matériel P.
L'authentification du programme logiciel ou mâtériel P s'éffectuera alors
auprès de la TPC par comparaison de la signature produite SSS' du
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
42
programme logiciel ou matériel P' à analyser avec celle (SSS) qui a été
déposée. Dans ce cas, le programme logiciel ou matériel P n'est pas protégé
contre la copie P', mais deux cas se présentent
SSS' est différent de SSS : les modifications que P a subies sont
détectables, puisque dans le cas de modifications sémantiques (par
exemple, ajout d'un virus, modification d'un algorithme), la signature est
différente;
SSS' est égal à SSS : le programme logiciel ou matériel P' est une
copie de P ou si le programme logiciel ou matériel P a été obfusqué
(manuellement ou automatiquement) pour devenir P', la signature SSS' de P'
sera égale à celle SSS de P, ce qui prouvera, avec une probabilité
extrémement faible d'erreur, que le programme logiciel ou matériel P a été
piraté, ce piratage étant masqué par un maquillage d'édition.
~5 (Voir Figure 6)
Un module DS de signature
Un module DS permettant de calculer ta signature SSS d'un
programme logiciel ou matériel P selon la sémantique abstraite secrète SAS
0 obtenue en utilisant le module précédent DA.
(Voir Figure 6A)
Un procédé M de marquage
25 Pour l'invention, une marque m est un élément de programme
logiciel ou matériel qui peut être insérée dans un programme logiciel ou
matériel par le procédé décrit dans le module B ci-dessous. Soit Pm le
programme logiciel ou mafiériel ie plus simple possible dans lequel la marque
m peut être inséré. Pour toute sémantique abstraite secrète SAS, ce
3o programme Pm a une signature sémantique secrète, calculable par le
module S, dite signature sémantique secrète de ladite marque m et notée
SSS(m).
Une « marque » m est un triplet constitué d'un « emplacement de
marque », d'une « marque d'initialisation » et d'une « marqùe d'induction »,
s5 l'une des deux dernières pouvant éventuellement être vide.
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
43
Soit Pm un programme logiciel ou matériel de la famille de
langages considérée, le plus simple possible, qui déclare si nécessaire
I'« emplacement de marque » 'X', exécute la « marque d'initialisation » 'la',
puis exécute une ou plusieurs voire un nombre infini de fois la « marque
d'induction » 'If'.
Le procédé M de marquage est paramétré par une sémantique
abstraite secrète SAS (par exemple, produite par le module A à partir d'un
domaine abstrait Di(K) en fonction d'une clé secrète K) et une signature
o sémantique secrète SSS ;
En utilisant une bijection f3 qui peut être secrète, le module M
calcule une valeur abstraite 's' du domaine abstrait Di(K) en fonction de la
signature sémantique secrète SSS, selon le codage de la sémantique
abstraite secrète SAS. Cette valeur abstraite 's' est choisie de sorte qu'il
existe de très nombreuses valeurs concrètes 'x' dont l'abstraction selon les
principes de l'interprétation abstraite ou celle du singleton '{x}' est la
valeur
abstraite 's' . Par exemple cette valeur 'x' peut être celle d'une variable
dans
le cas d'une analyse non-relationnelle ou d'un vecteur de variables pour une
analyse relationnelle ou la valeur de tout objet analogue à un vecteur de
variables ;
Le procédé M choisit, selon les principes de l'interprétation
abstraite, l'une quelconque des valeurs concrètes 'a' dont l'abstraction ou
celle du singleton '{a}' est la valeur abstraite s ;
Le procédé M choisit ensuite, selon les principes de l'interprétation
abstraite, une opération concrète 'f' dont l'abstraction fonctionnelle laisse
invariante la valeur abstraite 's' mais pas les valeurs concrètes
correspondantes (c'est-à-dire que si 'x' est une valeur concrète dont
l'abstraction selon les principes de l'interprétation abstraite ou celle du
singleton '{x}' est la valeur abstraite 's' alors 'f(x)' est en général
différent de
'x' tandis que l'abstraction selon les principes de l'interprétation abstraite
de
'f(x)' ou celle du singleton '{f(x)}' est égale à 's') ;
Le procédé M choisit ensuite un « emplacement de marque » 'X'
qui peut être une variable existante du programme qui est inutile ou n'est pas
vivante dans les éléments du programme P à tatouer, une nouvelle variable
auxiliaire, un champ inutile ou supplémentaire d'une structure de données
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
44
allouée dynamiquement, etc. dont les valeurs sont prises en compte dans
l'analyse statique sémantique utilisée pour déterminer la sémantique
abstraite secrète du programme ;
Le procédé M détermine ensuite une « marque d'initialisation » 'la'
qui est constituée d'une ou plusieurs primitives ou constructions de la
famille
de langages considérés s'interprétant comme une affectation de la valeur
concrète 'a' définie ci-dessus à l'emplacement de marque 'X' ;
Le procédé M détermine ensuite une « marque d'induction » 'If'
comprenant une ou plusieurs primitives ou constructions de la famille de
langages considérés s'interprétant comme une affectation de la valeur de
'f(X)' à l'emplacement de marque 'X'. Selon la famille de langages
considérés, ces primitives ou constructions seront des affectations, des
passages de paramètre, des unifications, etc.
La marque m est choisie telle que, selon les principes de
l'interprétation abstraite, !'analyse sémantique statique du programme Pm,
selon la sémantique abstraite secrète et conformément aux directives du
module S, détermine de façon reconnaissable par le détenteur du secret
SAS, la valeur abstraite 's' définie ci-dessus et telle que la signature
sémantique secrète du programme Pm, comme définie ci-dessus, est celle
2o SSS(m) de (a marque.
En utilisant des domaines abstraits ~ qui sont des produits
cartésiens ou des produits réduits de domaines abstraits élémentaires, il est
toujours possible de considérer les marques qui sont des ensembles finis de
marques élémentaires.
(Voir Figure 7)
Un Module DM de marquage
Parmi les modes préférés de réalisation du procédé M ci-dessus,
l'invention divulgue également un dispositif DM (pouvant être réalisé par un
produit/programme d'ordinateur) qui, à partir du programme implantant (a
sémantique abstraite secrète SAS et des données représentant la
sémantique secrète SSS du programme P, calcule le texte de la marque m.
(Voir Figure 7A)
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
Un procédé B de camouflage
Le procédé/module B dé camouflage prend en paramètre le
programme logiciel ou matériel original P, une sélection des éléments du
5 programme P à tatouer et une marque m. Le module B fournit le programme
tatoué PT qui est une fusion du programme original P et de la marque m.
Cette fusion est faite sans altérer la sémantique abstraite secrète de Ia
marque, ni la fonctionnalité. du programme original, ce qui permet de
retrouver la signature sémantique secrète SSS(m) de la marque m à partir de
la signature sémantique secrète SSS(PT) du programme tatoûé PT.
II est important de noter que, dans le mode de réalisation préféré
de l'invention, l'observation des valeurs prises par les variables lors de
l'exécution du programme logiciel ou matériel tatoué PT ne permet pas de
retrouver la marque. D'une part, il faut connaître la sémantique abstraite
15 secrète pour établir le programme tatoué PT. D'autre part, le calcul de
propriétés sémantiques de ce programme logiciel ou matériel tatoué PT ne
pourra se faire, dans les cas de domaines abstraits D(K) non triviaux, que
par analyse sémantique statique, et non pas par une exécution pas à pas.
L'insertion des instructions dans le programme logiciel ou matériel
2o à protéger P devra respecter un certain nombre de règles minimales de
robustesse. Par exemple, pour éviter la suppression pure et simple par un
optimiseur utilisant les techniques d'extraction « slicing », il faut
s'assurer
que les variables et les opérations contenant les marques de tatouage
donnent l'impression qu'ils ont une influence possible sur la sémantique
25 observable ,(par exemple les sorties) du programme. Ladite dépendance
potentielle peut être une simple dépendance syntaxique choisie de sorte que
la démonstration que cette dépendance syntaxique n'entraîne pas une
dépendance sémantique requiert la preuve complexe d'une équivalence
sémantique de programmes logiciels ou matériels. C'est le cas par exemple
3o de l'allocation dynamique de valeur (sémantiquement inutile mais ceci est
indécidable) de certaines valeurs calculées par les opérations contenant les
marques de tatouage.
La marque m créée par le module M, la sélection des éléments à
tatouer dans un programme logiciel ou matériel P telle qu'elle~est choisie par
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
46
le module PS et utilisée par le module B doivent satisfaire aux critères
énoncés ci-après.
Les « marques d'induction » 'If' doivent être incluses dans les
parties du programme logiciel ou matériel contenant des primitives ou
constructions de répétition (itérations, récursivités, etc.).
Les « marques d'initialisation » 'la' sont utilisées pour faire les
initialisations requises par la sémantique de la famille de langages
considérés. De plus, si nécessaire, pour la famille de langages considérée,
d'éventuelles déclarations doivent être ajoutées au programme tatoué PT si
la nature des I'« emplacement de marque » 'X' le nécessite.
Finalement, le module de camouflage B ajoute des primitives ou
constructions au programme tatoué PT rendant actives les valeurs
ëventuellement utilisées dans les « emplacements de marque » 'X'. Une
solution possible consiste à utiliser les valeurs éventuellement utilisées
dans
~5 les « emplacements de marque » dans le calcul de variables actives du
programme matériel ou logiciel tatoué PT, ou encore à affecter les valeurs
des « emplacements de marque » 'X' à des variables dynamiques du
programme tatoué PT, plus généralement en s'assurant que la durée de vie
dynamique des « emplacements de marque » 'X' est celle du programme
2o tatoué PT. Ä nouveau ces transformations du programme P en le programme
tatoué PT doivent être faites sans altérer la sémantique abstraite secrète de
la marque, ni la fonctionnalité du programme original, de façon que, selon les
principes de l'analyse statique par interprétation abstraite, cela permette de
retrouver la signature sémantique secrète SSS(m) de la marque m à partir de
25 la signature sémantique secrète SSS(PT) du programme tatoué PT.
(Voir Figure 8)
Un Module DB de camouflage
3o Parmi les modes préférés de réalisation du procédé B ci-dessus,
l'invention divulgue également un dispositif DB (pouvant être réalisé par un
produit/programme d'ordinateur) qui, à partir du texte du programme logiciel
ou matériel P, de données de sélection des éléments à tatouer dans P et du
texte de la marque m, produit le texte du programme logiciel ôu matériel PT
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
47
dont la sémantique est fonctionnellement équivalente à celle de P et qui
dissimule la marque m.
(Voir Figure 8A)
Un procédé PS de politique de sécurité
Le procédé PS de sélection du domaine abstrait de tatouage et
des éléments à tatouer dans le programme logiciel ou matériel P dépend de
la politique de sécurité à appliquer à ce programme P
Ä l'image des techniques stéganographiques, la marque peut être
répartie dans le programme à des endroits différents et éloignés en
choisissant par exerriple des analyses sémantiques statiques par
interprétation abstraite basées sur des domaines abstraits permettant
d'ignorer les structures de contrôle dans le calcul de la signature sémantique
~5 secrète de sorte que la répartition aléatoire des marques est sans effet
sur
cette analyse ; cette stratégie est par exemple applicable lorsque la marque
sert à authentifier tout un programme P, relativement important en taille.
Une autre politique de sécurité consiste ' à tatouer les parties
innovantes et/ou sensibles du programme P. En général les éléments
2o sélectionnés pour le tatouage concernent la partie algorithmique du
programme (opérations algébriques ou manipulations de variables en
mémoire vive). Selon la famille de langages de programmation considérés et
la méthodologie de programmation utilisée, cette partie algorithmique peut
être
25 - Des éléments significatifs du programme qui sont
sémantiquement autonomes. En JavaT"" par exemple, un programme est
assimilé à plusieurs classes composées de plusieurs méthodes, elles-
mêmes pouvant faire appel à des méthodes d'autres classes et d'autres
packages. Une politique de sécurité pour JavaT"" peut donc consister à
3o tatouer les méthodes qui sont les plus petites entités autonomes
significatives du programme. Un autre choix serait de tatouer des BeansT"".
- Des éléments répartis dans le programme constituant un
ensemble sémantiquement cohérent comme par exemple un type abstrait
algébrique qui serait implémenté par des structures de données et des
35 procédures et fonctions réparties dans tout le programme ;
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
48
Dans ce cas les éléments à tatouer peuvent être sélectionnés
automatiquement sur des critères syntaxiques (procédures, modules, etc.) ou
sémantiques (par une analyse statique de dépendance) ou manuellement
par intervention d'un opérateur.
Plusieurs politiques de sécurité différentes peuvent être mise en
ceuvre sur le même programme P en répétant des tatouages successifs du
même programme logiciel ou matériel original pour des acteurs différents. II
est ainsi possible d'affecter à plusieurs niveaux d'une chaîne de distribution
de matériel ou de logiciel (acheteur, grossiste, distributeur, détaillant) des
1o marques qui leur seront propres. On peut ainsi tatouer autant de fois que
l'on
veut un programme logiciel ou matériel (par superposition de tatouages),
contrairement aux tatouages de sons ou d'images qui subissent une certaine
saturation du canal subliminal (selon le modèle de perception choisi). On
n'altérera pas ie programme logiciel ou matériel, on le surchargera, les
~5 ressources mémoire et temporelles en seront seules affectées.
On peut utiliser pour chacun de ces tatouages des sémantiques
secrètes différentes, si bien que la chaîne de cbnfiance peut avoir des
secrets différents.
Bien entendu, ce dispositif et ce procédé de tatouage peuvent être
2o combinés avec des dispositifs et procédés de l'art antérieur pour rendre le
programme matériel ou logiciel inutilisable à un utilisateur non autorisé
(prévention) pour tracer la dissémination éventuelle dudit programme par un
utilisateur autorisé à des utilisateurs non autorisés (audit). II suffira pour
cela
de ne pas communiquer aux utilisateurs autorisés les clés leur permettant de
25 retrouver le tatouage.
II est également possible d'utiliser le dispositif et le procédé pour
authentifier de manière automatique les programmes logiciels ou matériels
que l'on va autoriser à transiter sur un réseau ou à être hébergés sur un
poste informatique donné. Le tatouage est assimilable à un certificat
3o d'authentificâtion dont le poste de surveillance du réseau ou du poste
informatique disposera de la clé de lecture.
(Voir Figure 9)
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
49
Un Module DPS de politique de sécurité
Parmi les modes préférés de réalisation du procédé PS ci-dessus,
l'invention divulgue également un dispositif DPS (pouvant être réalisé par un
produit/programme d'ordinateur) qui, à partir du texte du programme logiciel
ou matériel P et d'une famille de domaines abstraits D1, ..., Dm, choisit un
domaine abstrait D et sélectionne les éléments du programme P à tatouer.
(Voir Figure 9A)
o Un procédé T de tatouage
Le procédé T de tatouage utilise un module C de chiffrement, qui
implante une fonction bijective pour calculer une signature sémantique
secrète SSS en fonction d'un authentifiant Auth, en utilisant éventuellement
la sémantique abstraite secrète SAS. Ä partir de cette signature sémantique
secrète SSS et de ladite sémantique abstraite secrète SAS, le module de
marquage M décrit ci-dessus produit une marque m. Le module T utilise
encore le module B décrit ci-dessus qui, à partir de ladite marque m, du
programme logiciel ou matériel P et de ia sélection des éléments à tatouer
dans P fournit le programme logiciel ou matériel tatoué PT.
(Voir Figure 10)
Un Module DT de tatouage
Parmi les modes préférés de réalisation du procédé T de tatouage
ci-dessus, l'invention divulgue également un dispositif DT (pouvant être
réalisé par un produit/programme d'ordinateur) pour dissimuler un
authentifiant Auth dans le texte d'un programme original P logiciel ou
matériel grâce à un programme implantant une sémantique abstraite secrète
SAS et des données de sélection des éléments de P à tatouer.
(Voir Figure 10A)
Un procédé G général
Le procédé général G sert à tatouer un programme P. Pour ce
faire, le module PS décrit ci-dessus est utilisé pour choisir automatiquement
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
ou interactivement le domaine abstrait paramétré qui sera ultérieurement
utilisé pour réaliser l'analyse statique par interprétation abstraite par le
module Au d'authentification ainsi que pour sélectionner automatiquement ou
interactivement les éléments du programme logiciel ou matériel à tatouer P.
5 Ensuite, le module A décrit ci-dessus est utilisé pour calculer la
sémantique
abstraite secrète SAS à partir du domaine abstrait paramétré précédemment
sélectionné et d'une clé secrète, en général choisie en interaction avec un
opérateur mais qui peut également l'être automatiquement, voire
aléatoirement. Enfin, le module T décrit ci-dessus utilise le programme P, la
1 o sémantique abstraite secrète SAS, un authentifiant Auth et la sélection
des
éléments à tatouer dans P pour produire le programme logiciel ou matériel
tatoué PT. Des variantes consistent à fixer une fois pour tout le domaine
abstrait qui est utilisé par le module G et à choisir la clé secrète K en
utilisant
une méthode cryptographique standard.
Application à la compilation authentïfiante
La compilation conserve la sémantique concrète des programmes
logiciels ou matériels à un morphisme près. Par conséquent la compilation
conserve également la sémantique abstraite secrète du programme logiciel
ou matériel objet Po, qui est la même que celle du programme source P, à ce
même morphisme près. De ce fait, la compilation d'un programme matériel
ou logiciel tatoué source PT par un compilateur correct ne lessive pas le
tatouage dans le programme matériel ou logiciel objet PTo. Connaissant
l'ordinateur cible, on connaît la sémantique concrète du code objet et donc
celle du programme matériel ou logiciel objet PTo. En adaptant les dispositifs
DA et DS, selon les principes de la théorie de l'interprétation abstraite, à
la
sémantique , concrète du langage maçhine de l'ordinateur ou du système
informatique objet en utilisant ledit morphisme de compilation, on obtient des
dispositifs DAo et DSo conformes aux modules A et S pour la sémantique
3o concrète du code objet et tels que la composition de DA puis DS pour PT
donne la même sémantique secrète SSS (audit morphisme près) que la
composition de DAo et DSo pour PTo. Par conséquent, le dispositif DAu
utilisant le dispositif DSo calcule une représentation de la signature
sémantique secrète SSS du programme PTo, qui est égalément celle du
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
51
programme PT et peut donc être utilisée par le dispositif DAu pour retrouver
l'authentifiant du programme PT.
Une des applications de ce brevet est un module Ca de
compilation, authentifiante compilant un programme tout en y insérant un
tatouage selon les principes du module G. Dans son mode de réalisation
préféré, un compilateur authentifiant Dca intègre le.dispositif DG de la
figure
7 bis dans un compilateur pour un langage informatique matériel ou logiciel
qui est utilisable en option pour tatouer le code objet. Comme expliqué ci
dessus, le dispositif DAu permet de retrouver l'authentifiant du programme
0 objet tatoué.
(Voir Figure 11)
Le Modute DG gënérat
~5 Parmi les modes préférés de réalisation du procédé G de tatouage
ci-dessus, l'invention divulgue également un dispositif DG (pouvant être
réalisé par un produit/programme d'ordinateur) pour dissimuler un
authentifiant Auth dans le texte d'un programme original P logiciel ou
matériel (en fonction du choix un domaine abstrait paramétré par une clé
2o secrète).
(Voir Figure 11A)
Un procédé Au d'authentification
25 Le procédé Au d'authentification prend en paramètres, le
programme logiciel ou matériel marqué PT et la sémantique abstraite secrète
SAS. II calcule l'authentification originale Auth. Ce module A est composé de
deux sous-modules
le module S, décrit ci-dessus, qui à partir du programme logiciel
3o tatoué PT et de la sémantique secrète extrait la signature sémantique
secrète SSS(PT) et par conséquent celle SSS(m) de la marque m cachée
dans PT ;
un module F de déchiffrement et d'extraction, qui est l'inverse du
module C de chiffrement utilisé dans le module T de tatouage, prend en
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
52
paramètre la signature sémantique secrète SSS(PT) pour extraire
l'authentifiant original Auth de P.
Le module de déchiffrement F peut également constituer un
secret, tout comme le module C.
(Voir Figure 12)
Un Module DAu d'authentification
Parmi les modes préférés de réalisation du procédé
1o d'authentification Au ci-dessus, l'invention divulgue également un
dispositif
d'authentification DAu (pouvant être réalisé par un produit/programme
d'ordinateur utilisant le dispositif DS ci-dessus et un dispositif de
déchiffrement DF) pour l'authentification d'un prôgramme tatoué PT en
calculant son authentifiant Auth.
(Voir Figure 12A)
Présentation des figures supplémentaires
5 La figure 5 montre un schéma de principe du procédé A
pour engendrer la sémantique abstraite secrète SAS à partir d'un domaine
abstrait Di(K) dépendant d'une clé secrète K ;
6 La figure 6 montre un schéma de principe du procédé S
pour calculer la signature SSS selon la sémantique secrète SAS d'un
programme logiciel ou matériel P ;
Les figures 5A et 6A montrent le schéma des dispositifs DA et DS
correspondant aux procédés A et S dans une de leurs variantes de
réalisation ;
3o 7 La figure 7 (respectivement 7A) montre le schéma de
principe du procédé M (respectivement du dispositif DM dans une de ses
variantes de réalisation) pour produire une marque connaissant une
sémantique abstraite secrète SAS (résultant par exemple de l'application du
principe du procédé de la figure 1 ) et une signature sémàntique secrète
SSS ;
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
53
8 La figure 8 (respectivement 8A) montre le schéma de
principe du procédé B (respectivement du dispositif DB dans une de ses
variantes dé réalisation) pour tatouer un programme logiciel ou matériel P en
insérant une marque m dans une sélection d'éléments à tatouer dudit P ;
9 La figure 9 (respectivement 9ä) montre le schéma de
principe du procédé PS (respectivement du dispositif DPS dans une de ses
variantes de réalisation) qui, étant donné un programme logiciel ou matériel
P, choisit un domaine abstrait D parmi une famille de domaines abstraits
possibles et sélectionne des éléments de P à tatouer;
10 La figure 10 (respectivement 10A) montre le schéma de
principe du procédé T (respectivement du dispositif DT dans une de ses
variantes de réalisation) pour insérer une marque m caractéristique d'un
authentifiant Auth dans une sélection d'éléments d'un programme logiciel ou
matériel P original en utilisant une sémantique abstraite secrète SAS ;
~ 5 11 La figure 11 (respectivement 11 A) montre le schéma de
principe du procédé T (respectivement du dispositif DT dans une de ses
variantes de réalisation) pour choisir un domaine abstrait paramétré par une
clé, une c¿é secrète particulière et un authentifiant pour tatouer un
programme logiciel ou matériel P par transformation en un programme tatoué
2o fonctionnellement équivalent PT ;
12 La figure 12 (respectivement 12A) montre le schéma de
principe du procédé Au (respectivement du dispositif DAu dans une de ses
variantes de réalisation) pour authentifier un programme tatoué PT.
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
54
ANNEXE 6
Exemple 3
Considérons un programme original P à tatouer très simple par le
dispositif DG de la figure 11 A, qui est le suivant
public class Fibonacci
public Fibonacci()
~ o ()
public static void main(String[] args)
int n=Integer.parselnt(args[0]);
int a=0;
int b=1;
for (int i=1;i<n;i++)
int c=a+b;
2o a=b; //a vaut ui
b=c; //b vaut ui+1
)
System.out.println("La valeur de la suite pour n="+n+"
est : "+b);
A titre d'exemple, le dispositif DPS de la figure 9A sélectionne des
méthodes à tatouer, comme la méthode main.
Un exemple très simple de tatouage de méthodes JavaT"" consiste
3o à utiliser une sémantique collectrice qui est l'ensemble des descendants
des
états d'entrée de la méthode (d'autres alternatives étant la sémantique des
ascendants des états de sortie ou des combinaisons comme l'intersection de
ces sémantiques collectrices).
Dans cet exemple, la sémantique abstraite secrète SAS est
l'abstraction de la sémantique collectrice d'une méthode qui ne retient que
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
les variables locales entières et fait complètement abstraction des autres
variables, du graphe de flot de contrôle, des éléments extérieurs et du
contexte de la méthode. De ce fait l'analyse statique est insensible aux
transformations du programme (par exemple à des fins d'obfuscation ou de
5 brouillage) modifiant le graphe de flot de contrôle et des transformations
par
équivalence des expressions arithmétiques. Par simplicité pour cet exemple
de sémantique abstraite secrète SAS, seules les opérations arithmétiques de
base +, - et * sont considérées (y compris toutes les autres opérations
arithmétiques permettant de réécrire des expressions arithmétiques
comprenant ces opérations de base sous une forme arithmétiquement
équivalente, comme le moins unaire, etc.). La sémantique concrète est
choisie sur l'anneau (Z,+, *) des entiers mathématiques (et non comme des
entiers modulo 232 comme en JavaTM, les équivalences arithmétiques
mentionnées ci-dessus devant tenir compte de ce fait).
15 Dans cet exemple, la sémantique abstraite secrète SAS utilise un
domaine de hauteur finie pour les variables locales entières, ce qui la rend
insensible aux stratégies d'itération chaotique utilisées et évite, toujours
dans
l'optique d'une plus grande simplicité de l'exemple, l'utilisation
d'opérateurs
d'élargissement et de rétrécissement.
2o Dans cet exemple, la clé secrète K est le produit K1 *K2*...*Kn
d'entiers naturels strictement positifs et premiers entre eux. Dans l'exemple
' ~ considéré ci-dessous, n=2, K1=10000 et K2=5421. Le domaine abstrait D(K),
utilisé pour calculer la sémantique abstraite secrète SAS par interprétation
abstraite de la sémantique collectrice, est celui de la propagation des
25 constantes modulo K. D'après le lemme chinois, Z/~ = Z/K1*",*KnZ est
isomorphe à l'anneau produit Z/K1 Z x ~ ~ ~ x ~KnZ~ Étant donné la signature
sémantique secrète SSS du programme tatoué PT dans Z l~ -
~K1 *... *KnZ~ on considère son image (s1, ..., sn) dans Z/K1 Z x ~ ~ ~ x ~KnZ
dont les composantes sont données par la projection canonique sur l'anneau
3o Z/KiZ, i = 1, .~..,n. Dans l'exemple considéré, on suppose que le
dispositif DC
de la figure 6 bis calcule la signature sémantique secrète (2507, 3012) à
partir de l'authentifiant du programme. La sémantique statique secrète est
alors obtenue par n analyses statiques, pour toutes les variables entières
locales à la méthode des domaines abstraits Z/Ki Z, i = 1,...,n; correspondant
35 à la propagation des constantes modulo Ki. Le dispositif DA de la figure 5A
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
56
consiste donc en un programme d'analyses statiques successives par
propagation des constantes modulo (K1, ..., Kn).
Dans cet exemple, le dispositif DM de la figure 7A utilise la
sémantique abstraite secrète SAS et la signature sémantique secrète SSS
définies ci-dessus pour produire une marque m dont le texte est le suivant
int <watermark:10000:2507>;
int <tmp:10000:2507>;
o <watermark:10000:2507>=1;
<tmp:10000:2507>=<watermark:l 0000:2507>+227492;
<tmp:10000:25D7>~<watermark:10000:2507>*<tmp:10004:2507>;
<watermark:l 0000:2507>=<tmp:10000:2507>+155014;
<tmp:10000:2507>=<watermark:10000:2507>*1323;
<tmp:10000:2507>=<tmp:10000:2507>+153;
<tmp:10000:2507>=<tmp:10000:2507>*<watermark:l 0000:2507>;
<watermark:l 0000:2507>=<tmp:10000:2507>+9109;
2o int <watermark:5421:3012>;
int <tmp:5421:3012>;
<watermark:5421:3012> = 1;
<tmp:5421:3012>=<watermark:5421:3012>+-35539;
<tmp:5421:3012>=<watermark:5421:3012>*<tmp:5421:3012>;
<watermark:5421:3012>=<tmp:5421:3012>+11445;
<tmp:5421:3012>=<watermark:5421:3012>*658;
<tmp:5421:3012>=<tmp:5421:3012>+971;
<tmp:5421:3012>=<tmp:5421:3012>*<watermark:5421:3012>;
<watermark:5421:3012>=<tmp:5421:30i 2>+4623;
Dans un cas simplifié où Ki n'est pas trop grand efi pour une
signature sémantique secrète s donnée dans ZlKiZ, le texte~de la marque m
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
57
créé par le dispositif DM de la figure 7A peut consister en une seule marque
d'initialisation qui peut être une affectation
<watermark:Kia>= s';
où s' = s + aKi et la valeur a dans Z n'est pas choisie trop grande
de manière à éviter que s' ne déborde pas hors des 32 bits des entiers Java.
La valeur de la variable <watermark : Ki : s> est toujours constante dans
une analyse statique par propagation des constantes modulo Ki et égale à s.
Cette valeur n'apparaît pas en clair dans la marque et est d'autant plus
difficile à trouver que la clé secrète Ki est inconnue.
1o Une instanciation plus sophistiquée du dispositif DM de la figure
7A permet de choisir cette marque d'initialisation comme étant un polynôme
Q (en la variable <watermark:Kia>) de la forme
ak<watermark:Kia>k + ... + a1 <watermark:Kia> + a
où ak, ..., a1 sont des valeurs aléatoires et la valeur a est donnée
par
a -= s - akvk - ak-1 v k-1 _ , .. - a1 v mod Ki
où la valeur initiale v est choisie quelconque de manière aléatoire.
Dans ce cas, la marque d'initialisation est constituée par les affectations
<watermark:Kia>=v;
<watermark:Kia>= ak<watermark:Kia>k+...+a1 <watermark:Kia>
+ a;
de sorte que ('on a toujours
<watermark:Kia> = s mod Ki
L'utilisation d'une seule marque d'initialisation a l'inconvénient de
laisser la valeur de <watermark: Ki : s> constante et donc aisément
repérable par une analyse statique propageant les constantes. Pour l'éviter,
un dispositif DM plus sophistiqué ajoutera une marque d'induction permettant
de donner une dynamique à la variable de marque <watermark : Ki : s> de
façon qu'elle prenne des valeurs stochastiques dans Z mais reste constante
3o dans Z/KiZ. On utilise pour cela un polynôme Q' qui possède la propriété de
stabilité, c'est-à-dire
Q'(s) ---- s mod Ki
Le polynôme Q' est engendré comme expliqué ci-dessus et la
marque d'induction est constituée par l'instruction
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
58
<watermark:Kia>=
a'k~<watermark:Kia>k'+...+a'1 <watermark:Kia> + a';
ou tout équivalent, par exemple en utilisant le principe de calcul de
Hôrner.
Le dispositif DB de la figure 8A peut placer cette marque
d'induction dans une boucle ou dans un appel récursif de la méthode à
tatouer dans P car son exécution ne modifie pas la valeur de
<watermark: Ki : s> dans l'anneau Z/KiZ choisi pour calculer la sémantique
statique secrète s. Par contre la valeur observée dans le domaine
o d'interprétation des entiers Java sera totalement stochastique.
Dans l'exemple du tatouage du programme P ci-dessus, la
marque définie ci-dessus utilise deux variables locales <watermark : Ki : s>
et <tmp : Ki : s>. La marque d'initialisation est le segment de code initial
constitué par un polynôme Q calculant la valeur initiale de
~5 <watermark: Ki : s>. La marque d'induction est constituée par un polynôme
Q' possédant la propriété de stabilité pour s dans l'anneau Z/KiZ considéré.
On utilise des polynômes du second degré par commodité. Les valeurs des
coefficients du polynôme du second degré assurant l'initialisation sont
aléatoires. Ce polynôme est donné comme suit dans ZJKiZ
2o Q(x) _ (x -1 )(x - s) = x2 + coeffl .x + coeff2.
Un nombre aléatoire de périodes du modulo Ki est ajouté ou
retranché aux coefficients afin de ne pas dévoiler la clef s. La valeur
initiale
de <watermark : Ki : s> est donc
<watermark : Ki : s> = Q ( 1 ) - s dans Z/KiZ.
25 La marque initiale consiste à calculer ce polynôme Q en utilisant le
principe de calcul de H~rner. La marque d'induction est constituée par un
polynôme Q' (également du second degré, là aussi par commodité)
satisfaisant la propriété de stabilité
Q'(s) = s dans ZJKiZ
30 Le polynôme Q' s'écrit
Q'(x)=ax2+bx+c
Les coefficients a et b sont tirés au sort, tandis que c est choisi de
manière à assurer la propriété de stabilité pour la clef secrète comme
expliqué ci-dessus. La marque d'induction est constituée par l'instruction
35 d'affectation
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
59
<watermark:Kia> = Q'(<watermark:Kia>);
où le polynôme est calculé par la méthode de Hôrner.
Le programme tatoué PT correspondant au programme P incluant
la marque m ci-dessus est le suivant
public class FibonacciTatoue
f
public FibonacciTatoue()
f~
public static void main(String[] args)
f
int n=Integer.parselnt(args[0]);
int a=0;
~5 int b=1;
int d=1;
int e=35538;
intf=1;
int g=227493;
2o e=d*e;
d=e+11445;
g=f*9~
f=g+155014;
for (int i=1;i<n;i++)
25 ~ f
int c=a+b;
e=d*658;
f=f* 1323;
a=b; //a vaut ui
3o g=g+153;
e=e+971;
g=g*f~
e=e*d;
b=c; //b vaut ui+1
35 d=e+4623;
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
f=g+9109;
System.out.println("La valeur de la suite pour n="+n+"
est : "+b);
5 }
L'emplacement des marques est aléatoire, dans l'ordre des
marques, la marque d'initialisation étant placée au dëbut du programme et la
1o marque d'induction étant placée de préférence dans une boucle ou dans une
branche d'appel récursif de la méthode.
Dans l'exemple considéré de dispositif DB de la figure 8A, une
transformation supplémentaire du programme est ensuite nécessaire pour
lier le tatouage au programme original (pour résister par exemple au
15 détatouage par « slicing » automatique), comme par exemple)
public class FibonacciTatoue
public FibonacciTatoue()
public static void main(String(] args)
f
int n=Integer.parselnt(args[0]);
int a=0;
int b=1;
int d=1;
int e=35538;
int f=1;
3o int g=227493;
e=d*e;
d=e+11445;
g=f*9~
f=g+155014;
for (int i=1;i<n;i++)
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
61
int c=a+b;
e=d*658;
f=f*1323;
a=b+(155014/f); //a vaut ui
g=g+153;
e=e+971;
g=g*f
e=e*d;
1o b=c+(e/f); //b vaut ui+1
d=e+4623;
b=b-(e/f);
a=a-( 155014/f);
f=g+9109;
System.out.println("La valeur de la suite pour n="+n+"
est : "+b);
)
La suppression des variables d, e, f et g utilisées pour le tatouage
rendrait le programme erroné donc inutilisable.
Dans un exemple plus réaliste, le dispositif DB de la figure 8A doit
s'assurer que la transformation du programme original n'introduit pas
d'erreurs à l'exécution pouvant modifier la sémantique du programme
original. On utilisera pour cela les techniques classiques de l'interprétation
abstraite.
Dans un exemple plus réaliste, le dispositif DB de la figure 8A
utilisera des méthodes plus sophistiquëes pour lier la marque m au
3o programme original P dans le programme tatoué PT. Dans le cadre de
l'exemple considéré ci-dessus, il faut pour cela pouvoir utiliser des
propriétés
invariantes secrètes de la variable de tatouage qui soient transposables en
arithmétique signée sur 32 bits. C'est possible très simplement lorsque, par
exemple, la clef Ki est une puissance de 2. En effet, supposons que Ki =2k .
Alors on a
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
62
x=s+a.2kdansZ
Nous avons, toujours dans Z, que, pour tout j inférieur ou égal à
k:
x%2J=s%2J
où x % y désigne l'opération qui renvoie le reste de la division
euclidienne de x par y .On remarque que cette propriété reste trivialement
vraie dans Z/232Z qui est le domaine des entiers JavaTM. Les propriétés
arithmëtiques du tatouage peuvent être utilisées pour modifier des calculs de
la méthode. Par exemple, supposons que Ki = 216 et que s =18. Alors quelle
que soit la valeur de x , l'invariant x % 4=2 est toujours satisfait. De ce
fait,
une constante explicite 2 dans le programme original P, peut être remplacëe
par x % 4 dans le programme tatoué PT. Les autres constantes ou valeurs
de variables du programme tatoué PT peuvent également être aisément
calculées en fonction de cette valeur. Par exemple 1 dans P sera simplement
~ 5 remplacé par (x % 4)-1 dans PT.
Ceci conclut la description du dispositif de tatouage DT sur
l'exemple considéré par enchaînement des dispositifs DC, DM et DB comme
indiqué à la figure 10A et du dispositif DG par enchaînement des dispositifs
DPS, DA et DT comme indiqué à la figure 11A.
2o Dans cet exemple, le dispositif DS de la figure 6A calcule la
sémantique statique secrète s = (s1, ...,sn) en faisant n analyses statiques
successives du programme tatoué selon l'interprétation abstraite définie ci
dessus consistant en une analyse en avant, pouvant ignorer le flot de
contrôle ou non, avec propagation des constantes modulo les clés restées
25 secrètes K1, ..., Kn.
Ä partir de cette sémantique statique secrète s = (s1, ...,sn), ie
dispositif DF calcule l'authentifiant original du programme P comme indiqué à
la figure 8 bis.
Si le domaine D(K) utilisé dans l'exemple ci-dessus est public
30 (mais pas 1â clé K), alors la sémantique statique secrète s peut être
découverte par la force brute, du moins pour de très petits programmes
comportant peu de variables entières. Dans un exémple plus réaliste on
utilisera donc, non pas des clés s1,..., sn codées sur 32 bits, mais une ou
plusieurs clés s de 512 bits utilisant, par exemple, un codage àrithmétique de
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
63
la valeur de <watermark: xi : s> sur 16 variables de 32 bits ou 8 de 64 bits
ou utilisant toute autre technique de codage informatique de grands entiers.
Ceci conclut la description du dispositif DAu de la figure 12A pour
l'exemple considéré.
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
64
ANNEXE 7
Exemple 4
Un quatrième exemple est le programme de tri suivant
private static void bubbleSort (double [] data, int size) {
int indexl , index2;
double temps
boolean exchanged;
1o for (indexl = size; indexl >= 2; indexl--) {
exchanged = false;
for (index2 = 1; index2 <= indexa - 1; index2++) {
. if (data [index2] > data [index2 + 1 ]) {
temp = data [index2];
data [index2] = data [index2 + 1];
data [index2 + 1 ] = temps
exchanged = true;
2o if (!exchanged)
break;
Ä nouveau n=2, K1=10000 et K2=5421. La méthode bubblesort
est tatouée deux fois, une première fois par la même signature sémantique
secrète (2507, 3012) que ci-dessus et la deuxième fois par la signature
secrète (9876, 2345). Le deuxième tatouage aurait aussi bien pu être réalisé
pour des valeurs différentes de K1 et K2. Après compilation, tatouage,
obfuscation et décompilation, on obtient la classe bubblesort comme suit
private static void bubbleSort (double [] r0, int i0) {
int i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11;
double d0;
i1 = 1;
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
i2=i1;
i3 = i2;
i4 = i3;
i5 = i2 - 35539;
5 i6 = i1 - 62508;
i7 = i3 - 129877;
i6 = i1 * i6;
i5 = i2 * i5;
i1 = i6 - 144986;
10 i8 = i4 + 84390;
i7 = i3 * i7;
i2=i5-75291;
i8 = i4 * i8;
i3 = i7 + 169752;
15 i4=i$+10111;
for (i9 = i0; i9 >= 2; i9--) {
i10=0;
for (i11 = 1; i11 <= i9 - 1; i11++) {
if (r0 [i11] > r0 [i11 + 1]) {
20 i6 = i1 * 620;
i6=i6+1151;
d0 = r0 [i11];
i6=i6*i1;
i1 = i6 + 6570;
25 r0[i11]=r0[i11 +1];
i8 = i4 * 936;
i5 = i2 * 620;
i5=i5+1151;
i5 = i5 * i2;
30 i8 = i8 + 1057;
i2 = i5 + 2961;
r0 [i11 + 1] = d0;
i7 = i3 * 1231;
i7 = i7 + 1699;
35 if ((i2 - 2961 ) _= i5)
CA 02446291 2003-11-03
WO 02/091141 PCT/FR02/01389
66
i10= 1;
i8 = i8 * i4;
i7 = i7 * i3;
i3 = i7 + 2696;
i4 = i8 + 1389;
if (i 10 == 0)
break;
