4 Les informations traitées par un ordinateur ne sont, \textit{in fine},
5 que discrètes: les flottants (sur un nombre fini de bits) sont une
6 interprétation des réels, les \textit{longs} une interprétation finie
8 Les phénomènes physiques ou naturels peuvent aussi être modélisés par des
10 il n'est parfois pas nécessaire de suivre exactement tous les états par
11 lesquels peut passer l'élément d'étude. Pour peu que l'on sache
12 identifier les seuils de son domaine (c'est-à-dire les valeurs
13 critiques permettant au système global de changer),
14 il est parfois suffisant de réduire le domaine de l'état de l'élément
15 à un ensemble fini d'intervalles définis par ces seuils.
16 Un élément passe d'un état $i$ à un état $j$ si dans la version continue il
17 passe d'un état de l'intervalle numéro $i$ à un état de l'intervalle numéro $j$.
18 En abstrayant à l'extrême,
19 on peut considérer pour chaque élément seulement deux états:
20 1 pour le fait d'être présent et 0 pour le fait d'être absent, ou bien
21 1 pour le fait d'avoir une valeur supérieure à un seuil et 0 pour le fait qu'elle y soit inférieure.
22 Ces réseaux particuliers sont qualifiés de \emph{réseaux booléens}.
25 Soit ${\mathsf{N}}$ un entier naturel représentant le nombre
26 d'éléments étudiés (le nombre bits qu'un générateur veut engendrer,
27 le nombre de pixel que l'on veut modifier\ldots) un réseau booléen est
28 défini à partir d'une fonction booléenne $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$
29 et un mode de mise à jour.
30 A chaque étape, on peut intuitivement ne modifier qu'une partie des
31 $\mathsf{N}$ éléments.
32 En fonction des éléments qui sont susceptibles d'être modifiés à chaque étape,
33 on peut se poser les questions de savoir si le réseau atteint un point fixe (et qu'il peut donc converger) ou
34 s'il possède des attracteurs cycliques (et qu'il diverge donc).
36 Détecter la convergence ou son contraire peut se faire \textit{ a priori} dans
37 certain cas. En effet, de nombreux travaux ont énoncé des conditions
38 suffisantes sur les réseaux booléens garantissant leur convergence
39 ou leur divergence . Lorsqu'aucune d'entre elle ne s'applique, on peut penser
40 à étendre ces résultats théoriques et compléter ceci par des simulations.
41 Lorsque la convergence est pratiquement observée, il reste à vérifier que
42 celle-ci est indépendante du choix des parties à modifier, par exemple.
43 Une vérification \textit{a posteriori} s'impose, sauf si la méthode de
44 simulation a été prouvée comme exhaustive.
46 Une fonction qui admet un attracteur cyclique égal à l'ensemble
47 des sommets diverge. Admet-il cependant un comportement chaotique?
48 Les théories mathématiques du chaos ont énoncé des critères permettant
49 de décider si une fonction est chaotique ou non, et plus récemment
50 si certains réseaux booléens étaient l'étaient. Se pose légitimement
51 la question de savoir si cette caractérisation s'étend quelque soient
52 les parties modifiées à chaque étape. Naturellement, ceci n'a un sens
53 pratique que si le nombre de réseaux booléens qui possèdent cette
54 caractéristique est suffisamment grand et que l'on sache engendrer
55 algorithmiquement de tels réseaux.
57 Les liens entre chaos et aléas sont certes intuitifs, mais sont-ils suffisants
58 pour espérer construire un générateur de nombres pseudo-aléatoires (PRNG)
59 à partir de fonctions au comportement chaotique? La réponse est certes
60 positive, mais pas triviale. Il est nécessaire de définir les propriétés
61 attendues de la sortie d'un PRNG et
62 l'uniformité de sa distribution est sans doute la première
63 des propriétés à assurer.
64 Comment alors générer des fonctions chaotiques dont les itérations
65 peuvent converger vers une distribution uniforme?
66 Combien d'itérations suffit-il alors
67 d'effectuer pour s'approcher suffisamment de celle-ci?
69 Les liens entre chaos et marquage d'information sont aussi faciles à établir:
70 de tout média marqué même attaqué, la marque doit pouvoir être extraite.
71 Cette propriété du marquage est proche en effet de celle de régularité des opérateurs chaotique. Il est alors naturel d'envisager exploiter les
72 fonctions chaotiques extraites dans ce contexte et donc de modifier
73 certains bits d'un média pour y insérer de l'information: la marque.
76 Les compétences acquise dans l'étude des algorithme d'insertion d'une marque
77 dans une image nous permettent aussi d'adresser le problème d'insérer un message dans une image. Cependant, il s'agit de privilégier
78 cette fois l'imperceptibilité et non plus la robustesse. Ainsi, tandis que
79 l'idée principale était d'étaler le message sur un ensemble conséquent
80 de pixels pour adresser la robustesse, il s'agit ici de sélectionner finement
81 ceux dont les modifications seraient le moins perceptibles possible.
82 On pense immédiatement à insérer ces messages dans les pixels
83 contenant les zones les plus perturbées.
84 Les outils mathématiques d'analyse permettant d'identifier les lignes niveaux
85 pour ensuite voir lesquelles sont les moins régulières, les plus perturbées
86 sont le gradient et la matrice Hessienne.
87 Cependant, ces modèles d'analyse ne sont définis que pour des fonctions de $\R^n$ dans $\R$.
88 Se pose alors la question sur la possibilité de les adapter au cadre discret
89 puisque les images à traiter sont construites à partir de pixels dont les
90 valeurs sont discrètes.
93 \section*{Organisation de ce mémoire}
94 Ce mémoire est organisé en quatre parties.
96 La première partie sur les réseaux discrets.
97 Dans celle-ci, le chapitre~\ref{chap:sdd} formalise la notion de réseaux booléens
98 et leurs modes opératoires. On y définit notamment un nouveau mode opératoire
99 combinant convergence et rapidité de convergence. Les résultats de convergence suffisants à la compréhension de ce mémoire y sont rappelés et ceux relatifs à ce nouveau mode y sont prouvés.
101 Le chapitre~\ref{chap:promela} montre comment nous avons développé une démarche
102 de preuve automatique de convergence de réseaux discrets. La démarche est
103 prouvée correcte et complète: le verdict donné par l'outil est celui qui serait
104 donné par une preuve mathématique.
106 La seconde partie établit globalement le lien entre les réseaux discrets et
107 le chaos. Le chapitre~\ref{chap:carachaos} rappelle tout d'abord les notions
108 suffisantes concernant la théorie du chaos. Une caractérisation des fonctions engendrant des itérations
109 chaotiques y est donnée, selon le mode unaire et le mode généralisé,
110 les deux modes au c{\oe}ur de ce mémoire. Un théorème,
111 démontré, propose un algorithme permettant de générer des fonctions possédant
112 cette caractéristique.
114 Les itérations unaires de telles fonctions étant chaotiques, nous avons étudié
115 au chapitre~\ref{chp:ANN} la possibilité de les faire apprendre par un réseau de neurones, particulièrement un perceptron multi-couches.
117 Le titre de la troisième partie donne une idée de la conclusion de
118 cette étude puisqu'on y étudie une famille PRNG construite à partir de fonctions
119 dont les itérations sont chaotiques.
120 Plus précisément, le chapitre~\ref{chap:PRNG:chao} caractérise les PRNG
121 construits à partir de réseaux booléens qui sont chaotiques en donnant
122 des conditions suffisantes sur la fonction à itérer.
123 Le chapitre~\ref{chap:PRNG:gray} s'intéresse donc à générer
124 ce type de fonction de manière autrement plus efficaces qu'à partir de
125 la méthode décrite au chapitre~\ref{chap:carachaos}. On y présente aussi un
126 majorant du nombre d'itérations à effectuer pour obtenir une distribution
129 Comme annoncé dans les motivations à ce travail, les itérations chaotiques
130 peuvent s'appliquer à marquage de média et plus généralement
131 au masquage d'information. C'est l'objectif de la quatrième partie.
133 Dans le premier chapitre de celle-ci (chapitre~\ref{chap:watermarking}), nous
134 formalisons le processus de marquage d'information. Grâce à cette formalisation,
135 nous pouvons étudier des propriétés de stego securité et chaos sécurité.
137 Les deux chapitres suivants (chapitre~\ref{chap:watermarking:pdf} et
138 chapitre~\ref{chap:stabylo}) sont une parenthèse
139 au domaine discret puisqu'on s'intéresse au marquage de document PDF par une
140 méthode classique et au masquage d'information par une technique de détection
143 Le dernier chapitre des contributions (chapitre~\ref{chap:th:yousra})
144 retourne dans le monde discret. Il montre qu'on peut approximer efficacement
145 à l'aide de matrices discrètes des calculs de gradients pour, \textit{in fine},
146 construire des lignes de niveau et embarquer de l'information dans les lignes
147 de niveau les moins régulières.
149 Une conclusion et des perspectives sont données en dernière partie.
151 \section*{Publications issues des travaux de recherche post doctorale}
152 Le tableau de la figure~\ref{fig:bilan} donné
153 ci dessous synthétise les références auxquelles j'ai participées
154 depusi que je suis au DISC.
158 \begin{tabular}{|c|c|}
160 %& \multicolumn{2}{|c|}{Internationaux} & {Nationaux} & \\
162 Journaux & Conférences \\
163 internationaux & internationales
166 \cite{bcg12:ij,bcg11:ij,bcgs12:ij}
169 \cite{aagc+15:ip,bcfg12a:ip,bcfg12b:ip,bcfg+13:ip,bcg11:ip}
175 \cite{cds13:ij,ccg15:ij,BDCC16}
180 \cite{bcg11b:ip,acgs13:onp,BCVC10:ir,chgw+14:onp,Cou10:ir}
189 \cite{bcgr11:ip,bcgw11:ip,cds12:ip,chgw+14:oip,fccg15:ip}
198 \cite{accfg15:ip,ccfg16:ip,kcm16:ip}
208 \caption{Bilan synthétique des publications}\label{fig:bilan}
