\end{equation}
Dans cette définition, la fonction
-$\sigma: {\mathsf{N}}]^{\Nats} \longrightarrow
+$\sigma: [{\mathsf{N}}]^{\Nats} \longrightarrow
[{\mathsf{N}}]^{\Nats}
$
décale
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$}
% $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
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
\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
\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}$.
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})).
\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
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}
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}
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.
à $\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.
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}}$.
$$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}
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.
$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.
\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},
à 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é.
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$).
\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}
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
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.
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)$.
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.
$$\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.
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}
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
$$
-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
\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})$.
$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.
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
-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}
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}
\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
\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 :
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é.
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.
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)
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)$).
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)$.
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
$ 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.
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 à
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}
\]
\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
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}
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}
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
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.
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
\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é
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.
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.
${\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é.
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
\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.
\]
Un entier $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ est \emph{équitable}
- au temps $t$ s'il existe $0\leq j <t$ tel que $Z_{j+1}=(\ell,\cdot)$ et $h(X_j)\neq \ell$. En d'autres mots, il existe une date $j$ anérieure à $t$
+ au temps $t$ s'il existe $0\leq j <t$ tel que $Z_{j+1}=(\ell,\cdot)$ et $h(X_j)\neq \ell$. En d'autres mots, il existe une date $j$ antérieure à $t$
où le premier élément de la variable aléatoire $Z$ est $l$
(\textit{i.e.}, la stratégie vaut $l$ à la date $j$)
et où le n{\oe}ud $X_j$ permet de traverser l'arc $l$.
-Soit $\ts$ le premier tempsoù touis les éléments de $\llbracket 1, {\mathsf{N}} \rrbracket$
-sont équitables. On a le lemme suiant:%L'entier $\ts$ est un temps d'arrêt pour la chaîne de Markov $(X_t)$.
+Soit $\ts$ le premier temps où tous les éléments de $\llbracket 1, {\mathsf{N}} \rrbracket$
+sont équitables. On a le lemme suivant:%L'entier $\ts$ est un temps d'arrêt pour la chaîne de Markov $(X_t)$.
\begin{lemma}
A chaque étape, le $l^{\textrm{ème}}$ bit est inversé de $0$ à $1$ ou de $1$ à $0$, chaque fois avec la même
probabilité. Ainsi, pour $t\geq \tau_\ell$, le
$\ell^{\textrm{ème}}$ bit de $X_t$ est $0$ ou $1$ avec la même probabilité,
-et ce indépendament de la valeur des autres bits.
+et ce indépendamment de la valeur des autres bits.
\end{proof}
Pour chaque $X\in \Bool^{\mathsf{N}}$ et $\ell\in [{\mathsf{N}}]$,
soit $S_{X,\ell}$ une variable aléatoire qui compte le nombre d'itérations
-tel qu'en démarant de la configuration $X$ on en atteigne une où
+tel qu'en démarrant de la configuration $X$ on en atteigne une où
$\ell$ est équitable. Plus formellement,
$$S_{X,\ell}=\min \{t \geq 1\mid h(X_{t-1})\neq \ell\text{ et }Z_t=(\ell,.)\text{ et } X_0=X\}.$$
On peut majorer l'espérance de cette variable aléatoire comme suit.
Dans la configuration $X$ avec $i-1$ bits équitables,
la probabilité d'obtenir un nouveau bit équitable est soit
$1-\frac{i-1}{{\mathsf{N}}}$ si $h(X)$ est équitable,
-et $1-\frac{i-2}{{\mathsf{N}}}$ si $h(X)$ ne l'est pas.
+soit $1-\frac{i-2}{{\mathsf{N}}}$ si $h(X)$ ne l'est pas.
Ainsi,
$\P (W_i=k)\leq \left(\frac{i-1}{{\mathsf{N}}}\right)^{k-1} \frac{{\mathsf{N}}-i+2}{{\mathsf{N}}}.$
Tous les éléments sont en place pour majorer l'espérance de $\ts$.
\begin{theorem}
\label{prop:stop}
-Si $\ov{h}$ est bijective et anti involutive
+Si $\ov{h}$ est bijective et anti- involutive
$\ov{h}(\ov{h}(X))\neq X$, alors
$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$.
\end{theorem}
\begin{lemma}[Stratégie équivalente]\label{lemma:strategy}
Soit $\phi$ un système dynamique discret de stratégie $(S^t)^{t \in \Nats}$
- et $\psi$ sa traduction en promela.
+ et $\psi$ sa traduction en PROMELA.
Il existe une exécution de $\psi$ sous hypothèse d'équité faible telle
- le le scheduler met à jour les elements of $S^t$
- donnés par \verb+update_elems+ à l'iteration $t$.
+ le scheduler met à jour les éléments of $S^t$
+ donnés par \verb+update_elems+ à l'itération $t$.
\end{lemma}
\begin{proof}
La preuve est directe pour $t=0$.
- Supposons qu'elle est établie jusqu'en $t$ vallant un certain $t_0$.
+ Supposons qu'elle est établie jusqu'en $t$ valant un certain $t_0$.
On considère des stratégies pseudo périodiques.
Grâce à l'hypothèse d'équité faible, \verb+update_elems+ modifie
- les éléments de $S^t$ à l'iteration $t$.
+ les éléments de $S^t$ à l'itération $t$.
\end{proof}
Dans ce qui suit, soit $Xd^t_{ji}$ la valeur de
dans la fonction \verb+update_elems+ à l'itération $t$ où
% \begin{itemize}
% \item
- $Y^k_{ij}$ est la valeur du cannal \verb+channels[i].sent[j]+
+ $Y^k_{ij}$ est la valeur du canal \verb+channels[i].sent[j]+
à l'indice $k$,
%\item
$a^k_{ij}$ est la date (antérieure à $t$) mémorisant quand $Y^k_{ij}$ est ajouté et
\end{array}
\end{equation*}
-Intuitivement, $M_{ij}^t$ est la mémoire du cannal
-\verb+channels[i].sent[j]+ à l'iterations $t$.
+Intuitivement, $M_{ij}^t$ est la mémoire du canal
+\verb+channels[i].sent[j]+ à l'itération $t$.
On note que le domaine de chaque $M_{ij}^1$ est $\{0\}$ et
$M_{ij}^1(0)=(\verb+Xp[i]+,0,0)$: en effet le processus
\verb+init+ initialise \verb+channels[i].sent[j]+ avec \verb+Xp[i]+.
Montrons comment l'indéterminisme des deux fonctions
\verb+fetch_values+ et \verb+diffuse_values+
permet de modéliser l'équation \Equ{eq:async}.
-La function $M_{ij}^{t+1}$ est obtenue à l'aide de mises à jour successives
-de $M_{ij}^{t}$ au travers des deux functions \verb+fetch_values+ and
+La fonction $M_{ij}^{t+1}$ est obtenue à l'aide de mises à jour successives
+de $M_{ij}^{t}$ au travers des deux fonctions \verb+fetch_values+ and
\verb+diffuse_values+. Par abus, soit $M_{ij}^{t+1/2}$
la valeur de $M_{ij}^{t}$ après la première fonction pendant l'itération
$t$.
Dans la fonction \verb+diffuse_values+,
s'il existe un $\tau$, $\tau\ge t$
tel que \mbox{$D^{\tau}_{ji} = t$}, soit alors $c_{ij}$ défini par $ \min\{l \mid
-D^{l}_{ji} = t \} $. Dans ce cas, on exécution l'instruction qui
-ajoute la valeur \verb+Xp[i]+ dans la queue du cannal
+D^{l}_{ji} = t \} $. Dans ce cas, on exécute l'instruction qui
+ajoute la valeur \verb+Xp[i]+ dans la queue du canal
\verb+channels[i].sent[j]+. Alors,
$M_{ij}^{t+1}$ est défini en étendant $M_{ij}^{t+1/2}$ à $m$ de sorte que
$M_{ij}^{t+1}(m)$ est $(\verb+Xp[i]+,t,c_{ij})$.
\begin{lemma}[Existence d'une exécution SPIN]\label{lemma:execution}
- Pour chaque sequence $(S^t)^{t \in \Nats}$,\linebreak $(D^t)^{t \in \Nats}$,
+ Pour chaque séquence $(S^t)^{t \in \Nats}$,\linebreak $(D^t)^{t \in \Nats}$,
pour chaque fonction $F$,
il existe une exécution SPIN telle que pour toute itération $t$, $t
\ge 1$, et pour chaque $i$ et $j$ dans $[ \mathsf{N} ]$
la variable \verb+Xp[k]+ en sortant du processus
\verb+update_elems+ est égale à
$X_k^{t}$ \textit{i.e.}, $F_{k}\left( X_1^{D_{k\,1}^{t-1}},\ldots,
- X_{\mathsf{N}}^{D_{k\,{\mathsf{N}}}^{t-1}}\right)$ à la fin de la $t^{\text{th}}$ itération.
+ X_{\mathsf{N}}^{D_{k\,{\mathsf{N}}}^{t-1}}\right)$ à la fin de la $t^{\text{ème}}$ itération.
\end{lemma}
\begin{proof}
La preuve est faite par induction sur le nombre d'itérations.
\paragraph{Situation initiale:}
-Pour le premier item, par definition de $M_{ij}^t$, on a $M_{ij}^1(0) = \left(
+Pour le premier item, par définition de $M_{ij}^t$, on a $M_{ij}^1(0) = \left(
\verb+Xp[i]+, 0,0 \right)$ qui est égal à $\left(X_i^{D_{ji}^{0}},
0,0 \right)$.
Ensuite, le premier appel à la fonction \verb+fetch_value+
-soit affecte à la tête de \verb+channels[i].sent[j]+ à \verb+Xd[j].v[i]+ soit ne modifie par
+soit affecte la tête de \verb+channels[i].sent[j]+
+à \verb+Xd[j].v[i]+ soit ne modifie par
\verb+Xd[j].v[i]+.
Grâce au processus \verb+init+ process,
les deux cas sont égaux à
-\verb+Xp[i]+, \textit{i.e.}, $X_i^0$. L'equation (\ref{eq:correct_retrieve}) est ainsi établie.
+\verb+Xp[i]+, \textit{i.e.}, $X_i^0$. L'équation (\ref{eq:correct_retrieve}) est ainsi établie.
Pour le dernier item, soit $k$, $0 \le k \le \mathsf{N}-1$.
A la fin de la première exécution du processus \verb+update_elems+,
Il reste à prouver la partie inductive de la troisième partie du lemme.
Soit $k$, $k
\in S^{l+1}$. % and $\verb+k'+ = k-1$.
-A l'issue de la première exécutions
+A l'issue de la première exécution
du processus \verb+update_elems+, on a
$\verb+Xp[+k\verb+]+= F(\verb+Xd[+k\verb+][0]+,
\ldots,\verb+Xd[+k\verb+][+n\verb+-1]+)+$.
Par définition $Xd=F(Xd^{l+1}_{k\,0}, \ldots,Xd^{l+1}_{k\,n-1})$.
-Grace à~\Equ{eq:correct_retrieve} déjà prouvée, on peut conclure la preuve.
+Grâce à~\Equ{eq:correct_retrieve} déjà prouvée, on peut conclure la preuve.
\end{proof}
\begin{lemma}
- Borner la taille du cannal à $\textit{max} = \delta_0$ est suffisant
+ Borner la taille du canal à $\textit{max} = \delta_0$ est suffisant
lorsqu'on simule un système dynamique dont les délais sont bornés par
$\delta_0$.
\end{lemma}
Pour chaque $i$ et $j$, à chaque itération $t+1$, comme les délais sont bornés par
$\delta_0$, l'élément $i$ doit connaître au plus $\delta_0$
valeurs qui sont
- $X_j^{t}$, \ldots, $X_j^{t-\delta_0+1}$. Elles peuvent être mémorisées dans n'importe quel cannal
+ $X_j^{t}$, \ldots, $X_j^{t-\delta_0+1}$. Elles peuvent être mémorisées dans n'importe quel canal
de taille $\delta_0$.
\end{proof}
% to convenient available dates $D_{ji}$. It is then easy to construct
% corresponding iterations of the DDN that are convergent.
% \ANNOT{quel sens donnes-tu a \emph{convenient} ici ?}
- Montrons la conraposée du théorème.
+ Montrons la contraposée du théorème.
Le lemme précédent a montré que pour chaque séquence d'itérations du système dynamique discret,
Il existe une exécution du modèle PROMELA qui la simule.
Si des itérations du système dynamique discret sont divergentes, leur exécution vont empêcher
le modèle PROMELA de se stabiliser, \textit{i.e.}
- ce dernier ne verifiera pas la propriété LTL (\ref{eq:ltl:conv}).
+ ce dernier ne vérifiera pas la propriété LTL (\ref{eq:ltl:conv}).
\end{proof}
\promelacomplete*
\begin{proof}
- Pour chaque modele $\psi$
+ Pour chaque modèle $\psi$
qui ne vérifie pas la propriété LTL (\ref{eq:ltl:conv}),
- il est immédiat de construire les itérations correpondantes du
+ il est immédiat de construire les itérations correspondantes du
système dynamique, dont la stratégie est pseudo périodique en raison
de la propriété d'équité faible..
On suppose tout d'abord que ${\mathsf{N}}$ a une boucle
négative.
Alors, d'après la définition de
-$G(f)$, il existe $x\in\Bool^{\mathsf{N}}$ tel que $f_{{\mathsf{N}}{\mathsf{N}}}(x)<0$.
+$G(f)$, il existe $x\in\Bool^{\mathsf{N}}$ tel que $f_{{\mathsf{N}}}(x)<0$.
Ainsi si $x_{\mathsf{N}}=0$, on a $f_{\mathsf{N}}(x)>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}})$;
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
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
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}.
$(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}):
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.
\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}
$(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$.
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.
à 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*}
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
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
\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 .
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.
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.
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.
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
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
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
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.
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
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
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
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
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
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}
%%--------------------
%% 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.
%%--------------------
%% Change the speciality of the PhD thesis
-%\Set{speciality}{Informatique}
+\Set{speciality}{Informatique}
%%--------------------
%% Change the institution
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.
\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}.
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.
\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}
\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}
\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}
% 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$)
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$
$$
\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
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}
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:
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}
\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.
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.
\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).
\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}
% \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}
\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.
\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}
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
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
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
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}
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
\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}
\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)})
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}
\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é (
\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
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$:
\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} &
\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
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}
\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}
$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) \\
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}
$\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|$.
\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}
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}
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}.
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.
\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
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)$.
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
\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}
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é
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.
\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.
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}
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$.
\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
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}.
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
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$.
\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é
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
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}
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}.
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
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.
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
\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
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
$\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}
\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
\]
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$)
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$,
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}
