From 3759a997c005ffb313be135f98820410cb6061b4 Mon Sep 17 00:00:00 2001 From: couchot Date: Mon, 19 Sep 2016 09:29:29 +0200 Subject: [PATCH] =?utf8?q?apr=C3=A8s=20correction=20sylvaine?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- 12TIPE.tex | 6 +- 14Secrypt.tex | 63 +++++++-------- 15RairoGen.tex | 32 ++++---- 15TSI.tex | 4 +- ahmad.tex | 4 +- annexePreuveDistribution.tex | 8 +- annexePreuveGrayEquilibre.tex | 2 +- annexePreuveMarquageCorrectioncompletude.tex | 4 +- annexePreuveMarquagedhci.tex | 6 +- annexePreuveMarquagefldblement.tex | 12 +-- annexePreuveMixage.tex | 26 +++--- annexePreuveStopping.tex | 22 +++--- annexePromelaProof.tex | 51 ++++++------ annexesccg.tex | 2 +- chaosANN.tex | 41 +++++----- conclusion.tex | 13 +-- intro.tex | 43 +++++----- main.tex | 83 +++++++++++++++----- mixage.tex | 44 +++++------ modelchecking.tex | 41 +++++----- oxford.tex | 70 ++++++++--------- preuveDistanceGeneralisee.tex | 2 +- sdd.tex | 8 +- stabylo.tex | 20 ++--- stegoyousra.tex | 30 +++---- 25 files changed, 345 insertions(+), 292 deletions(-) diff --git a/12TIPE.tex b/12TIPE.tex index 7c04d49..e54ed79 100644 --- a/12TIPE.tex +++ b/12TIPE.tex @@ -41,7 +41,7 @@ G_{f_u}(x,s)=(F_{f_u}(x,s_0),\sigma(s)). \end{equation} Dans cette définition, la fonction -$\sigma: {\mathsf{N}}]^{\Nats} \longrightarrow +$\sigma: [{\mathsf{N}}]^{\Nats} \longrightarrow [{\mathsf{N}}]^{\Nats} $ décale @@ -54,7 +54,7 @@ $$ Ainsi, effectuer des itérations unaires sur la fonction $f$ selon une stratégie $s$ revient à effectuer des itérations -parallèles de la fonctions $G_{f_u}$ dans $\mathcal{X}_u$. +parallèles de la fonction $G_{f_u}$ dans $\mathcal{X}_u$. La section suivante introduit une métrique sur $\mathcal{X}_u$. \subsection{Une métrique pour $\mathcal{X}_u$} @@ -99,7 +99,7 @@ chaotiques $G_{f_u}$ sur $\mathcal{X}_u$} % $G_{f_u}$ est continue sur $\mathcal{X}_u$ (cf annexe~\ref{anx:cont}). Pour caractériser les fonctions rendant chaotiques dans $\mathcal{X}_u$ les itérations de $G_{f_u}$ -on se focalise donc que sur la régularité et sur la transitivité de $G_{f_u}$. +on se focalise donc sur la régularité et sur la transitivité de $G_{f_u}$. Ceci se réalise en établissant les relations d'inclusion entre les ensembles $\mathcal{T}$ des fonctions topologiquement transitives, $\mathcal{R}$ des fonctions régulières diff --git a/14Secrypt.tex b/14Secrypt.tex index 858a8e5..5e4cafc 100644 --- a/14Secrypt.tex +++ b/14Secrypt.tex @@ -12,7 +12,7 @@ Une approche plus pragmatique consiste à supprimer un cycle hamiltonien dans l graphe d'itérations $\textsc{giu}(\neg)$ (section~\ref{sec:hamiltonian}). Pour obtenir plus rapidement une distribution uniforme, l'idéal serait de supprimer un cycle hamiltonien qui nierait autant de fois chaque bit. -Cette forme de cycle est dit équilibré. La section~\ref{sub:gray} établit le +Cette forme de cycle est dite équilibré. La section~\ref{sub:gray} établit le lien avec les codes de Gray équilibrés, étudiés dans la littérature. La section suivante présente une démarche de génération automatique de code de Gray équilibré (section~\ref{sec:induction}). La vitesse avec laquelle l'algorithme de PRNG converge en interne vers @@ -55,7 +55,7 @@ la matrice est stochastique à droite; \item pour chaque indice de colonne $j$, $1 \le j\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le i\le 2^{\mathsf{N}}} M_{ij}$: la matrice est stochastique à gauche; -\item Toutes les éléments de la somme $\sum_{1\le k\le 2^{\mathsf{N}}}M^k$ sont strictement positif, \textit{i.e.}, le graphe $\textsc{giu}(f)$ est fortement connexe; +\item Tous les éléments de la somme $\sum_{1\le k\le 2^{\mathsf{N}}}M^k$ sont strictement positifs, \textit{i.e.}, le graphe $\textsc{giu}(f)$ est fortement connexe; \end{enumerate} Ce problème s'exprime sur des domaines finis entiers avec des opérateurs arithmétiques simples (sommes et produits). Il pourrait théoriquement être @@ -69,7 +69,7 @@ ici pour $\mathsf{N} = 2$. Dans ce code, \verb+summ(+$X,Y,R$\verb+)+ valent True si et seulement si $R$ est le produit matriciel (ou la somme matricielle) -entre $X$ and $Y$ respectivement. +entre $X$ et $Y$ respectivement. Il n'est pas difficile d'adapter ce code à n'importe quelle valeur entière naturelle $\mathsf{N}$. @@ -120,7 +120,7 @@ Cette approche, basée sur une démarche de type \emph{générer, tester} ne peu pas être retenue pour $n$ de grande taille, même en s'appuyant sur l'efficience de l'algorithme de backtrack natif de PROLOG. -Cependant, pour des valeurs de $n$ petites, nous avons +Cependant, pour des petites valeurs de $n$, nous avons comparé les fonctions non équivalentes selon leur proportion à engendrer des temps de mélange petits (cf. équation~(\ref{eq:mt:ex})). @@ -162,9 +162,9 @@ $$ \end{table} \end{xpl} -Une analyse syntaxique de ces fonctions ne permet pas, à priori, +Une analyse syntaxique de ces fonctions ne permet pas, a priori, de déduire des règles permettant de construire de nouvelles -fonction dont le temps de mélange serait faible. +fonctions dont le temps de mélange serait faible. Cependant, le graphe $\textsc{giu}(f^*)$ (donné à la Figure~\ref{fig:iteration:f*}) est le $3$-cube dans lequel le cycle @@ -320,9 +320,9 @@ hamiltonien $c$. Aucun arc n'appartient à la fois à $r$ et à $c$: en effet, sinon $c$ contiendrait un n{\oe}ud deux fois. Ainsi aucune arête de $r$ n'est enlevée dans $C_1$. -Le cycle $r$ est évidement un cycle hamiltonien et contient tous les n{\oe}uds. -Tous les n{\oe}uds de $C_1$ dans lequel $c$ a été enlevé sont accessibles -depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsf{giu}$ qui +Le cycle $r$ est évidemment un cycle hamiltonien et contient tous les n{\oe}uds. +Tous les n{\oe}uds de $C_1$ dans lesquels $c$ a été enlevé sont accessibles +depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsc{giu}$ qui étend le précédent graphe est ainsi fortement connexe. \end{proof} @@ -435,17 +435,17 @@ deux premiers éléments qui ont été intervertis. L'étape~(\ref{item:nondet}) n'est pas constructive: il n'est pas précisé comment sélectionner des sous-séquences qui assurent que le code obtenu est équilibré. -La théorème suivante montre que c'est possible et sa preuve, -donnée en annexes~\ref{anx:generateur}, explique comment le faire. +Le théorème suivant montre que c'est possible et sa preuve, +donnée en annexe~\ref{anx:generateur}, explique comment le faire. \begin{restatable}[Existence d'un code de Gray équilibré]{theorem}{theograyequilibre} \label{prop:balanced} Soit $\mathsf{N}$ dans $\Nats^*$, et $a_{\mathsf{N}}$ défini par $a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$. -il existe une séquence $l$ dans l'étape~(\ref{item:nondet}) de l'extension -de l'algorithme de \emph{Robinson-Cohn} extension telle que -le nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$ -sont tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$ +Il existe une séquence $l$ dans l'étape~(\ref{item:nondet}) de l'extension +de l'algorithme de \emph{Robinson-Cohn} telle que +les nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$ +valent tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$ pour chaque $i$, $1 \le i \le \mathsf{N}$. \end{restatable} @@ -461,11 +461,11 @@ stratégie donnée. Tout d'abord, celles-ci peuvent être interprétées comme une marche le long d'un graphe d'itérations $\textsc{giu}(f)$ tel que le choix de tel ou tel arc est donné par la stratégie. -On remarque que ce graphe d'itération est toujours un sous graphe +On remarque que ce graphe d'itérations est toujours un sous graphe du ${\mathsf{N}}$-cube augmenté des boucles sur chaque sommet, \textit{i.e.}, les arcs $(v,v)$ pour chaque $v \in \Bool^{\mathsf{N}}$. -Ainsi, le travail ci dessous répond à la question de +Ainsi, le travail ci-dessous répond à la question de définir la longueur du chemin minimum dans ce graphe pour obtenir une distribution uniforme. Ceci se base sur la théorie des chaînes de Markov. @@ -513,7 +513,7 @@ On remarque que dans cette marche on reste sur place avec une probabilité égal à $\frac{1}{2}+\frac{1}{2\mathsf{N}}$ et l'on passe d'un sommet à son voisin lorsque c'est possible avec une probabilité $\frac{1}{2\mathsf{N}}$. Les probabilités usuelles que l'on appliquerait aux transitions de -l'algorithme~\ref{CI Algorithm} serait quant à elles uniformément égales +l'algorithme~\ref{CI Algorithm} seraient quant à elles uniformément égales à $\frac{1}{\mathsf{N}}$. Cette manière paresseuse d'itérer (puisqu'on reste plus souvent sur place) n'est donc pas équivalente à celle issue de l'algorithme. @@ -530,7 +530,7 @@ $$\tv{\pi-\mu}=\max_{A\subset \Bool^{\mathsf{N}}} |\pi(A)-\mu(A)|.$$ On sait que $$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$ De plus, si -$\nu$ est une distribution on $\Bool^{\mathsf{N}}$, on a +$\nu$ est une distribution sur $\Bool^{\mathsf{N}}$, on a $$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}.$$ Soit $P$ une matrice d'une chaîne de Markov sur $\Bool^{\mathsf{N}}$. @@ -545,8 +545,8 @@ et $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ Intuitivement, $t_{\rm mix}(\varepsilon)$ est le nombre d'itérations nécessaire -pour être proche de la distribution stationnaire à $\varepsilon$ prêt, -peut importe la configuration de départ. On a le théorème suivant démontré en annexes~\ref{anx:generateur}. +pour être proche de la distribution stationnaire à $\varepsilon$ près, +peu importe la configuration de départ. On a le théorème suivant démontré en annexe~\ref{anx:generateur}. \begin{restatable}[Temps de mixage sans chemin hamiltonien]{theorem}{theotpsmix} @@ -577,7 +577,7 @@ pour chaque n{\oe}ud du $\mathsf{N}$-cube un arc entrant et un arc sortant sont supprimés. Le fait qu'on enlève un cycle hamiltonien et que ce dernier soit équilibré n'est pas pris en compte. -En intégrant cette contrainte, ce majorant pourrait être réduite. +En intégrant cette contrainte, ce majorant pourrait être réduit. En effet, le temps de mixage est en $\Theta(N\ln N)$ lors d'une marche aléatoire classique paresseuse dans le $\mathsf{N}$-cube. @@ -596,7 +596,7 @@ résume ces résultats. Dans celle-ci, un cercle représente une approximation $E[\ts]$ pour un $\mathsf{N}$ donné tandis que la courbe est une représentation de la fonction $x \mapsto 2x\ln(2x+8)$. On constate que l'approximation de $E[\ts]$ est largement inférieure -à le majorant quadratique donné au théorème~\ref{prop:stop} et que la conjecture +au majorant quadratique donné au théorème~\ref{prop:stop} et que la conjecture donnée au paragraphe précédent est sensée. @@ -695,8 +695,9 @@ Elle n'est donc pas rappelée. \begin{xpl} On reprend l'exemple donné à la section~\ref{sec:plc}. - Dans le $3$-cube, le cycle hamiltonien défini par la séquence - $000,100,101,001,011,111,110,010,000$ a été supprimé engendrant + On considère le cycle hamiltonien défini par la séquence + $000,100,101,001,011,111,110,010,000$. En supprimant celui-ci dans + le $3$-cube, cela engendre la fonction $f^*$ définie par $$f^*(x_1,x_2,x_3)= (x_2 \oplus x_3, \overline{x_1}.\overline{x_3} + x_1\overline{x_2}, @@ -827,7 +828,7 @@ fonctions qui ont été générées selon la méthode détaillée à la section~\ref{sec:hamiltonian}. Pour chaque nombre $n=3$, $4$, $5$ et $6$, tous les cycles hamiltoniens non isomorphes ont été générés. Pour les -valeur de $n=7$ et $8$, seules $10^{5}$ cycles ont été évalués. Parmi +valeur de $n=7$ et $8$, seuls $10^{5}$ cycles ont été évalués. Parmi toutes les fonctions obtenues en enlevant du $n$-cube ces cycles, n'ont été retenues que celles qui minimisaient le temps de mélange relatif à une valeur de $\epsilon$ fixée à $10^{-8}$ et pour un mode donné. @@ -837,7 +838,7 @@ colonne sous la variable $b$. La variable $b'$ reprend le temps de mélange pour l'algorithme~\ref{CI Algorithm}. On note que pour un nombre $n$ de bits fixé et un mode donné d'itérations, -il peut avoir plusieurs fonctions minimisant ce temps de mélange. De plus, comme ce temps +il peut y avoir plusieurs fonctions minimisant ce temps de mélange. De plus, comme ce temps de mélange est construit à partir de la matrice de Markov et que celle-ci dépend du mode, une fonction peut être optimale pour un mode et ne pas l'être pour l'autre (c.f. pour $n=5$). @@ -901,7 +902,7 @@ $$ \end{array} $$ \caption{Nombre moyen - d'appels à un générateurs binaire par bit généré}\label{table:marchevssaute} + d'appels à un générateur binaire par bit généré}\label{table:marchevssaute} \end{table} @@ -926,7 +927,7 @@ permet de générer la stratégie aléatoire. que la chaîne est considérée comme aléatoire avec une confiance de $99\%$. -Les tableau~\ref{fig:TEST:generalise} donnent +Les tableaux~\ref{fig:TEST:generalise} donnent une vision synthétique de ces expérimentations. Nous avons évalué les fonctions préfixées par $f$ (respectivement $g$) avec les générateurs issus des itérations @@ -936,10 +937,10 @@ générateurs passe avec succès le test de NIST. Interpréter ces résultats en concluant que ces générateurs sont -tous équivalents serait erroné: la meilleur des +tous équivalents serait erroné: la meilleure des méthodes basées sur le mode des itérations généralisées (pour $n=8$ par exemple) -est au moins deux fois plus rapide que la meilleur de celles qui +est au moins deux fois plus rapide que la meilleure de celles qui sont basées sur les itérations unaires. diff --git a/15RairoGen.tex b/15RairoGen.tex index 432991f..a57e19f 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -59,7 +59,7 @@ En interne, il exploite un algorithme de génération de nombres pseudo aléatoires donné en paramètre. Cela peut être n'importe quel PRNG (XORshift, Mersenne-Twister) dont la sortie est uniformément distribuée. -Notre approche vise a donner des propriétés de chaos a ce générateur embarqué. +Notre approche vise a donner des propriétés de chaos à ce générateur embarqué. % \textit{Random}$(l)$. @@ -97,11 +97,11 @@ Notre approche vise a donner des propriétés de chaos a ce générateur embarqu Nous avons vu au chapitre~\ref{chap:carachaos} que $G_{f_u}$ est chaotique dans l'espace $\mathcal{X}_u$ -si et seulement le graphe d'itérations $\textsc{giu}(f)$ +si et seulement si le graphe d'itérations $\textsc{giu}(f)$ est fortement connexe. Pour $b=1$, l'algorithme itère la fonction $F_{f_u}$. -Pour simuler au mieux l'aléa, un bon générateur de nombre pseudo-aléatoires +Pour simuler au mieux l'aléa, un bon générateur de nombres pseudo-aléatoires se doit de fournir des nombres selon une distribution uniforme. Regardons comment l'uniformité de la distribution contraint la fonction $f$ à itérer. @@ -118,7 +118,7 @@ si la propriété suivante est établie: $$\exists k \in \mathds{N}^\ast, \forall i,j \in \llbracket 1; n \rrbracket, M_{ij}^k>0.$$ On énonce le théorème classique suivant liant les -vecteur de probabilités +vecteurs de probabilités et les chaînes de Markov. @@ -140,7 +140,7 @@ et les chaînes de Markov. Montrons sur un exemple jouet à deux éléments que ce théorème permet de vérifier si la sortie d'un générateur de nombres pseudo aléatoires est uniformément distribuée ou non. -Soit alors $g$ et $h$ deux fonctions de $\Bool^2$ +Soient alors $g$ et $h$ deux fonctions de $\Bool^2$ définies par $g(x_1,x_2)=(\overline{x_1},x_1.\overline{x_2}) $ et $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$. Leurs graphes d'interactions donnés en figure \ref{fig:g:inter} et \ref{fig:h:inter} @@ -294,7 +294,7 @@ de valeurs soit suffisamment grand de sorte que le vecteur d’état de la chaîne de Markov ait une distribution suffisamment proche de la distribution uniforme. -On énonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}. +On énonce directement le théorème suivant dont la preuve est donnée en annexe~\ref{anx:generateur}. \begin{restatable}[Uniformité de la sortie de l'algorithme~\ref{CI Algorithm}]{theorem}{PrngCIUniforme}\label{thm:prng:u} Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son @@ -478,7 +478,7 @@ F_{f_u}(\hdots (F_{f_u}(F_{f_u}(x,u^0), u^1), \hdots), u^{p_i-1}). $$ -on construit l'espace +On construit l'espace $\mathcal{X}_{\mathsf{N},\mathcal{P}}= \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, où $\mathds{S}_{\mathsf{N},\mathcal{P}}= [\mathsf{N}]^{\Nats}\times @@ -528,7 +528,7 @@ où $s=(u,v)$ et $\check{s}=(\check{u},\check{v})$ sont dans $ \mathds{S}_{\math \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. \begin{enumerate} \item $e$ et $\check{e}$ sont des entiers appartenant à $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. -La distance de Hamming $d_{\mathds{B}^\mathsf{N}}$ sur entre les +La distance de Hamming $d_{\mathds{B}^\mathsf{N}}$ entre les décompositions binaires de $e$ et de $\check{e}$ (\textit{i.e.}, le le nombre de bits qu'elles ont de différent) constitue la partie entière de $d(X,\check{X})$. @@ -558,7 +558,7 @@ jusqu'à atteindre $p+n\times \max{(\mathcal{P})}$ éléments. \item Si $v^0<\check{v}^0$, alors les $ \max{(\mathcal{P})}$ blocs de $n$ éléments sont $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$, -$\check{u}^{v^0}$ (sur $n$ éléments), ..., $\check{u}^{\check{v}^0-1}$ (sur $n$ éléments), suivi par des 0, si besoin. +$\check{u}^{v^0}$ (sur $n$ éléments), ..., $\check{u}^{\check{v}^0-1}$ (sur $n$ éléments), suivis par des 0, si besoin. \item Le cas $v^0>\check{v}^0$ est similaire, et donc omis \end{enumerate} \item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc. @@ -615,7 +615,7 @@ On prend alors le $v^0=1$ premier terme de $u$, chaque terme étant codé sur $n=2$ éléments, soit 06. Comme on itère au plus $\max{(\mathcal{P})}$ fois, on complète cette valeur par des 0 de sorte que -la chaîne obtenue a $n\times \max{(\mathcal{P})}=22$ éléments, soit: +la chaîne obtenue ait $n\times \max{(\mathcal{P})}=22$ éléments, soit: 0600000000000000000000. De manière similaire, les $\check{v}^0=2$ premiers termes de $\check{u}$ sont représentés par @@ -652,7 +652,7 @@ la séquence. -On a la proposition suivante, qui est démontrée en annexes~\ref{anx:generateur}. +On a la proposition suivante, qui est démontrée en annexe~\ref{anx:generateur}. \begin{restatable}[Une distance dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$]{theorem}{distancedsxnp} @@ -722,12 +722,12 @@ $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$ déjà détail Le graphe $\textsc{giu}_{\{1\}}(h)$ a déjà été donné à la figure~\ref{fig:h:iter}. Les graphes $\textsc{giu}_{\{2\}}(h)$, $\textsc{giu}_{\{3\}}(h)$ et -$\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnés aux figure~\ref{fig:h2prng}, ~\ref{fig:h3prng} et ~\ref{fig:h23prng}. +$\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnés aux figures~\ref{fig:h2prng}, ~\ref{fig:h3prng} et ~\ref{fig:h23prng}. Le premier (respectivement le second) illustre le comportement du générateur lorsque qu'on itère exactement 2 fois (resp. 3 fois) puis qu'on affiche le résultat. Le dernier donnerait le comportement d'un générateur qui s'autoriserait -à itérer en interne systématiquement 2 ou trois fois avant de retourner un résultat. +à itérer en interne systématiquement 2 ou 3 fois avant de retourner un résultat. \end{xpl} @@ -735,12 +735,12 @@ Le dernier donnerait le comportement d'un générateur qui s'autoriserait \subsection{le PRNG de l'algorithme~\ref{CI Algorithm} est chaotique sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$} Le théorème suivant, similaire à ceux dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$ -est prouvé en annexes~\ref{anx:generateur}. +est prouvé en annexe~\ref{anx:generateur}. -\begin{restatable}[Conditions pour la choticité de $G_{f_u,\mathcal{P}}$]{theorem}{thmchoticitgfp} +\begin{restatable}[Conditions pour la chaoticité de $G_{f_u,\mathcal{P}}$]{theorem}{thmchoticitgfp} La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si -le graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ +le graphe d'itérations $\textsc{giu}_{\mathcal{P}}(f)$ est fortement connexe. \end{restatable} % On alors corollaire suivant diff --git a/15TSI.tex b/15TSI.tex index 138036f..670df80 100644 --- a/15TSI.tex +++ b/15TSI.tex @@ -49,7 +49,7 @@ $\mathcal{X}_g = \Bool^{\mathsf{N}} \times \subsection{Une métrique pour $\mathcal{X}_g$} Cette nouvelle distance va comparer des ensembles. -On rappelle pour quelques notions ensemblistes. +On rappelle quelques notions ensemblistes. Pour $A$ et $B$ deux ensembles de l'univers $\Omega$, on rappelle la définition de l'opérateur de \emph{différence ensembliste} symétrique : @@ -78,7 +78,7 @@ La fonction $d$ est une somme de deux fonctions. La fonction $d_H$ est la distance de Hamming; il est aussi établi que la somme de deux distances est une distance. Ainsi, pour montrer que $d$ est aussi une distance, il suffit -de montrer que $d_S$ en une aussi, ce qui est fait en annexe~\ref{anx:distance:generalise}. +de montrer que $d_S$ en est une aussi, ce qui est fait en annexe~\ref{anx:distance:generalise}. La section suivante caractérise les fonctions $f$ qui sont chaotiques pour le schéma généralisé. diff --git a/ahmad.tex b/ahmad.tex index 0f09bdd..3188a74 100644 --- a/ahmad.tex +++ b/ahmad.tex @@ -9,7 +9,7 @@ ajoutent des caractères invisibles dans le document. En supprimant ces espaces ou caractères invisibles, la marque s'enlève facilement. Dans~\cite{PD2008}, les auteurs modifient de manière imperceptible -le positionnements des caractères. D'autres éléments de positionnement +le positionnement des caractères. D'autres éléments de positionnement sont intégrés dans~\cite{WT08}. Une attaque qui modifierait aléatoirement de manière faible ces positions détruirait la marque dans les deux cas. @@ -164,7 +164,7 @@ possible de remarquer une différence entre le document original et le document marqué. Il nous reste à détailler les expériences d'étude de robustesse de la démarche. -Comme dans l'évaluation de la transparence, il s'est agit de faire +Comme dans l'évaluation de la transparence, il s'est agi de faire varier le paramètre $\Delta$. Pour chacune de ces valeurs, le document a été altéré selon un flou gaussien (de paramètre 0,1 et 0,25) diff --git a/annexePreuveDistribution.tex b/annexePreuveDistribution.tex index ea5f4f1..af03fed 100644 --- a/annexePreuveDistribution.tex +++ b/annexePreuveDistribution.tex @@ -63,10 +63,10 @@ $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$. Réciproquement si $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$, alors $\forall k \in \mathds{N}, v^k=\check{v}^k$ d'après la définition de $d$. Or les éléments entre les positions $p+1$ et $p+n$ -sont nules et correspondent à $|u^0-\check{u}^0|$, +sont nulles et correspondent à $|u^0-\check{u}^0|$, on peut conclure que $u^0=\check{u}^0$. On peut étendre ce résultat aux $n \times \max{(\mathcal{P})}$ premiers -bloc engendrant $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$, +blocs engendrant $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$, et en vérifiant tous les $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$. \item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ est évidemment symétrique ($d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\check{s},s)$). @@ -79,7 +79,7 @@ aussi. Montrons que: \begin{lemma} -Le graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ +Le graphe d'itérations $\textsc{giu}_{\mathcal{P}}(f)$ est fortement connexe si et seulement si la fonction $G_{f_u,\mathcal{P}}$ est topologiquement transitive sur $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$. @@ -92,7 +92,7 @@ Soit $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v})) On cherche un point $y$ dans une boule ouverte $\mathcal{B}(x,\varepsilon )$ et un nombre $n_0 \in \mathds{N}$ tels que $G_{f_u,\mathcal{P}}^{n_0}(y)=\check{x}$: -Cette transitivité forte entrainera la propriété de transitivité classique. +Cette transitivité forte entraînera la propriété de transitivité classique. On peut supposer que $\varepsilon <1$ sans perte de généralité. Soit $(E,(U,V))$ les éléments de $y$. Comme diff --git a/annexePreuveGrayEquilibre.tex b/annexePreuveGrayEquilibre.tex index 2d351e7..6d050b4 100644 --- a/annexePreuveGrayEquilibre.tex +++ b/annexePreuveGrayEquilibre.tex @@ -55,7 +55,7 @@ Tout d'abord, l'entier $r$ est pair puisque $r_{\mathsf{N}}$ est un multiple de $ r_{\mathsf{N}}= 2^{\mathsf{N}} - q_{\mathsf{N}}.2\mathsf{N}= 2(2^{\mathsf{N}-1} - q_{\mathsf{N}}.\mathsf{N})$. Ensuite, $a_{\mathsf{N}}$ vaut $\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}$. Ainsi -$d_{\mathsf{N}}$ vaut $r_{\mathsf{N}}/2$ est est donc un entier positif tel que +$d_{\mathsf{N}}$ vaut $r_{\mathsf{N}}/2$. C'est donc un entier positif tel que $0 \le d_{\mathsf{N}} <\mathsf{N}$. La preuve pour $c_{\mathsf{N}}$ est évidente. diff --git a/annexePreuveMarquageCorrectioncompletude.tex b/annexePreuveMarquageCorrectioncompletude.tex index 76e6e5c..287cf09 100644 --- a/annexePreuveMarquageCorrectioncompletude.tex +++ b/annexePreuveMarquageCorrectioncompletude.tex @@ -11,7 +11,7 @@ Soit $D=\{d_i|i \in \Im(S_p) \}$. L'ensemble $\Im(S_c)_{|D}$ est donc la restriction de l'image de $S_c$ à $D$. -Le vecteur qui résutle de ces itérations est donc +Le vecteur qui résulte de ces itérations est donc $(x^l_0,\ldots,x^l_{\mathsf{N}-1})$ où $x^l_i$ est soit $x^{d_i}_i$ si $i$ appartient à $\Im(S_p)$ ou $x^0_i$ sinon. De plus, pour chaque $i \in \Im(S_p)$, l'élément $x^{d_i}_i$ est égal à @@ -28,7 +28,7 @@ l'élément $j$ a été invoqué avant $d_i-1$. Réciproquement, si $\Im(S_c)_{|D} \subsetneq \llbracket 0 ;\mathsf{P} -1 \rrbracket$, -i lexiste un $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ qui n'appartient pas à $\Im(S_c)_{|\Im(S_p)}$. +il existe un $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ qui n'appartient pas à $\Im(S_c)_{|\Im(S_p)}$. Ainsi, $m_j$ n'est pas présent dans $x^l$ et le message ne peut pas extrait. \end{proof} diff --git a/annexePreuveMarquagedhci.tex b/annexePreuveMarquagedhci.tex index 22187f7..817e622 100644 --- a/annexePreuveMarquagedhci.tex +++ b/annexePreuveMarquagedhci.tex @@ -20,7 +20,7 @@ p(\textit{deci}(X^{t}) = j , S^t = k , i =_k j , f_k(j) = i_k ) \] \noindent où $ i =_k j $ est vraie si et seulement si les représentations binaires de -$i$ et de $j$ ne diffèrent que le $k^{\textrm{ème}}$ élément et +$i$ et de $j$ ne diffèrent que pour le $k^{\textrm{ème}}$ élément et où $i_k$ représente dans cette preuve le $k^{\textrm{ème}}$ élément dans la représentation binaire du nombre @@ -29,7 +29,7 @@ $i$. En raison des hypothèses sur la stratégie, la probabilité $p(\textit{deci}(X^t) = j , S^t = k , i =_k j, f_k(j) = i_k )$ est égale à $\frac{1}{l}.p(\textit{deci}(X^t) = j , i =_k j, f_k(j) = i_k)$. -Enfin, puisque $i =_k j$ et $f_k(j) = i_k$ sont constant +Enfin, puisque $i =_k j$ et $f_k(j) = i_k$ sont constants et sont donc indépendants de $X^t$, on a \[ \pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0} @@ -85,6 +85,6 @@ $(\frac{1}{2^l},\dots,\frac{1}{2^l}) = (\frac{1}{2^l},\dots,\frac{1}{2^l})M$ et donc $\pi = (\frac{1}{2^l},\dots,\frac{1}{2^l})$. Il existe donc $q$ t.q. $|\pi^q- \pi| < \epsilon$. -Puisque $p(Y| K)$ est $p(X^q)$, la méthode est donc $\epsilon$-stego-secure +Puisque $p(Y| K)$ est $p(X^q)$, la méthode est donc $\epsilon$-stégo-sécure pour peu que l'adapteur de stratégie soit uniformément distribué. \end{proof} diff --git a/annexePreuveMarquagefldblement.tex b/annexePreuveMarquagefldblement.tex index 2c7c1e1..a56ddc2 100644 --- a/annexePreuveMarquagefldblement.tex +++ b/annexePreuveMarquagefldblement.tex @@ -16,7 +16,7 @@ x_i \oplus x_{i-1} \textrm{ si $i$ est pair} Prouvons que la matrice de Markov associée est doublement stochastique par induction sur la longueur $l$. Pour $l=1$ et $l=2$ la preuve est évidente. -Considérons que le résulat est établi jusqu'à $l=2k$ avec $k \in \Nats$. +Considérons que le résultat est établi jusqu'à $l=2k$ avec $k \in \Nats$. On montre d'abord que la double stochasticité est établie pour $l=2k+1$. En suivant les notations introduites à la section~\ref{anx:sccg}, soit @@ -31,7 +31,7 @@ $(x_1,\dots,x_{2k},1) \to (x_1,\dots,x_{2k},0)$. Dans $\textsc{giu}(f_{2k+1})$, deux sortes d'arcs pointent vers $(x_1,\dots,x_{2k},0)$. Ceux qui sont de la forme $(y_1,\dots,y_{2k},0)$, où un seul des $y_i$ est différent de $x_i$, et leur nombre est celui des arcs qui pointent vers $(x_1,\dots,x_{2k})$ dans $\textsc{giu}(f_{2k})$. -L'arc $(x_1,\dots,x_{2k},0) \to (x_1,\dots,x_{2k},0)$ qui existe d'après la définition de $f_l$ +L'arc $(x_1,\dots,x_{2k},0) \to (x_1,\dots,x_{2k},0)$ qui existe d'après la définition de $f_l$. De même pour le nombre d'arcs dont l'extrémité est de la forme $(x_1,\dots,x_{2k},1)$. Par hypothèse d'induction, la chaîne de Markov associée à $\textsc{giu}(f_{2k})$ est doublement stochastique. @@ -40,22 +40,22 @@ Ainsi tous les sommets $(x_1,\dots,x_{2k})$ ont le même nombre d'arcs entrants Montrons à présent la double stochasticité pour $l=2k+2$. La fonction $f_l$ est définie par $f_l(x)= (\overline{x_1},x_2 \oplus x_{1},\dots,\overline{x_{2k+1}},x_{2k+2} \oplus x_{2k+1})$. On se concentre sur $\textsc{giu}(f_{2k+2})^0$ et $\textsc{giu}(f_{2k+2})^1$ qui sont isomorphes à $\textsc{giu}(f_{2k+1})$. -Parmi les configurations de $\Bool^{2k+2}$, seuls quatre suffixes de longueur 2 peuvent appraître: +Parmi les configurations de $\Bool^{2k+2}$, seuls quatre suffixes de longueur 2 peuvent apparaître: $00$, $10$, $11$ et $01$. Puisque $f_{2k+2}(\dots,0,0)_{2k+2}=0$, $f_{2k+2}(\dots,1,0)_{2k+2}=1$, -$f_{2k+2}(\dots,1,1)_{2k+2}=0$ et $f_{2k+2}(\dots,0,1)_{2k+2}=1$, le nombre d'arcs dont les extrémités est +$f_{2k+2}(\dots,1,1)_{2k+2}=0$ et $f_{2k+2}(\dots,0,1)_{2k+2}=1$, le nombre d'arcs dont les extrémités sont \begin{itemize} \item $(x_1,\dots,x_{2k},0,0)$ est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},0)$ dans $\textsc{giu}(f_{2k+1})$ - auquel on ajoute 1 (une boucle autours des configurations $(x_1,\dots,x_{2k},0,0)$); + auquel on ajoute 1 (une boucle autour des configurations $(x_1,\dots,x_{2k},0,0)$); \item $(x_1,\dots,x_{2k},1,0)$ est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ auquel on ajoute 1 (l'arc entre les configurations $(x_1,\dots,x_{2k},1,1)$ et les configurations $(x_1,\dots,x_{2k},1,0)$); \item $(x_1,\dots,x_{2k},0,1)$ est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ - auquel on ajoute 1 (une boucle autours des configurations $(x_1,\dots,x_{2k},0,1)$); + auquel on ajoute 1 (une boucle autour des configurations $(x_1,\dots,x_{2k},0,1)$); \item $(x_1,\dots,x_{2k},1,1)$ est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},1)$ in $\textsc{giu}(f_{2k+1})$ auquel on ajoute 1 (l'arc entre les configurations diff --git a/annexePreuveMixage.tex b/annexePreuveMixage.tex index 8132c68..71c1c8e 100644 --- a/annexePreuveMixage.tex +++ b/annexePreuveMixage.tex @@ -8,28 +8,28 @@ s'il existe un chemin de longueur $\alpha$ \class{q}. \begin{lemma} - Il existe un processus de renommage qui effecte un nouvel identifiant aux - élément $i\in$ \class{p} et $j \in$ \class{q} tel que + Il existe un processus de renommage qui affecte un nouvel identifiant aux + éléments $i\in$ \class{p} et $j \in$ \class{q} tel que $i \le j$ si et seulement si \class{p} $\preceq$ \class{q}. \begin{proof} - Tout d'abord, soit \class{p_1}, \ldots, \class{p_l} des classes + Tout d'abord, soient \class{p_1}, \ldots, \class{p_l} des classes contenant respectivement les éléments $n_1$,\ldots, $n_l$ qui ne dépendent d'aucune autre classe. Les éléments de \class{p_1} sont renommés par $1$, \ldots, $n_1$, - les elements de \class{p_i}, $2 \le i \le l$ sont renommés par + les éléments de \class{p_i}, $2 \le i \le l$ sont renommés par $1+ \Sigma_{k=1}^{i-1} n_k$, \ldots, $\Sigma_{k=1}^{i} n_k$. On considère maintenant les classes \class{p_1}, \ldots, \class{p_{l'}} dont les éléments ont été renommés et soit - $m$ le plus grand indice des elements de \class{p_1}, \ldots, + $m$ le plus grand indice des éléments de \class{p_1}, \ldots, \class{p_{l'}}. Soit une autre classe \class{p} qui dépend exclusivement d'une classe - \class{p_i}, $1 \le i \le l'$ et qui contient $k$ elements. + \class{p_i}, $1 \le i \le l'$ et qui contient $k$ éléments. Les éléments de \class{p} sont renommés par $m+1$, \ldots, $m+k$. Ce processus a été appliqué sur $l'+1$ classes. Il se termine - puisqu'il diminue le nombre d'elements auquel il reste + puisqu'il diminue le nombre d'éléments auquel il reste à affecter un numéro. Il reste à montrer que cette méthode de renommage vérifie la propriété @@ -41,7 +41,7 @@ s'il existe un chemin de longueur $\alpha$ dépend immédiatement de \class{p}, \textit{i.e.} le chemin le plus long entre les éléments de \class{p} et les - elements de \class{q} est de longueur 1. + éléments de \class{q} est de longueur 1. En raison de la méthode renommage, chaque numéro d'élément \class{q} est plus grand que tous ceux de \class{p} et la preuve est établie. @@ -81,20 +81,20 @@ On peut remarquer que ce processus de renommage est inspiré des \emph{graphes fini d'itérations. %pseudo periods. % [[JFC : borner m1/n1]]. Ainsi toutes les \emph{classes sources} (indépendantes de toutes les autres classes) vont aussi converger - dans le mode mixe. - On peut ainsi supposer que le mode d'itération mixe avec délais + dans le mode mixte. + On peut ainsi supposer que le mode d'itération mixte avec délais uniformes fait converger les classes \class{b_1}, \ldots, \class{b_k} en un temps $t_k$. Par construction, la classe \class{b_{k+1}} dépend uniquement de certaines classes de \class{b_1}, \ldots, \class{b_k} et éventuellement d'elle-même. - Il existe un nombre d'iteration suffisamment grand - $t_0$ tel que $D^{t_0}_{p_{k+1}p_j}$ est suppérieur ou égal à $t_k$ + Il existe un nombre d'itérations suffisamment grand + $t_0$ tel que $D^{t_0}_{p_{k+1}p_j}$ est supérieur ou égal à $t_k$ pour chaque $p_{k+1} \in$ \class{b_{k+1}} et $p_j \in$ \class{b_j}, $1 \le j \le k$. Il ne reste donc que des itérations synchrones entre les - elements of \class{b_{k+1}} en démarant dans des configurations + éléments de \class{b_{k+1}} en démarrant dans des configurations où tous les éléments de \class{b_j}, $1 \le j \le k$, ont des valeurs constantes. D'après les hypothèses du théorème, cela converge. diff --git a/annexePreuveStopping.tex b/annexePreuveStopping.tex index 5b77e95..75d05e4 100644 --- a/annexePreuveStopping.tex +++ b/annexePreuveStopping.tex @@ -46,7 +46,7 @@ En d'autres mots, $E$ est l'ensemble des tous les arcs du ${\mathsf{N}}$-cube. Soit $h: \Bool^{\mathsf{N}} \to [{\mathsf{N}}]$ qui mémorise pour chaque n{\oe}ud $X \in \Bool^{\mathsf{N}}$ quel -arc est supprimée à partir du cycle hamiltonien, +arc est supprimé à partir du cycle hamiltonien, \textit{i.e.} quel bit dans $[{\mathsf{N}} ]$ ne peut pas être inversé. @@ -97,8 +97,8 @@ $\ov{h}^{-1}(X)\oplus X = 0^{{\mathsf{N}}-k}10^{k-1}$. Supposons $h(X) = h(\ov{h}^{-1}(X))$. Dans un tel cas, $h(X) =k$. Par définition $\ov{h}$, $(X, \ov{h}(X)) \in E $ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1} = 0^{{\mathsf{N}}-k}10^{k-1}$. -Ainsi $\ov{h}(X)= \ov{h}^{-1}(X)$, ce qui entraine $\ov{h}(\ov{h}(X))= X$ et -qui contredit le fiat que $\ov{h}$ est anti-involutive. +Ainsi $\ov{h}(X)= \ov{h}^{-1}(X)$, ce qui entraîne $\ov{h}(\ov{h}(X))= X$ et +qui contredit le fait que $\ov{h}$ est anti-involutive. \end{proof} Soit $Z$ une variable aléatoire suivant une distribution uniforme sur @@ -108,7 +108,7 @@ Pour $X\in \Bool^{\mathsf{N}}$, on définit avec $Z=(i,b)$, \left\{ \begin{array}{ll} f(X,Z)=X\oplus (0^{{\mathsf{N}}-i}10^{i-1}) & \text{ si } b=1 \text{ et } i\neq h(X),\\ -f(X,Z)=X& \text{otherwise.} +f(X,Z)=X& \text{sinon.} \end{array}\right. \] @@ -121,13 +121,13 @@ X_t= f(X_{t-1},Z_t). Un entier $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ est \emph{équitable} - au temps $t$ s'il existe $0\leq j f_{\mathsf{N}}(\overline{x}^{\mathsf{N}})$, et donc $x_{\mathsf{N}}=0\neq f_{\mathsf{N}}(x)$ et $\overline{x}^{\mathsf{N}}_{\mathsf{N}}=1\neq f_{\mathsf{N}}(\overline{x}^{\mathsf{N}})$; diff --git a/chaosANN.tex b/chaosANN.tex index 89ac939..a818675 100644 --- a/chaosANN.tex +++ b/chaosANN.tex @@ -12,7 +12,7 @@ leur comportement imprévisible et proche de l'aléa. Les réseaux de neurones chaotiques peuvent être conçus selon plusieurs principes. Des neurones modifiant leur état en suivant une fonction non -linéaire son par exemple appelés neurones chaotiques~\cite{Crook2007267}. +linéaire sont par exemple appelés neurones chaotiques~\cite{Crook2007267}. L'architecture de réseaux de neurones de type Perceptron multi-couches (MLP) n'itèrent quant à eux, pas nécessairement de fonctions chaotiques. Il a cependant été démontré que ce sont des approximateurs @@ -28,7 +28,7 @@ fonctions chaotiques. Ces réseaux de neurones partagent le fait qu'ils sont qualifiés de ``chaotiques'' sous prétexte qu'ils embarquent une fonction de ce type -et ce sans aucune preuve rigoureuse ne soit fournie. +et ce sans qu'aucune preuve rigoureuse ne soit fournie. Ce chapitre caractérise la classe des réseaux de neurones MLP chaotiques. Il s'intéresse ensuite à l'étude de prévisibilité de systèmes dynamiques @@ -39,7 +39,7 @@ chaotique selon Devanay. La section~\ref{S3} présente l'approche duale de vérification si un réseau de neurones est chaotique ou non. La section~\ref{sec:ann:approx} s'intéresse à étudier pratiquement si un réseau de -neurones peut approximer des itération unaires chaotiques. Ces itérations +neurones peut approximer des itérations unaires chaotiques. Ces itérations étant obtenues à partir de fonctions issues de la démarche détaillée dans le chapitre précédent. Ce travail a été publié dans~\cite{bcgs12:ij}. @@ -58,7 +58,7 @@ Plus précisément, pour chaque entrée $(x,s) \in \mathds{B}^{\mathsf{N}} \times [{\mathsf{N}}]$, la couche de sortie doit générer $F_{f_u}(x,s)$. On peut ainsi lier la couche de sortie avec celle d'entrée pour représenter -les dépendance entre deux itérations successives. +les dépendances entre deux itérations successives. On obtient une réseau de neurones dont le comportement est le suivant (voir Figure.~\ref{Fig:perceptron}): @@ -68,8 +68,8 @@ On obtient une réseau de neurones dont le comportement est le suivant et calcule le vecteur de sortie $x^1=F_{f_u}\left(x^0,S^0\right)$. Ce vecteur est publié comme une sortie et est aussi retourné sur la couche d'entrée - à travers les liens de retours. -\item Lorsque le réseau est activé à la $t^{th}$ itération, l'état du + à travers les liens de retour. +\item Lorsque le réseau est activé à la $t^{\textrm{ème}}$ itération, l'état du système $x^t \in \mathds{B}^{\mathsf{N}}$ reçu depuis la couche de sortie ainsi que le premier terme de la séquence $(S^t)^{t \in \Nats}$ (\textit{i.e.}, $S^0 \in [{\mathsf{N}}]$) servent à construire le nouveau vecteur de sortie. @@ -82,7 +82,7 @@ On obtient une réseau de neurones dont le comportement est le suivant \begin{figure} \centering \includegraphics[scale=0.625]{images/perceptron} - \caption{Un Perceptron équivalent aux itérations unitaires} + \caption{Un Perceptron équivalent aux itérations unaires} \label{Fig:perceptron} \end{figure} @@ -91,7 +91,7 @@ initial est composé de $x^0~\in~\mathds{B}^{\mathsf{N}}$ et d'une séquence $(S^t)^{t \in \Nats}$, alors la séquence contenant les vecteurs successifs publiés $\left(x^t\right)^{t \in \mathds{N}^{\ast}}$ est exactement celle produite par les itérations unaires décrites à la section~\ref{sec:TIPE12}. -Mathématiquement, cela signifie que si on utilise les mêmes vecteurs d'entrées +Mathématiquement, cela signifie que si on utilise les mêmes vecteurs d'entrée les deux approches génèrent successivement les mêmes sorties. En d'autres termes ce réseau de neurones modélise le comportement de $G_{f_u}$, dont les itérations sont chaotiques sur $\mathcal{X}_u$. @@ -140,10 +140,10 @@ $f_j\left(x_1,x_2,\dots,x_{\mathsf{N}}\right) = F\left(\left(x_1,x_2,\dots,x_{\mathsf{N}}\right),j\right)$. Si ce réseau de neurones est initialisé avec $\left(x_1^0,\dots,x_{\mathsf{N}}^0\right)$ et $S \in [{\mathsf{N}}]^{\mathds{N}}$, -il produit exactement les même sorties que les itérations de $F_{f_u}$ avec une +il produit exactement les mêmes sorties que les itérations de $F_{f_u}$ avec une condition initiale $\left((x_1^0,\dots, x_{\mathsf{N}}^0),S\right) \in \mathds{B}^{\mathsf{N}} \times [{\mathsf{N}}]^{\mathds{N}}$. Les itérations de $F_{f_u}$ -sont donc un modèle formel de cette classe de réseau de neurones. +sont donc un modèle formel de cette classe de réseaux de neurones. Pour vérifier si un de ces représentants est chaotique, il suffit ainsi de vérifier si le graphe d'itérations $\textsc{giu}(f)$ est fortement connexe. @@ -162,12 +162,12 @@ qui approximerait les itérations de la fonction $G_{f_u}$ comme définie à l'équation~(\ref{eq:sch:unaire}). Sans perte de généralité, on considère dans ce qui suit une instance -de de fonction à quatre éléments. + de fonction à quatre éléments. \subsection{Construction du réseau} \label{section:translation} -On considère par exemple les deux fonctions $f$ and $g$ de $\Bool^4$ +On considère par exemple les deux fonctions $f$ et $g$ de $\Bool^4$ dans $\Bool^4$ définies par: \begin{eqnarray*} @@ -197,7 +197,7 @@ Dans le premier cas, on considère une entrée booléenne par élément tandis que dans le second cas, les configurations sont mémorisées comme des entiers naturels. Dans ce dernier cas, une approche naïve pourrait consister à attribuer à chaque configuration de $\Bool^{\mathsf{N}}$ -l'entier naturel naturel correspondant. +l'entier naturel correspondant. Cependant, une telle représentation rapproche arbitrairement des configurations diamétralement opposées dans le ${\mathsf{N}}$-cube comme une puissance de @@ -224,7 +224,7 @@ Les sorties (stratégies et configurations) sont mémorisées selon les mêmes règles. Concentrons nous sur la complexité du problème. -Chaque entrée, de l'entrée-sortie de l'outil est un triplet +Chaque entrée de l'entrée-sortie de l'outil est un triplet composé d'une configuration $x$, d'un extrait $S$ de la stratégie à itérer de taille $l$, $2 \le l \le k$ et d'un nombre $m \in [l-1]$ d'itérations à exécuter. Il y a $2^{\mathsf{N}}$ configurations $x$ et ${\mathsf{N}}^l$ stratégies de @@ -241,7 +241,7 @@ donc \dfrac{(k-1)\times {\mathsf{N}}^{k+1}}{{\mathsf{N}}-1} - \dfrac{{\mathsf{N}}^{k+1}-{\mathsf{N}}^2}{({\mathsf{N}}-1)^2} \enspace . \nonumber \end{equation} \noindent -Ainsi le nombre de paire d'entrée-sortie pour les réseaux de neurones considérés +Ainsi le nombre de paires d'entrée-sortie pour les réseaux de neurones considérés est $$ 2^{\mathsf{N}} \times \left(\dfrac{(k-1)\times {\mathsf{N}}^{k+1}}{{\mathsf{N}}-1} - \dfrac{{\mathsf{N}}^{k+1}-{\mathsf{N}}^2}{({\mathsf{N}}-1)^2}\right) \enspace . @@ -259,8 +259,9 @@ ont montré qu'un MLP pouvait apprendre la dynamique du circuit de Chua. Ce réseau avec rétropropagation est composé de deux couches et entraîné à l'aide d'une propagation arrière Bayesienne. -Le choix de l'architecture du réseau ainsi que de la méthode d'apprentissage -ont été détaillé dans~\cite{bcgs12:ij}. +Les choix de l'architecture de réseau ainsi que ceux concernant les + méthodes d'apprentissage +ont été détaillés dans~\cite{bcgs12:ij}. En pratique, nous avons considéré des configurations de quatre éléments booléens et une stratégie fixe de longueur 3. @@ -366,8 +367,8 @@ apprendre le comportement de la stratégie. Les résultats concernant le second codage (\textit{i.e.}, avec les codes de Gray) sont synthétisés dans le tableau~\ref{tab2}. On constate -que le réseau apprend cinq fois mieux les comportement non chaotiques -que ceux qui le sont. Ceci est est illustré au travers des +que le réseau apprend cinq fois mieux les comportements non chaotiques +que ceux qui le sont. Ceci est illustré au travers des figures~\ref{Fig:chaotic_predictions} et~\ref{Fig:non-chaotic_predictions}. De plus, comme dans le codage précédent, les stratégies ne peuvent pas être prédites. @@ -417,7 +418,7 @@ Nous avons enfin montré en pratique qu'il est difficile pour un réseau de neurones d'apprendre le comportement global d'itérations chaotiques. Comme il est difficile (voir impossible) d'apprendre le comportement -de telles fonction, il paraît naturelle de savoir si celles ci peuvent être +de telles fonctions, il paraît naturel de savoir si celles ci peuvent être utilisées pour générer des nombres pseudo aléatoires, ce que propose la partie suivante. diff --git a/conclusion.tex b/conclusion.tex index e2eac3e..98fcbc5 100644 --- a/conclusion.tex +++ b/conclusion.tex @@ -37,24 +37,25 @@ itérations. Elle est présentée au chapitre~\ref{chap:PRNG:gray}. Ces méthodes ont permis d'étendre à l'infini la classe des fonctions dont les itérations sont chaotiques. -Nous de plus entrepris d'étudier ces itérations et plus particulièrement leur +Nous avons aussi +entrepris d'étudier ces itérations et plus particulièrement leur apprentissage par un réseau de neurones. Nous avons notamment pu contribuer à montrer pratiquement qu'il est très difficile (voir impossible) de les prédire à l'aide d'outils d'intelligence artificielle (chapitre~\ref{chp:ANN}). -Avec la production d'une grande collection de fonctions à itérations chaotiques, -Nous avons donc proposé de répondre à la question suivante: comment engendrer des fonctions +Avec la production d'une grande collection de fonctions à itérations chaotiques, nous avons donc proposé de répondre à la question suivante: comment engendrer des fonctions dont les itérations vont produire des nombres simulant correctement l'aléa. En d'autres termes, quelles fonctions peuvent être embarquées dans un PRNG? Nous avons d'abord caractérisé les fonctions dont les itérations produisent des nombres selon une distribution uniforme (chapitre~\ref{chap:PRNG:chao}). Pour cela il a fallu réécrire l'algorithme de génération comme une marche aléatoire dans une partie du $\mathsf{N}$-cube, -de se ramener à une chaîne de Markov puis d'utiliser la théorie élaborée sur ce sujet +se ramener ensuite à une chaîne de Markov puis enfin +utiliser la théorie élaborée sur ce sujet pour conclure (chapitre~\ref{chap:PRNG:gray}). Parmi les fonctions retenues, celles issues de la suppression -d'un cycle hamiltonien dans un $\mathsf{N}$ ont retenu notre attention. +d'un cycle hamiltonien dans un $\mathsf{N}$-cube ont retenu notre attention. Nous nous sommes aussi attaché à montrer l'importance de l'équilibrage du cycle hamiltonien à enlever (chapitre~\ref{chap:PRNG:gray}). Nous avons de plus entrepris dans ce chapitre @@ -121,7 +122,7 @@ Nous avons fait sauter un premier verrou en proposant une méthode déterministe de Robinson-Cohn. Il est apparu récemment des algorithmes permettant d'obtenir des codes de Gray localement équilibrés, c.-à-d. où la longueur du plus grand nombre d'étapes entre deux changements d'un même bit est aussi petite que possible. -Dans tous les cas, aucun des ces codes n'est globalement équilibré ni même presque équilibré. +Dans tous les cas, aucun de ces codes n'est globalement équilibré ni même presque équilibré. Cette double propriété serait cependant très intéressante aussi bien théoriquement que pratiquement pour nos générateurs. Un second verrou consistera à adapter ces algorithmes pour proposer des codes possédant les diff --git a/intro.tex b/intro.tex index 23fb304..d2bbf98 100644 --- a/intro.tex +++ b/intro.tex @@ -23,8 +23,8 @@ Ces réseaux particuliers sont qualifiés de \emph{réseaux booléens}. Soit ${\mathsf{N}}$ un entier naturel représentant le nombre -d'éléments étudiés (le nombre bits qu'un générateur veut engendrer, -le nombre de pixel que l'on veut modifier\ldots) un réseau booléen est +d'éléments étudiés (le nombre de bits qu'un générateur veut engendrer, +le nombre de pixels que l'on veut modifier\ldots) un réseau booléen est défini à partir d'une fonction booléenne $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$ et un mode de mise à jour. A chaque étape, on peut intuitivement ne modifier qu'une partie des @@ -33,10 +33,10 @@ En fonction des éléments qui sont susceptibles d'être modifiés à chaque ét on peut se poser les questions de savoir si le réseau atteint un point fixe (et qu'il peut donc converger) ou s'il possède des attracteurs cycliques (et qu'il diverge donc). -Détecter la convergence ou son contraire peut se faire \textit{ a priori} dans -certain cas. En effet, de nombreux travaux ont énoncé des conditions +Détecter la convergence ou son contraire peut se faire \textit{a priori} dans +certains cas. En effet, de nombreux travaux ont énoncé des conditions suffisantes sur les réseaux booléens garantissant leur convergence -ou leur divergence . Lorsqu'aucune d'entre elle ne s'applique, on peut penser +ou leur divergence. Lorsqu'aucune d'entre elles ne s'applique, on peut penser à étendre ces résultats théoriques et compléter ceci par des simulations. Lorsque la convergence est pratiquement observée, il reste à vérifier que celle-ci est indépendante du choix des parties à modifier, par exemple. @@ -47,11 +47,11 @@ Une fonction qui admet un attracteur cyclique égal à l'ensemble des sommets diverge. Admet-il cependant un comportement chaotique? Les théories mathématiques du chaos ont énoncé des critères permettant de décider si une fonction est chaotique ou non, et plus récemment -si certains réseaux booléens étaient l'étaient. Se pose légitimement -la question de savoir si cette caractérisation s'étend quelque soient +si certains réseaux booléens l'étaient. Se pose légitimement +la question de savoir si cette caractérisation s'étend quelques soient les parties modifiées à chaque étape. Naturellement, ceci n'a un sens pratique que si le nombre de réseaux booléens qui possèdent cette -caractéristique est suffisamment grand et que l'on sache engendrer +caractéristique est suffisamment grand et que l'on sait engendrer algorithmiquement de tels réseaux. Les liens entre chaos et aléas sont certes intuitifs, mais sont-ils suffisants @@ -68,21 +68,22 @@ d'effectuer pour s'approcher suffisamment de celle-ci? Les liens entre chaos et marquage d'information sont aussi faciles à établir: de tout média marqué même attaqué, la marque doit pouvoir être extraite. -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 +Cette propriété du marquage est proche en effet de celle de régularité +des opérateurs chaotiques. Il est alors naturel d'envisager exploiter les fonctions chaotiques extraites dans ce contexte et donc de modifier certains bits d'un média pour y insérer de l'information: la marque. -Les compétences acquise dans l'étude des algorithme d'insertion d'une marque +Les compétences acquises dans l'étude des algorithmes d'insertion d'une marque 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 cette fois l'imperceptibilité et non plus la robustesse. Ainsi, tandis que l'idée principale était d'étaler le message sur un ensemble conséquent -de pixels pour adresser la robustesse, il s'agit ici de sélectionner finement +de pixels pour garantir la robustesse, il s'agit ici de sélectionner finement ceux dont les modifications seraient le moins perceptibles possible. On pense immédiatement à insérer ces messages dans les pixels contenant les zones les plus perturbées. -Les outils mathématiques d'analyse permettant d'identifier les lignes niveaux -pour ensuite voir lesquelles sont les moins régulières, les plus perturbées +Les outils mathématiques d'analyse permettant d'identifier les lignes de niveaux +pour ensuite voir lesquelles sont les moins régulières (les plus perturbées) sont le gradient et la matrice Hessienne. Cependant, ces modèles d'analyse ne sont définis que pour des fonctions de $\R^n$ dans $\R$. Se pose alors la question sur la possibilité de les adapter au cadre discret @@ -96,7 +97,7 @@ Ce mémoire est organisé en quatre parties. La première partie sur les réseaux discrets. Dans celle-ci, le chapitre~\ref{chap:sdd} formalise la notion de réseaux booléens et leurs modes opératoires. On y définit notamment un nouveau mode opératoire -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. +assurant la convergence et ce en un temps réduit. 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. Le chapitre~\ref{chap:promela} montre comment nous avons développé une démarche de preuve automatique de convergence de réseaux discrets. La démarche est @@ -112,7 +113,7 @@ démontré, propose un algorithme permettant de générer des fonctions posséda cette caractéristique. Les itérations unaires de telles fonctions étant chaotiques, nous avons étudié -au chapitre~\ref{chp:ANN} la possibilité de les faire apprendre par un réseau de neurones, particulièrement un perceptron multi-couches. +au chapitre~\ref{chp:ANN} la possibilité de les faire apprendre par un réseau de neurones, plus précisement par un perceptron multi-couches. Le titre de la troisième partie donne une idée de la conclusion de cette étude puisqu'on y étudie une famille PRNG construite à partir de fonctions @@ -121,18 +122,18 @@ Plus précisément, le chapitre~\ref{chap:PRNG:chao} caractérise les PRNG construits à partir de réseaux booléens qui sont chaotiques en donnant des conditions suffisantes sur la fonction à itérer. Le chapitre~\ref{chap:PRNG:gray} s'intéresse donc à générer -ce type de fonction de manière autrement plus efficaces qu'à partir de +ce type de fonction de manière autrement plus efficace qu'à partir de la méthode décrite au chapitre~\ref{chap:carachaos}. On y présente aussi un majorant du nombre d'itérations à effectuer pour obtenir une distribution uniforme. Comme annoncé dans les motivations à ce travail, les itérations chaotiques -peuvent s'appliquer à marquage de média et plus généralement +peuvent s'appliquer auz marquage de média et plus généralement au masquage d'information. C'est l'objectif de la quatrième partie. Dans le premier chapitre de celle-ci (chapitre~\ref{chap:watermarking}), nous formalisons le processus de marquage d'information. Grâce à cette formalisation, -nous pouvons étudier des propriétés de stego securité et chaos sécurité. +nous pouvons étudier des propriétés de stégo-securité et chaos-sécurité. Les deux chapitres suivants (chapitre~\ref{chap:watermarking:pdf} et chapitre~\ref{chap:stabylo}) sont une parenthèse @@ -148,10 +149,10 @@ de niveau les moins régulières. Une conclusion et des perspectives sont données en dernière partie. -\section*{Publications issues des travaux de recherche post doctorale} +\section*{Publications en tant qu'enseignant-chercheur} Le tableau de la figure~\ref{fig:bilan} donné -ci dessous synthétise les références auxquelles j'ai participées -depusi que je suis au DISC. +ci dessous synthétise les références auxquelles j'ai participé +depuis mon intégration en tant qu'enseignant chercheur. \begin{figure}[h] \begin{center} diff --git a/main.tex b/main.tex index cac65e9..ceebcde 100644 --- a/main.tex +++ b/main.tex @@ -56,25 +56,72 @@ %%-------------------- %% Set the University where HDR was made -\hdrpreparedin{Université de Technologie de Belfort-Montbéliard} +\hdrpreparedin{l'Université de Franche-Comté} + %%-------------------- %% Set the English abstract -%\hdrabstract[english]{This is the abstract in English} +\hdrabstract[english]{ +Thanks to its conciseness, a discrete model may allow to reason with +problems that may not be handled without such a model. Discrete +dynamical systems (DDS) belong this computer science area. In this +authorization to direct researches manuscript, we firstly present +contributions on convergence, convergence proof, and a new iteration +scheme of such systems. We further present contributions about +functions whose iterations can be chaotic. We particularly present a +set of methods leading to such functions. One of them built over Gray +codes allows to obtain a Markov chain that is doubly stochastic. This +last method permits to produce a large number of Pseudo-random Number +Generators (PRNG). Theoretical and practical contributions are +presented in this field. Information Hiding area has been +strengthened in this manuscript and some contributions are thus +presented. Instances of such algorithms are given according to +functions that can achieve a large robustness. Finally, we have +proposed an new method to build distortion functions +that can be embedded in information hiding schemes +with analysis gradient but expressed in a +discrete way.} %%-------------------- %% Set the English keywords. They only appear if %% there is an English abstract -%\hdrkeywords[english]{Keyword 1, Keyword 2} +\hdrkeywords[english]{discrete dynamical system, pseudo random number +generator, information hiding} %%-------------------- %% Set the French abstract -\hdrabstract[french]{Blabla blabla.} +\hdrabstract[french]{ +Grâce à leur concision, les modèle discrets permettent d'appréhender +des problèmes informatiques qui ne seraient parfois pas traitables +autrement. Les systèmes dynamiques discrets (SDD) s'intègrent dans +cette thématique. Dans cette habilitation, nous présenterons tout +d'abord des contributions concernant la convergence, la preuve de +convergence et un nouveau mode opératoire de tels systèmes. Nous +présenterons ensuite un ensemble de contributions autour des +fonctions dont les itérations peuvent être +chaotiques. Particulièrement, nous présentons plusieurs méthodes +permettant d'obtenir de telles fonctions, dont une basée sur les codes +de Gray, permettant d'obtenir en plus une chaîne de Markov doublement +stochastique. Cette dernière méthode nous a permis notamment +d'obtenir un grand ensemble de générateurs de nombres +pseudo-aléatoires (PRNG). Des contributions théoriques et pratiques +autour de ces PRNGs seront présentées. La thématique de masquage +d'information (déjà présente) a été renforcée et des contributions sur +ce sujet seront présentées. Des instances de ces algorithmes sont +formalisés en sélectionnant les fonctions à itérer pour garantir une +robustesse élevée. Finalement, nous montrons qu'on peut construire +de nouvelles fonctions de distorsion utilisables +en masquage d'information à l'aide de +méthodes d'analyse par gradient mais discret cette fois encore. + + +} %%-------------------- %% Set the French keywords. They only appear if %% there is an French abstract -%\hdrkeywords[french]{Mot-cl\'e 1, Mot-cl\'e 2} +\hdrkeywords[french]{systèmes dynamiques discrets, générateur de nombres +pseudo aléatoires, masquage d'information} %%-------------------- %% Change the layout and the style of the text of the "primary" abstract. @@ -102,7 +149,7 @@ %%-------------------- %% Change the speciality of the PhD thesis -%\Set{speciality}{Informatique} +\Set{speciality}{Informatique} %%-------------------- %% Change the institution @@ -195,9 +242,9 @@ dernières sections ont fait l'objet du rapport~\cite{BCVC10:ir}. Introduire de l'asynchronisme peut permettre de réduire le temps d'exécution global, mais peut aussi introduire de la divergence. -Dans ce chapitre, après avoir introduit les bases sur les réseaux bouléens, +Dans ce chapitre, après avoir introduit les bases sur les réseaux booléens, nous avons exposé comment construire un mode combinant les -avantage du synchronisme en terme de convergence avec les avantages +avantages du synchronisme en terme de convergence avec les avantages de l'asynchronisme en terme de vitesse de convergence. @@ -214,21 +261,21 @@ de l'asynchronisme en terme de vitesse de convergence. \part{Des systèmes dynamiques discrets au chaos} -\chapter[Caracterisation des systèmes - discrets chaotiques]{Caracterisation des systèmes +\chapter[Caractérisation des systèmes + discrets chaotiques]{Caractérisation des systèmes discrets chaotiques pour les schémas unaires et généralisés}\label{chap:carachaos} La suite de ce document se focalise sur des systèmes dynamiques discrets qui ne convergent pas. Parmi ceux-ci se trouvent ceux qui sont \og chaotiques\fg{}. La première section de ce chapitre rappelle ce que sont les systèmes -dynamiques chaotiques et leur caractéristiques. +dynamiques chaotiques et leurs caractéristiques. La section~\ref{sec:TIPE12}, qui est une reformulation de~\cite{guyeux10}, se focalise sur le schéma unaire. Elle est rappelée pour avoir un document se suffisant à lui-même. La section~\ref{sec:chaos:TSI} étend ceci au mode généralisé. Pour chacun de ces modes, une métrique est définie. Finalement, la section~\ref{sec:11FCT} -exhibe des conditions suffisantes premettant d'engendrer -des fonctions chaotiques seon le mode unaire. +exhibe des conditions suffisantes permettant d'engendrer +des fonctions chaotiques selon le mode unaire. Les sections~\ref{sec:TIPE12} et~\ref{sec:11FCT} ont été publiées dans~\cite{bcg11:ij,bcgr11:ip}. @@ -252,7 +299,7 @@ Ce chapitre a montré que les itérations unaires sont chaotiques si et seulement si le graphe $\textsc{giu}(f)$ est fortement connexe et que les itérations généralisées sont chaotiques si et seulement si le graphe $\textsc{gig}(f)$ est aussi fortement connexe. -On dispose ainsi à priori d'une collection infinie de fonctions chaotiques. +On dispose ainsi a priori d'une collection infinie de fonctions chaotiques. Le chapitre suivant s'intéresse à essayer de prédire le comportement de telles fonctions. @@ -282,10 +329,10 @@ de telles fonctions. \chapter{Une démarche de marquage de PDF}\label{chap:watermarking:pdf} \input{ahmad} -\chapter{Une démarches plus classique de dissimulation: STABYLO}\label{chap:stabylo} +\chapter[STABYLO] {Une démarche plus classique de dissimulation: STABYLO}\label{chap:stabylo} \input{stabylo} -\chapter{Schéma de stéganographie: les dérivées du second ordre}\label{chap:th:yousra} +\chapter[Stéganographie par dérivées secondes]{Schémas de stéganographie: les dérivées secondes}\label{chap:th:yousra} \input{stegoyousra} @@ -306,7 +353,7 @@ de telles fonctions. \chapter{Preuves sur les réseaux discrets} -\section{Convergence du mode mixe}\label{anx:mix} +\section{Convergence du mode mixte}\label{anx:mix} \input{annexePreuveMixage} @@ -348,7 +395,7 @@ de telles fonctions. \input{annexePreuveStopping} \chapter{Preuves sur le marquage de média}\label{anx:marquage} -\section{Le marquage est $\epsilon$-sego-secure} +\section{Le marquage est $\epsilon$-stégo-sécure} \input{annexePreuveMarquagedhci} \section{Le mode $f_l$ est doublement stochastique}\label{anx:marquage:dblesto} diff --git a/mixage.tex b/mixage.tex index 4ee1171..4045262 100644 --- a/mixage.tex +++ b/mixage.tex @@ -50,11 +50,11 @@ et les quatre derniers éléments (15 est 01111). % strategy $s$, as in the synchronous mode. Dans le mode asynchrone, a chaque itération $t$, chaque composant peut mettre à jour son état en -fonction des dernières valeurs qu'il connaît des autre composants. +fonction des dernières valeurs qu'il connaît des autres composants. Obtenir ou non les valeurs les plus à jour dépend du temps de calcul et du temps d'acheminement de celles-ci. On parle de latence, de délai. -Formalisons le mode les itérations asynchrone. +Formalisons le mode des itérations asynchrone. Soit $x^0 =(x_1^0, \ldots, x_n^0)$ une configuration initiale. Soit $(D^{t})^{t \in \Nats}$ la suite de matrice de taille $n \times n$ dont chaque élément $D_{ij}^{t}$ représente la date (inférieure ou égale à $t$) @@ -155,7 +155,7 @@ le système peut infiniment boucler entre 11 et 3, entre 15 et 7. Comme les itérations unaires ne convergent pas pour certaines stratégies, les itérations asynchrones basées sur les même stratégies peuvent ne pas -converger aussi. Cependant, même si l'on considère que tous les composants +converger non plus. Cependant, même si l'on considère que tous les composants sont activés à chaque itération, c'est à dire si $s^t$ est constamment égal à $2^n-1$, le délai peut introduire de la divergence. On considère par exemple la matrice $D^t$ dont chaque élément vaut $t$ @@ -169,13 +169,13 @@ f_5(x^{t}) $$ \noindent sinon. En démarrant de $x^0=00011$, le système atteint $x^1 = 01011$ et boucle entre -ces deux configurations. Pour une même stratégies, les itérations +ces deux configurations. Pour une même stratégie, les itérations asynchrones divergent alors que les synchrones convergent. Les sections suivantes de ce chapitre montrent comment résoudre ce problème. -\subsection{Itérations Mixes} +\subsection{Itérations mixtes} Introduit dans~\cite{abcvs05} -le mode d'\emph{itérations mixes} combine synchronisme et asynchronisme. +le mode d'\emph{itérations mixtes} combine synchronisme et asynchronisme. Intuitivement, les n{\oe}uds qui pourraient introduire des cycles dans les itérations asynchrones sont regroupés. Les noeuds à l'intérieur de chaque groupe seront itérés de manière @@ -194,11 +194,11 @@ On peut facilement démontrer que la relation de synchronisation est une relation d'équivalence sur l'ensemble des éléments. On introduit quelques notations: par la suite \class{i} représente la classe d'équivalence de $i$ et $\mathcal{K}$ représente l'ensemble de toutes -les classe, \textit{i.e.}, -$\mathcal{K}=\{1,\ldots,n\}/\eqNode$. On peut définir les itérations mixes. +les classes, \textit{i.e.}, +$\mathcal{K}=\{1,\ldots,n\}/\eqNode$. On peut définir les itérations mixtes. -\begin{Def}[Itérations mixes] -Les itérations mixes d'un système discret suit l'équation \Equ{eq:async} où +\begin{Def}[Itérations mixtes] +Les itérations mixtes d'un système discret suivent l'équation \Equ{eq:async} où de plus $bin(s^t)[i]=bin(s^t)[j]$ et $D_{ij}^t=D_{ji}^t=t$ si $i \eqNode j$. \end{Def} @@ -210,8 +210,8 @@ des délais différents entre $p_0$ et $q$ et entre $p_1$ et $q$. Ainsi $p_1$ et $p_2$ sont distinguables même s'ils appartiennent à la même classe. Pour gommer cette distinction, on définit le mode suivant: -\begin{Def}[Itérations mixes avec delais uniformes] - Le mode mixe a des \emph{délais uniformes} si pour chaque +\begin{Def}[Itérations mixtes avec delais uniformes] + Le mode mixte a des \emph{délais uniformes} si pour chaque $t=0,1,\ldots$ et pour chaque paire de classes $(\class{p}, \class{q})$, il existe une constante $d^t_{pq}$ telle que la propriété suivante est établie: @@ -229,7 +229,7 @@ On a alors le théorème suivant. Soit une fonction $f$ possédant un unique point fixe $x^*$ et une stratégie pseudo périodique $s$. Si les itérations synchrones convergent vers $x^*$ pour cette stratégie, - alors les itérations mixes à délai uniforme convergent aussi vers $x^*$ + alors les itérations mixtes à délai uniforme convergent aussi vers $x^*$ pour cette stratégie. \end{theorem} @@ -240,7 +240,7 @@ La preuve de ce théorème est donnée en section~\ref{anx:mix}. \subsection{Durées de convergence} Cette section donne des bornes supérieures et inférieures des durées -globales de convergence pour les modes synchrones, mixes et asynchrones. +globales de convergence pour les modes synchrones, mixtes et asynchrones. Pour simplifier le discours, on considère que les itérations convergent en $I$ étapes dans le mode synchrone et que le graphe d'interaction ne contient qu'une seule composante connexe. @@ -259,7 +259,7 @@ Les notations utilisées sont les suivantes: de bits nécessaires pour représenter l'état courant du composant $i$ et est notée $\textit{cs}_i$; -\item [Temps de calcul] le composant $i$ a besoins de $\textit{cp}_i$ unités de temps +\item [Temps de calcul] le composant $i$ a besoin de $\textit{cp}_i$ unités de temps pour faire une mise à jour locale de son état; \item [Temps de communication] on utilise le modèle classique de communication $\beta+L\tau$ où $L$ est le nombre de bits transférés. @@ -289,7 +289,7 @@ graphe d'interaction, le temps global de convergence est \begin{xpl} Intuitivement la convergence se propage selon les dépendances internes au système: - un n{\oe}uds se stabilise lorsque ceux dont il dépend sont eux aussi stables. + un n{\oe}ud se stabilise lorsque ceux dont il dépend sont eux aussi stables. Cette stabilisation progressive est illustrée à la \Fig{fig:evalsync} qui représente des exécutions synchrones dans le cas d'une initialisation avec la valeur (00100). @@ -307,7 +307,7 @@ graphe d'interaction, le temps global de convergence est \begin{minipage}{1\textwidth} \includegraphics[scale=0.4]{eval_mixte} - \caption{Itérations mixes avec + \caption{Itérations mixtes avec \class{1} $=\{1,2\}$, \class{3} $=\{3\}$, \class{4} $=\{4,5\}$.} \label{fig:evalmixte} @@ -379,15 +379,15 @@ graphe d'interaction, le temps global de convergence est % \end{figure} % \end{xpl} -\subsection{le mode mixe} +\subsection{le mode mixte} \label{sec:evalmixed} On considère $|\mathcal{K}|$ classes de composants synchronisés. (comme donné en équation~(\ref{eq:I})). -Soit $I_k$ le nombre d'itérations suffisants pour que la classe +Soit $I_k$ le nombre d'itérations suffisant pour que la classe $\class{k} \in \mathcal{K}$ se stabilise -sachant toutes ses dépendances ont déjà convergé. +sachant que toutes ses dépendances ont déjà convergé. Ainsi $I$ vaut $\sum_{\class{k} \in \mathcal{K}} I_k$. La borne inférieure pour la durée de convergence des itérations asynchrones est \begin{equation} @@ -411,7 +411,7 @@ ascendants pour converger. On a dans ce cas: \end{equation} \begin{xpl} - Une exécution du mode mixe est donnée à la~\Fig{fig:evalmixte}. + Une exécution du mode mixte est donnée à la~\Fig{fig:evalmixte}. On peut constater que le temps d'exécution peut être plus petit que pour le mode synchrone. @@ -420,7 +420,7 @@ ascendants pour converger. On a dans ce cas: \subsection{Le mode unaire asynchrone} \label{sec:evalasync} En terme de durée de convergence, ce mode peut être vu comme un -cas particulier du mode mixe où toutes les classes sont des singletons. +cas particulier du mode mixte où toutes les classes sont des singletons. La borne minimale peut donc s'exprimer comme: \begin{equation} \label{eq:asynclow} diff --git a/modelchecking.tex b/modelchecking.tex index d9e626e..96a8586 100644 --- a/modelchecking.tex +++ b/modelchecking.tex @@ -1,15 +1,15 @@ L'étude de convergence de systèmes dynamiques discrets est simple à vérifier pratiquement pour le mode synchrone. Lorsqu'on introduit des stratégies -pseudo périodiques pour les modes unaires et généralisées, le problème +pseudo périodiques pour les modes unaires et généralisés, le problème se complexifie. C'est pire encore lorsqu'on traite des itérations asynchrones -et mixes prenant de plus en compte les délais. +et mixtes prenant de plus en compte les délais. Des méthodes de simulation basées sur des stratégies et des délais générés aléatoirement ont déjà été présentées~\cite{BM99,BCV02}. Cependant, comme ces implantations ne sont pas exhaustives, elles ne donnent un résultat formel que lorsqu'elles fournissent un contre-exemple. Lorsqu'elles exhibent une convergence, -cela ne permet que donner une intuition de convergence, pas une preuve. +cela ne permet que de donner une intuition de convergence, pas une preuve. Autant que nous sachions, aucune démarche de preuve formelle automatique de convergence n'a jamais été établie. Dans le travail théorique~\cite{Cha06}, Chandrasekaran a montré que les itérations asynchrones sont convergentes @@ -17,7 +17,7 @@ si et seulement si on peut construire une fonction de Lyaponov décroissante, ma automatique pour construire cette fonction. Un outil qui construirait automatiquement toutes -les transitons serait le bienvenu. +les transitions serait le bienvenu. Pour peu qu'on établisse la preuve de correction et de complétude de la démarche, la convergence du réseau discret ne reposerait alors que sur le verdict @@ -31,7 +31,7 @@ combinatoire, ces outils appliquent des méthodes d'ordre partiel, d'abstraction de quotientage selon une relation d'équivalence. Ce chapitre montre comment nous simulons -des réseaux discrets selon pour établir +des réseaux discrets pour établir formellement leur convergence (ou pas). Nous débutons par un exemple et faisons quelques rappels sur le langage PROMELA qui est le langage du model-checker @@ -98,8 +98,8 @@ Pour les modes unaires ou généralisés avec une stratégie pseudo périodique, on a des comportements qui dépendent de la configuration initiale: \begin{itemize} -\item initialisée avec 7, les itérations restent en 7; -\item initialisée avec 0, 2, 4 ou 6 les itérations convergent vers 2; +\item initialisées avec 7, les itérations restent en 7; +\item initialisées avec 0, 2, 4 ou 6 les itérations convergent vers 2; \item initialisées avec 1, 3 ou 5, les itérations convergent vers un des deux points fixes 2 ou 7. \end{itemize} @@ -155,12 +155,12 @@ déclarations de variables qui servent dans l'exemple de ce chapitre. Il définit: \begin{itemize} \item les constantes \verb+N+ et \verb+d_0+ qui précisent respectivement le nombre - ${\mathsf{N}}$ d'éléments et le délais maximum $\delta_0$; + ${\mathsf{N}}$ d'éléments et le délai maximum $\delta_0$; \item les deux tableaux (\verb+X+ et \verb+Xp+) de \verb+N+ variables booléennes; les cellules \verb+X[i]+ et \verb+Xp[i]+ sont associées à la variables $x_{i+1}$ d'un système dynamique discret; elles mémorisent les valeurs de $X_{i+1}$ respectivement avant et après sa mise à jour; -il suffit ainsi de comparer \verb+X+ et \verb+Xp+ pour constater si $x$ à changé ou pas; +il suffit ainsi de comparer \verb+X+ et \verb+Xp+ pour constater si $x$ a changé ou pas; \item le tableau \verb+mods+ contient les éléments qui doivent être modifiés lors de l'itération en cours; cela correspond naturellement à l'ensemble des éléments $s^t$; \item le type de données structurées \verb+vals+ et le tableau de tableaux @@ -186,9 +186,9 @@ Dans l'exemple précédent, on déclare successivement: \item un canal \verb+sent+ qui vise à mémoriser \verb+d_0+ messages de type \verb+bool+; le tableau nommé \verb+channels+ de \verb+N+*\verb+N+ éléments de type \verb+a_send+ est utilisé pour mémoriser les valeurs intermédiaires $x_j$; - Il permet donc de temporiser leur emploi par d'autres elements $i$. + Il permet donc de temporiser leur emploi par d'autres éléments $i$. \item les deux canaux \verb+unlock_elements_update+ et \verb+sync_mutex+ contenant -chacun un message booléen et utilisé ensuite comme des sémaphores. +chacun un message booléen et sont utilisés ensuite comme des sémaphores. \end{itemize} \end{xpl} @@ -432,7 +432,7 @@ inline F(){ \begin{enumerate} \item elle commence en mettant à jour la variable \texttt{X} avec les valeurs de \texttt{Xp} dans la fonction \texttt{update\_X},~\Fig{fig:spin:sauve} -\item elle mémorise dans \texttt{Xd} la valeurs disponible pour chaque élément grâce à la fonction \texttt{fetch\_values}; cette fonction est détaillée +\item elle mémorise dans \texttt{Xd} la valeur disponible pour chaque élément grâce à la fonction \texttt{fetch\_values}; cette fonction est détaillée dans la section suivante; \item une boucle %sur les \texttt{ar\_len} éléments qui peuvent être modifiés met à jour itérativement la valeur de $j$ (grâce à l'appel de fonction \texttt{f(j)}) @@ -458,8 +458,8 @@ dans la section suivante; Cette section montre comment les délais inhérents au mode asynchrone sont traduits dans le modèle PROMELA grâce à deux fonctions \verb+fetch_values+ et \verb+diffuse_values+. -Celles-ci sont données en {\sc Figure}~\ref{fig:val} et~\ref{fig:broadcast}, -qui récupèrent et diffusent respectivement les valeurs des elements. +Celles-ci sont données en {\sc Figure}~\ref{fig:val} et~\ref{fig:broadcast}. +Elles récupèrent et diffusent respectivement les valeurs des éléments. \begin{figure}[t] \begin{minipage}[h]{.475\linewidth} @@ -537,7 +537,7 @@ Il y a deux cas. \begin{itemize} \item puisque $i$ connaît sa dernière valeur (\textit{i.e.}, $D^t_{ii}$ est toujours $t$) \verb+Xd[i].v[i]+ est donc \verb+Xp[i]+; -\item sinon, il y a deux sous cas qui peuvent peuvent potentiellement modifier la valeur +\item sinon, il y a deux sous-cas qui peuvent peuvent potentiellement modifier la valeur que $j$ a de $i$ (et qui peuvent être choisies de manière aléatoire): \begin{itemize} \item depuis la perspective de $j$ la valeur de $i$ peut ne pas avoir changé ( @@ -602,7 +602,7 @@ de prouver la formule temporelle linéaire (LTL) suivante: \diamond (\Box \verb+Xp+ = \verb+X+) \label{eq:ltl:conv} \end{equation} -où les opérateur $\diamond$ et $\Box$ ont +où les opérateurs $\diamond$ et $\Box$ ont la sémantique usuelle, à savoir respectivement {\em éventuellement} et {\em toujours} dans les chemins suivants. On note que cette propriété, si elle est établie, garantit @@ -680,7 +680,7 @@ pour prouver formellement sa convergence universelle. On peut remarquer que SPIN n'impose l'équité faible qu'entre les process alors que les preuves des deux théorèmes précédentes reposent sur le fait que -celle-ci est établie dès qu'un choix indéterministe est effectué. +cette équité est établie dès qu'un choix indéterministe est effectué. Naïvement, on pourrait considérer comme hypothèse la formule suivante chaque fois qu'un choix indéterministe se produit entre $k$ événements respectivement notés $l_1$, \ldots $l_k$: @@ -764,7 +764,7 @@ pour établir un verdict. \begin{tabular}{|*{13}{c|}} \cline{2-13} \multicolumn{1}{c|}{ } - &\multicolumn{6}{|c|}{Mode Mixe} & \multicolumn{6}{|c|}{Seulement borné} \\ + &\multicolumn{6}{|c|}{Mode Mixte} & \multicolumn{6}{|c|}{Seulement borné} \\ \cline{2-13} \multicolumn{1}{c|}{ } &\multicolumn{3}{|c|}{Synchrones} & \multicolumn{3}{|c|}{Pseudo-Périodique} & @@ -863,12 +863,13 @@ l'approche. \label{sec:spin:concl} L'idée principale de ce chapitre est que l'on peut, -pour des réseaux bouléens à délais bornés de petite taille, obtenir +pour des réseaux booléens à délais bornés de petite taille, obtenir une preuve de la convergence ou de sa divergence et ce de manière automatique. L'idée principale est de traduire le réseau en PROMELA et de laisser le model checker établir la preuve. -Toute l'approche a été prouvée: le verdict rendu par a donc valeur de vérité. +Toute l'approche a été prouvée: le verdict rendu par l'approche +a donc valeur de vérité. L'approche a cependant ses limites et ne peut donc pas être apliquée qu'à des modèles simplifiés de programmes. La suite de ce travail consiste à se focaliser sur les systèmes qui ne diff --git a/oxford.tex b/oxford.tex index ebdc417..5cc17c0 100644 --- a/oxford.tex +++ b/oxford.tex @@ -51,7 +51,7 @@ dans lui même. de $\Nats$ dans l'ensemble des séquences d'entiers qui associe à chaque entier naturel $\mathsf{N}$ la suite - $S \in [\mathsf{N}@]^{\mathds{N}}$. + $S \in [\mathsf{N}]^{\mathds{N}}$. \end{Def} @@ -83,15 +83,15 @@ Ceci se fait à l'aide d'une fonction de signification. \begin{Def}[Fonction de signification ] Une \emph{fonction de signification } -est une fonction $u$ qui a toute +est une fonction $u$ qui à toute séquence finie de bit $x$ associe la séquence $(u^k(x))$ de taille $\mid x \mid$ à valeur dans les réels. Cette fonction peut dépendre du message $y$ à embarquer, ou non. \end{Def} Pour alléger le discours, par la suite, on notera $(u^k(x))$ pour $(u^k)$ -lorsque cela n'est pas ambiguë. -Il reste à partionner les bits de $x$ selon qu'ils sont +lorsque cela n'est pas ambigüe. +Il reste à partitionner les bits de $x$ selon qu'ils sont peu, moyennement ou très significatifs. \begin{Def}[Signification des bits]\label{def:msc,lsc} @@ -100,7 +100,7 @@ $m$ et $M$ deux réels t.q. $m < M$. Alors: $u_M$, $u_m$ et $u_p$ sont les vecteurs finis respectivement des \emph{bits les plus significatifs (MSBs)} de $x$, \emph{bits les moins significatifs (LSBs)} de $x$ -\emph{bits passifs} of $x$ définis par: +\emph{bits passifs} de $x$ définis par: \begin{eqnarray*} u_M &=& \left( k ~ \big|~ k \in \mathds{N} \textrm{ et } u^k \geqslant M \textrm{ et } k \le \mid x \mid \right) \\ @@ -130,7 +130,7 @@ avec La fonction qui associe $(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ pour chaque hôte $x$ est la \emph{fonction de décomposition}, plus tard notée $\textit{dec}(u,m,M)$ puisqu'elle est paramétrée par -$u$, $m$ and $M$. +$u$, $m$ et $M$. \end{Def} @@ -189,7 +189,7 @@ $f$ un mode, $\mathcal{S}$ un adapteur de stratégie, $x$ un hôte, $(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ -sont image par $\textit{dec}(u,m,M)$, +son image par $\textit{dec}(u,m,M)$, $q$ un entier naturel positif et $y$ un média numérique de taille $l=|u_m|$. @@ -216,7 +216,7 @@ La figure~\ref{fig:organigramme} synthétise la démarche. \centering %\includegraphics[width=8.5cm]{organigramme2.pdf} \includegraphics[width=8.5cm]{organigramme22} -\caption{The dhCI dissimulation scheme} +\caption{Le schéma de marquage dhCI} \label{fig:organigramme} \end{figure} @@ -227,20 +227,20 @@ La figure~\ref{fig:organigramme} synthétise la démarche. On caractérise d'abord ce qu'est un média marqué selon la méthode énoncée à la section précédente. On considère que l'on connaît -la marque à embarquer $y$, le support $x$ et que l'on a face à soit un média +la marque à embarquer $y$, le support $x$ et que l'on a face à soi un média $z$. \begin{Def}[Média marqué] -Soit $\textit{dec}(u,m,M)$ une fonction de décomposition +Soit $\textit{dec}(u,m,M)$ une fonction de décomposition, $f$ un mode, -$\mathcal{S}$ un adapteur de stratégie +$\mathcal{S}$ un adapteur de stratégie, $q$ un entier naturel strictement positif, $y$ un média digital et soit $(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ l'image par $\textit{dec}(u,m,M)$ du média $x$. Alors, $z$ est \emph{marqué} avec $y$ si l'image -par $\textit{dec}(u,m,M)$ of $z$ est +par $\textit{dec}(u,m,M)$ de $z$ est $(u_M,u_m,u_p,\phi_{M},\hat{y},\phi_{p})$, où $\hat{y}$ est le second membre de $G_{f_l}^q(S_y,\phi_{m})$. \end{Def} @@ -273,7 +273,7 @@ que l'algorithme de marquage dont le mode est la fonction négation est stégo-sécure. Un des intérêts de l'algorithme présenté ici est qu'il est paramétré par un mode. Lorsque celui-ci a les même propriétés que celles vues pour la création de PRNG (\textit{i.e.} graphe des itérations fortement connexes et matrice de Markov doublement -stochastique), on a un marquage qui peut être rendu stégo-sécure à $\varepsilon$ prêt, +stochastique), on a un marquage qui peut être rendu stégo-sécure à $\varepsilon$ près, ce que précise le théorème suivant. La preuve de ce théorème est donnée en annexes~\ref{anx:marquage}. @@ -326,8 +326,8 @@ x_i \oplus x_{i-1} \textrm{ si $i$ est pair} on peut déduire immédiatement du théorème~\ref{th:Adrien} (chap.~\ref{chap:carachaos}) que le graphe $\textsc{giu}(f_l)$ est fortement connexe. -La preuve de double-stochasiticité de la matrice associée -à $f_l$ est donnée en annexes~\ref{anx:marquage:dblesto}. +La preuve de double-stochasticité de la matrice associée +à $f_l$ est donnée en annexe~\ref{anx:marquage:dblesto}. On dispose ainsi d'un nouvel algorithme de marquage $\varepsilon$-stégo-sécure et chaos-sécure. @@ -350,7 +350,7 @@ la fonction de signification $u$ associe \item -1 si c'est un bit apparaissant dans la représentation binaire de la valeur d'un coefficient dont les coordonnées appartiennent à $\{(3,1),(2,2),(1,3)\}$ et qui est un des - des trois bits de poids faible de cette valeur, + trois bits de poids faible de cette valeur, \item 0 sinon. \end{itemize} Le choix de l'importance de chaque coefficient est défini grâce aux seuils @@ -387,13 +387,13 @@ Dans ce qui suit, {dwt}(neg), correspondant respectivement aux embarquements en fréquentiels dans les domaines DWT et DCT avec le mode de négation et celui issu de la fonction $f_l$ -détaillé à l'équation~\ref{eq:fqq}. +détaillée à l'équation~\ref{eq:fqq}. A chaque série d'expériences, un ensemble de 50 images est choisi aléatoirement de la base du concours BOSS~\cite{Boss10}. Chaque hôte est une image en $512\times 512$ en niveau de gris et la marque $y$ est une suite de 4096 bits. -La résistances à la robustesse est évaluée en appliquant successivement +La résistance à la robustesse est évaluée en appliquant successivement sur l'image marquée des attaques de découpage, de compression, de transformations géométriques. Si les différences entre $\hat{y}$ and $\varphi_m(z)$. @@ -473,19 +473,19 @@ Pour les deux modes dans le domaine DCT, la détection est optimale pour le seuil de 44\% (correspondant aux points (0.05, 0.18) et (0.05, 0.28)). On peut alors donner des intervalles de confiance pour les attaques évaluées. -L'approche est résistante à: +L'approche est résistante: \begin{itemize} -\item tous les découpages où le pourcentage est inférieur à 85\%; -\item les compression dont le ratio est supérieur à 82\% dans le domaine +\item à tous les découpages où le pourcentage est inférieur à 85\%; +\item aux compression dont le ratio est supérieur à 82\% dans le domaine DWT et 67\% dans celui des DCT; -\item les modifications du contraste lorsque le renforcement est dans +\item aux modifications du contraste lorsque le renforcement est dans $[0.76,1.2]$ dans le domaine DWT et $[0.96,1.05]$ dans le domaine DCT; -\item toutes les rotations dont l'angle est inférieur à 20 degrés dans le domaine DCT et +\item à toutes les rotations dont l'angle est inférieur à 20 degrés dans le domaine DCT et celles dont l'angle est inférieur à 13 degrés dans le domaine DWT. \end{itemize} -\section{Embarquons d'avantage qu'1 bit}\label{sec:watermarking:extension} +\section{Embarquons davantage qu'1 bit}\label{sec:watermarking:extension} L'algorithme présenté dans les sections précédentes ne permet de savoir, \textit{in fine}, que si l'image est marquée ou pas. Cet algorithme ne permet pas @@ -532,17 +532,17 @@ Pour chaque $(n,i,j) \in \begin{array}{l} x_i^n=\left\{ \begin{array}{ll} -x_i^{n-1} & \text{ if }S_p^n\neq i \\ -m_{S_c^n}^{n-1} & \text{ if }S_p^n=i. +x_i^{n-1} & \text{ si }S_p^n\neq i \\ +m_{S_c^n}^{n-1} & \text{ si }S_p^n=i. \end{array} \right. \\ \\ m_j^n=\left\{ \begin{array}{ll} -m_j^{n-1} & \text{ if }S_m^n\neq j \\ +m_j^{n-1} & \text{ si }S_m^n\neq j \\ & \\ -\overline{m_j^{n-1}} & \text{ if }S_m^n=j. +\overline{m_j^{n-1}} & \text{ si }S_m^n=j. \end{array} \right. \end{array} @@ -594,32 +594,32 @@ embarqué plusieurs fois dans $x^l$. Or, en comptant le nombre de fois où ce bit a été inversé dans $S_m$, la valeur de $m_j$ peut se déduire en plusieurs places. Sans attaque, toutes ces valeurs sont identiques -et le message est obtenus immédiatement. +et le message est obtenu immédiatement. Si attaque il y a, la valeur de $m_j$ peut s'obtenir en prenant la valeur moyenne de toutes les valeurs obtenues. \subsection{Détecter si le média est marqué}\label{sub:ci2:distances} On considère un média $y$ marqué par un message $m$. Soit $y'$ une version altérée de $y$, c.-à-d. une version -où certains bits on été modifiés et soit +où certains bits ont été modifiés et soit $m'$ le message extrait de $y'$. Pour mesurer la distance entre $m'$ et $m$, on considère respectivement -$M$ et $M$ l'ensemble des indices de $m$ et de $m'$ +$M$ et $M'$ l'ensemble des indices de $m$ et de $m'$ où $m_i$ vaut 1 et ou $m'_1$ vaut 1. Beaucoup de mesures de similarité~\cite{yule1950introduction,Anderberg-Cluster-1973,Rifqi:2000:DPM:342947.342970}, dépendent des ensembles $a$, $b$, $c$ et $d$ définis par $a = |M \cap M' |$, $b = |M \setminus M' |$, -$c = |M' \setminus M|$, and +$c = |M' \setminus M|$ et $d = |\overline{M} \cap \overline{M'}|$ Selon ~\cite{rifq/others03} la mesure de Fermi-Dirac $S_{\textit{FD}}$ est celle dont le pouvoir de discrimination est le plus fort, -c.-à-d. celui qui permet la séparation la plus forte entre des vecteurs -corrélés et des ceux qui ne le sont pas. +c.-à-d. celle qui permet la séparation la plus forte entre des vecteurs +corrélés et des des vecteurs qui ne le sont pas. La distance entre $m$ et $m'$ est construite selon cette mesure et produit un réel dans $[0;1]$. Si elle est inférieure à un certain seuil (à définir), le média $y'$ est déclaré @@ -630,7 +630,7 @@ La méthode d'expérimentation de robustesse appliquée à la section précéden pourrait être réappliquée ici et nous pourrions obtenir, grâce aux courbes de ROC une valeur seuil pour déterminer si une marque est présente ou pas. Dans~\cite{bcfg+13:ip}, nous n'avons cependant pas poussé -la démarche plus loin que de l'embarquement +la démarche plus loin que dans la direction de l'embarquement dans les bits de poids faible en spatial et l'on sait que ceci est particulièrement peu robuste. diff --git a/preuveDistanceGeneralisee.tex b/preuveDistanceGeneralisee.tex index c8a6c5c..93c8481 100644 --- a/preuveDistanceGeneralisee.tex +++ b/preuveDistanceGeneralisee.tex @@ -4,7 +4,7 @@ on définit \displaystyle{d_S(S,S')=\frac{9}{{\mathsf{N}}}\sum_{t\in\Nats}\frac{|S_t \Delta S'_t|}{10^{t+1}}}. \] Montrons que $d_S$ est une distance sur $\mathcal{P}(\{1, \ldots, {\mathsf{N}}\})$ et ainsi -que $d$ définie à l'equation~(\ref{eq:distance:Xg}) est une distance. +que $d$ définie à l'équation~(\ref{eq:distance:Xg}) est une distance. diff --git a/sdd.tex b/sdd.tex index c41efa9..ad52238 100644 --- a/sdd.tex +++ b/sdd.tex @@ -147,7 +147,7 @@ schémas suivants : jour. La suite $S = \left(s^t\right)^{t \in \mathds{N}}$ est une séquence de sous-ensembles de $[{\mathsf{N}}]$ appelée \emph{stratégie généralisée}. - Il est basé sur la relation définie pour tout $i \in [{\mathsf{N}}]$ par + Ce schéma est basé sur la relation définie pour tout $i \in [{\mathsf{N}}]$ par \begin{equation} x^{t+1}_i= \left\{ \begin{array}{l} @@ -184,7 +184,7 @@ sont les éléments de $\Bool^{\mathsf{N}}$ (voir \textsc{Figure}~\ref{fig:xpl:g est le graphe orienté de $\Bool^{\mathsf{N}}$ qui contient un arc $x \rightarrow y$ si et seulement si $y=f(x)$. \item Le \emph{graphe des itérations unaires} de $f$, noté $\textsc{giu}(f)$ -est le graphe orienté de $\Bool^{\mathsf{N}}$ qui contient un arc $x \rightarrow y$ pour $x \neq$ si +est le graphe orienté de $\Bool^{\mathsf{N}}$ qui contient un arc $x \rightarrow y$ si et seulement s'il existe $i \in \Delta f(x)$ tel que $y = \overline{x}^i$. Si $\Delta f(x)$ est vide, on ajoute l'arc $x \rightarrow x$. @@ -275,7 +275,7 @@ On a la proposition suivante: \begin{theorem}\label{Prop:attracteur} La configuration $x$ est un point fixe si et seulement si -$\{x\}$ est un attracteur du graphe d'itération (synchrone, unaire, généralisé). +$\{x\}$ est un attracteur du graphe d'itérations (synchrone, unaire, généralisé). En d'autres termes, les attracteurs non cycliques de celui-ci sont les points fixes de $f$. Ainsi pour chaque $x\in \Bool^{\mathsf{N}}$, il existe au moins un chemin @@ -316,7 +316,7 @@ ${\mathsf{N}}\times {\mathsf{N}}$. Celle-ci mémorise uniquement l'existence d'une dépendance de tel élément vis à vis de tel élément. -Elle ne mémorise pas \emph{comment} dépendent les éléments +Elle ne mémorise pas \emph{comment} les éléments dépendent les uns par rapport aux autres. Cette matrice est nommée \emph{matrice d'incidence}. diff --git a/stabylo.tex b/stabylo.tex index c08354a..5c9bce5 100644 --- a/stabylo.tex +++ b/stabylo.tex @@ -8,8 +8,8 @@ un hôte vierge d'une image contenant un message. Les outils les plus récents et les plus efficaces de cette famille sont HUGO~\cite{DBLP:conf/ih/PevnyFB10}, WOW~\cite{conf/wifs/HolubF12} et UNIWARD~\cite{HFD14}. -Pour détecter de la présence ou non d'un message dans une image, -on peut demander l'oracle à un +Pour détecter la présence ou non d'un message dans une image, +on peut demander l'oracle à un \emph{stéganalyseur}~\cite{LHS08,DBLP:conf/ih/Ker05,FK12}. Usuellement, un outil de cette famille, après une démarche d'apprentissage, classifie les images @@ -22,7 +22,7 @@ SPAM~\cite{DBLP:journals/tifs/PevnyBF10}, HUGO mesure la distorsion qui serait induite par la modification de chaque pixel. Similairement, WOW et UNIWARD construisent une carte de distorsion mais celle-ci est -issue caractéristiques directionnelles calculées à partir d'ondelettes. +issue de caractéristiques directionnelles calculées à partir d'ondelettes. A partir de ces cartes de distorsion, chacun de ces algorithmes sélectionne les pixels dont les modifications induisent la distorsion la plus faible possible. Ceci revient à définir une fonction de signification $u$. @@ -78,7 +78,7 @@ le message $m$. \subsection{Un embarquement dans les bords}\label{sub:edge} -L'idée d'embarquer dans des bords dans une image +L'idée d'embarquer dans les bords d'une image repose sur le fait que les pixels de ceux-ci représentent déjà une rupture de continuité entre pixels voisins. Une faible modification de ceux-ci n'aurait donc pas un grand impact sur la qualité @@ -105,18 +105,18 @@ Nous argumentons que le schéma d'embarquement doit s'adapter au message $m$ et au nombre de bits disponibles pour cet embarquement. Deux stratégies sont possibles dans STABYLO. Dans la première, dite \emph{adaptative}, le taux d'embarquement -(rapport entre le nombre de bits embarqués par rapport au nombre de pixels +(rapport entre le nombre de bits embarqués et le nombre de pixels modifiés) dépend du nombre de bits disponibles à l'issue de l'extraction des pixels de bords. Si ce nombre de bits est inférieur au double de la taille du message, celui-ci est découpé en plusieurs parties. -La justification de ce rapport de 1 à 2 à donné ci dessous dans la partie STC. +%La justification de ce rapport de 1 à 2 à donné ci dessous dans la partie STC. Dans la seconde dite \emph{fixe}, ce taux est fixe et l'algorithme augmente iterrativement la valeur de $T$ jusqu'à obtenir à nouveau deux fois plus de bits de bords qu'il n'y en a dans le message. STABYLO applique alors par défaut l'algorithme STC~\cite{DBLP:journals/tifs/FillerJF11} -pour ne modifier aussi peu que possible les bits parmi ceux dont il dispose. +pour modifier aussi peu que possible les bits parmi ceux dont il dispose. Dans le cas où c'est la stratégie adoptive qui est choisie, le paramètre $\rho$ de cet algorithme vaut 1 pour chacun des bits. Dans le cas contraire, la valeur de ce paramètre varie en @@ -175,7 +175,7 @@ La figure~\ref{fig:compared} représente graphiquement les complexités des étapes d'embarquement des schémas WOW/UNIWARD, HUGO, and STABYLO en considérant des images de la taille $n \times n$ où $n$ varie entre 512 et 4096. L'axe des $y$ est exprimé selon une échelle logarithmique. -Cette figure illustre bien le fait que le qualificatif de \og LOw cost\fg{} +Cette figure illustre bien le qualificatif de \og LOw cost\fg{} attribué à STABYLO. \begin{figure} \begin{center} @@ -189,8 +189,8 @@ attribué à STABYLO. Comme dans le chapitre~\ref{chap:watermarking}, la base BOSS~\cite{Boss10} de 10,000 images (au format RAW, de taille $512\times 512$ en niveau de gris) a été à nouveau prise pour évaluer le schéma face à une épreuve de stéganalyse. -Pour des rapport entre le nombre de bits embarqués par -rapport au nombre de pixels entre 1/2 et 1/9, le choix de la +Pour des rapports entre le nombre de bits embarqués et le +nombre de pixels entre 1/2 et 1/9, le choix de la matrice dupliquée dans STC est celui énoncé dans les travaux de Filler~\cite{FillerJF11}. diff --git a/stegoyousra.tex b/stegoyousra.tex index de9836b..d931298 100644 --- a/stegoyousra.tex +++ b/stegoyousra.tex @@ -1,7 +1,7 @@ La plupart des schémas de stéganographie sont conçus de sorte à minimiser une fonction de distorsion. Dans les exemples du chapitre précédent, ces fonctions de distorsion sont construites dans l'objectif de préserver -les caractéristiques de l'images. +les caractéristiques de l'image. On comprend aisément que dans des régions uniformes ou sur des bords clairement définis, une modification même mineure de l'image est facilement détectable. Au contraire les textures, le bruit ou les régions chaotiques @@ -73,7 +73,7 @@ En un pixel $(x_0,y_0)$, plus les valeurs de cette matrice sont éloignées de z plus le gradient varie en ce point. Évaluer ce type de matrice est ainsi primordial en stéganographie. Cependant cette tâche n'est pas aussi triviale qu'elle n'y paraît puisque les images naturelles ne sont pas définies à l'aide -de fonction différentiables de $\R^+\times \R^+$ +de fonctions différentiables de $\R^+\times \R^+$ dans $\R^+$. La suite montre comment obtenir des approximations de telles matrices. @@ -125,9 +125,9 @@ de gradient d'images}\label{sub:class:2} Il est connu que $\dfrac{\partial^2 P}{\partial x \partial y} $ est égal à $\dfrac{\partial^2 P}{\partial y \partial x}$ si -les méthode qui calculent le gradient et le gradient du gradient (la matrice hessienne) +les méthodes qui calculent le gradient et le gradient du gradient (la matrice hessienne) sont les mêmes. -Le tableau~\ref{table:hessian:usual} résume les les noyaux +Le tableau~\ref{table:hessian:usual} résume les noyaux $K_{x^2}''$ et $K_{xy}''$ qui permettent de calculer respectivement @@ -239,14 +239,15 @@ pour chacun des opérateurs de gradient rappelés à la section précédente. \end{table} Le noyau $\textit{Ks}_{x^2}''$ permet de détecter si le -pixel central appartient à un bord ``vertical'', même si celui contient du bruit, -en considérant ces voisins verticaux. Ces derniers sont vraiment +pixel central appartient à un bord ``vertical'', même si celui-ci + contient du bruit, +en considérant ses voisins verticaux. Ces derniers sont vraiment pertinents dans un objectif de détecter les bords. Cependant, leur lien avec les lignes de niveau n'est pas direct. De plus tous les pixels qui sont dans la deuxième et la quatrième colonne de ce noyau sont ignorés. Le noyau de Prewitt a des propriétés similaires. Le noyau de différence centrale $\textit{Kc}_{x^2}''$ n'est pas influencé par les -voisins verticaux du pixel central et peu paraître plus adapté ici. +voisins verticaux du pixel central et peut paraître plus adapté ici. Cependant, le noyau $\textit{Kc}_{xy}''$ perd aussi les valeurs des pixels qui sont alignés verticalement et diagonalement avec le pixel central. Enfin, le noyau de différence intermédiaire $\textit{Ki}_{x^2}''$ décale @@ -291,7 +292,7 @@ qui représente en effet les variation horizontales de la partie horizontale du gradient autour du pixel central. On obtient donc bien une approximation de $\dfrac{\partial^2 P}{\partial x^2}$. Lorsque $n$ vaut 1, ce noyau est une version centrée du noyau horizontal de différence -intermédiaires. $\textit{Ki}_{x^2}''$ à un facteur $1/2$ près). +intermédiaire. $\textit{Ki}_{x^2}''$ à un facteur $1/2$ près). Lorsque $n$ vaut 2, on retrouve $\textit{Kc}_{x^2}''$. Les variations verticales du gradient sont aussi obtenues en faisant subir @@ -375,7 +376,7 @@ et de $\dfrac{\partial^2 P}{\partial y^2}$. La section suivante étudie la pertinence d'interpoler une image par un polynome -lorsqu'on cherche a obtenir ces dérivées secondes. +lorsqu'on cherche à obtenir ces dérivées secondes. \section{Interpolation polynomiale pour le calcul de la matrice hessienne}\label{sec:poly} @@ -545,7 +546,7 @@ On remarque que pour $n=1$, le noyau est égal à $Kc''_{xy}$. \section{Fonction de distorsion}\label{sec:distortion} Une fonction de distorsion associe à chaque pixel $(i,j)$ -le coût $\rho_{ij}$ du modification par $\pm 1$. L'objectif est d'associer une +le coût $\rho_{ij}$ de modification par $\pm 1$. L'objectif est d'associer une valeur faible aux pixels dont toutes les dérivées secondes sont éloignées de 0 et une valeur rédhibitoire sinon. Dans WOW comme dans UNIWARD la fonction de distorsion est définie par @@ -559,7 +560,7 @@ Dans WOW comme dans UNIWARD la fonction de distorsion est définie par \] où $p$ est un nombre négatif et $\xi_{ij}^h$ (resp. $\xi_{ij}^v$ et $\xi_{ij}^d$) -représentent la pertinence horizontale (resp. verticale et diagonale) de modification. +représente la pertinence horizontale (resp. verticale et diagonale) de modification. Une faible pertinence dans une direction signifie que l'embarquement dans ce pixel est inapproprié. La fonction de distorsion que l'on a retenu est une particularisation ($p=-1$) @@ -615,9 +616,8 @@ concentrent les changements. Les deux méthodes présentées ici dépendent de noyaux dont la taille va jusqu'à $(2N+1)\times(2N+1)$. Cette section montre comment évaluer $N$ pour maximiser le niveau de sécurité. -Pour chaque approche, 1,000 images stégos avec -$N=2$, $4$, $6$, $8$, $10$, $12$ et $14$ et dont les supports appartiennent -à l'ensemble des 10000 images du challenge BOSS. +Pour chaque approche ($N=2$, $4$, $6$, $8$, $10$, $12$ et $14$), +1000 images stégos du challenge BOSS ont été selectionnées. La sécurité de l'approche a été évaluée avec le stéganalyseur Ensemble Classifier~\cite{DBLP:journals/tifs/KodovskyFH12}. Pour un taux d'embarquement $\alpha$ égal soit à $0.1$ ou soit à $0.4$, @@ -626,7 +626,7 @@ Le tableau~\ref{table:choice:parameter} synthétise les résultats. On observe que la taille $N=4$ (respectivement $N=12$) permet d'obtenir des erreurs suffisamment élevées pour l'approche basée sur $Ky$ (resp. pour celle basée sur $Ko$). -Ces deux valeurs de paramètre sont retenues par la suite. +Ces deux valeurs de paramètres sont retenues par la suite. \begin{table}[ht] \caption{Erreur moyenne de test en fonction de la taille du noyau} -- 2.39.5