$\mathcal{R}$ des fonctions régulières
et $\mathcal{C}$ des fonctions chaotiques définis respectivement ci-dessous:
\begin{itemize}
-\item $\mathcal{T} = \left\{f : \mathds{B}^n \to
-\mathds{B}^n \textrm{ t. q. } G_{f_u} \textrm{ est transitive} \right\}$,
-\item $\mathcal{R} = \left\{f : \mathds{B}^n \to
-\mathds{B}^n \textrm{ t. q. } G_{f_u} \textrm{ est régulière} \right\}$,
-\item $\mathcal{C} = \left\{f : \mathds{B}^n \to
-\mathds{B}^n \textrm{ t. q. } G_{f_u} \textrm{ est chaotique} \right\}$.
+\item $\mathcal{T} = \left\{f : \mathds{B}^{\mathsf{N}} \to
+\mathds{B}^{\mathsf{N}} \textrm{ t. q. } G_{f_u} \textrm{ est transitive} \right\}$,
+\item $\mathcal{R} = \left\{f : \mathds{B}^{\mathsf{N}} \to
+\mathds{B}^{\mathsf{N}} \textrm{ t. q. } G_{f_u} \textrm{ est régulière} \right\}$,
+\item $\mathcal{C} = \left\{f : \mathds{B}^{\mathsf{N}} \to
+\mathds{B}^{\mathsf{N}} \textrm{ t. q. } G_{f_u} \textrm{ est chaotique} \right\}$.
\end{itemize}
On énonce les théorèmes successifs suivants dont les preuves sont données
-dans~\cite{guyeux10}.
+dans~\cite{guyeuxphd}.
\begin{theorem} $G_{f_u}$ est transitive si et seulement si
$\textsc{giu}(f)$ est fortement connexe.
section~\ref{sec:mixing}.
L'extension du travail aux itérations généralisées est présentée à la
section~\ref{sec:prng:gray:general}.
-Finalement, des instances de PRNGS engendrés selon les méthodes détaillées dans
-ce chapitre sont présentés en section~\ref{sec:prng;gray:tests}.
-Les sections~\ref{sec:plc} à~\ref{sub:gray} ont été publiées
+Finalement, des instances de PRNGs engendrés selon les méthodes détaillées dans
+ce chapitre sont présentées en section~\ref{sec:prng;gray:tests}.
+Les sections~\ref{sec:plc} à~\ref{sub:gray} ont été publiées
à~\cite{chgw+14:oip}.
+La section~\ref{sec:mixing} est publiée dans~\cite{ccgh16}.
% This aim of this section is to show
configuration $i$ est inférieur à ${\mathsf{N}}$;
\item pour $j \neq i$, $0 \le M_{ij} \le 1$: on construit l'arc de $i$ à $j$
-si et seulement si $M_{ij}$ vaut 1 (et 0 sinon)
+si et seulement si $M_{ij}$ vaut 1 (et 0 sinon);
\item pour chaque indice de ligne $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$:
la matrice est stochastique à droite;
\item pour chaque indice de colonne $j$,
principalement de prouver que si $\mathsf{N}$ est une puissance de 2,
le code de Gray équilibré engendré par l'extension est toujours totalement équilibré et
que $S_{\mathsf{N}}$ est la séquence de transition d'un code de Gray de $\mathsf{N}$ bits
-si $S_{\mathsf{N}-2}$ l'est aussi..
+si $S_{\mathsf{N}-2}$ l'est aussi.
Cependant les auteurs ne prouvent pas que leur approche fournit systématiquement
un code de Gray (totalement) équilibré.
Cette section montre que ceci est vrai en rappelant tout d'abord
}
\Return{$\textit{nbit}$}\;
%\end{scriptsize}
-\caption{Pseudo Code pour évaluer le temps d'arrêt}
+\caption{Pseudo-code pour évaluer le temps d'arrêt}
\label{algo:stop}
\end{algorithm}
définie par
$M = \dfrac{1}{2^n} \check{M}$.
Si $\textsc{gig}(f)$ est fortement connexe, alors
- la sortie du générateur de nombres pseudo aléatoires détaillé par
+ la sortie du générateur de nombres pseudo-aléatoires détaillé par
l'algorithme~\ref{CI Algorithm:prng:g} suit une loi qui
tend vers la distribution uniforme si
et seulement si $M$ est une matrice doublement stochastique.
Ce chapitre présente donc une application directe
de la théorie développée ci-avant
-à la génération de nombres pseudo aléatoires.
+à la génération de nombres pseudo-aléatoires.
La section~\ref{sub:prng:algo}
présente tout d'abord l'algorithme de PRNG. La contrainte de
distribution uniforme de la sortie est discutée dans cette section.
La section~\ref{sub:prng:algo} a été publiée à ~\cite{bcgw11:ip,bcgr11:ip}.
-\section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo}
+\section{ Nombres pseudo-aléatoires construits par itérations unaires}\label{sub:prng:algo}
\end{algorithm}
\subsection{Algorithme d'un générateur}
-On peut penser à construire un générateur de nombres pseudo
-aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.
+On peut penser à construire un générateur de nombres
+pseudo-aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.
Celui-ci prend en entrée: une fonction $f$;
vue au chapitre~\ref{chap:carachaos}) et correspondant
à des itérations unaires.
En interne, il exploite un algorithme de génération
-de nombres pseudo aléatoires donné en paramètre.
+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 à ce générateur embarqué.
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.
+nombres pseudo-aléatoires est uniformément distribuée ou non.
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)$.
sont donc fortement connexes, ce que l'on peut vérifier aux figures~\ref{fig:g:iter}
et~\ref{fig:h:iter}.
\textit{A priori}, ces deux fonctions pourraient être intégrées
-dans un générateur de nombres pseudo aléatoires. Montrons que ce n'est pas le cas pour $g$ et
+dans un générateur de nombres pseudo-aléatoires. Montrons que ce n'est pas le cas pour $g$ et
que cela l'est pour $h$.
pour n'importe quel vecteur initial de probabilités $\pi^0$, on a
$\lim_{k \to \infty} \pi^0 M^k_g = \pi_g$ et
$\lim_{k \to \infty} \pi^0 M^k_h = \pi_h$.
-Ainsi la chaîne de Markov associé à $h$ tend vers une
+Ainsi la chaîne de Markov associée à $h$ tend vers une
distribution uniforme, contrairement à celle associée à $g$.
On en déduit que $g$ ne devrait pas être itérée dans
-un générateur de nombres pseudo aléatoires.
+un générateur de nombres pseudo-aléatoires.
Au contraire,
$h$ devrait pouvoir être embarquée dans l'algorithme~\ref{CI Algorithm},
pour peu que le nombre $b$ d'itérations entre deux mesures successives
définie par
$M = \dfrac{1}{n} \check{M}$.
Si $\textsc{giu}(f)$ est fortement connexe, alors
- la sortie du générateur de nombres pseudo aléatoires détaillé par
+ la sortie du générateur de nombres pseudo-aléatoires détaillé par
l'algorithme~\ref{CI Algorithm} suit une loi qui
tend vers la distribution uniforme si
et seulement si $M$ est une matrice doublement stochastique.
colonne utilisé comme le paramètre $b$
dans l'algorithme~\ref{CI Algorithm}.
-Soit $e_i$ le $i^{\textrm{ème}}$ vecteur la base canonique de $\R^{2^{n}}$.
+Soit $e_i$ le $i^{\textrm{ème}}$ vecteur de la base canonique de $\R^{2^{n}}$.
Chacun des éléments $v_j$, $1 \le j \le 2^n$,
du vecteur $e_i M_f^t$ représente la probabilité
d'être dans la configuration $j$ après $t$ étapes du processus de Markov
La qualité des séquences aléatoires a été évaluée à travers la suite
de tests statistiques développée pour les générateurs de nombres
-pseudo aléatoires par le
+pseudo-aléatoires par le
\emph{National Institute of Standards and Technology} (NIST).
L'expérience a montré notamment que toutes ces fonctions
passent avec succès cette batterie de tests.
c'est l'ensemble
des $s_{t}^{\textrm{ème}}$ éléments (inclus dans $[{\mathsf{N}}]$) qui
sont mis à jour (cf. équation~(\ref{eq:schema:generalise})).
-On redéfinit la fonction la fonction
+On redéfinit la fonction
$F_{f_g}: \Bool^{\mathsf{N}} \times \mathcal{P}(\{1, \ldots, \mathsf{N}\})
\rightarrow \Bool^{\mathsf{N}}$ par
\[
détruirait la marque dans les deux cas.
La quantification (au sens du traitement du signal) est une réponse
à ces attaques: des positions modifiées de manière mal intentionnée
-peuvent grâce cette démarche être rapprochées (abstraites) en des positions
+peuvent grâce à cette démarche être rapprochées (abstraites) en des positions
préétablies et conserver ainsi leur information et donc la marque.
STDM~\cite{CW01} est une instance de ces schémas de marquage.
La première section fournit quelques rappels sur la STDM. Le schéma basé sur
cette approche est présenté à la section~\ref{sec:stdm:schema}.
Finalement, la démarche expérimentale permettant de trouver un compromis entre
-robustesse et qualité visuelle est présentée à la section~\ref{sec:stdm:exp}
+robustesse et qualité visuelle est présentée à la section~\ref{sec:stdm:exp}.
Ce travail a été publié dans~\cite{BDCC16}.
de chaque caractère rencontré dans le document PDF.
La dimension $L$ est calculée comme la partie entière de $N/k$.
-\item Un générateur pseudo aléatoire (initialisé par une clef)
+\item Un générateur pseudo-aléatoire (initialisé par une clef)
construit $k$ ensembles $M_1$, \ldots, $M_k$
de taille $L$ mutuellement disjoints dans $[1,N]$. Ainsi
$\bigcup_{1\le i \le k} M_i \subseteq [N]$.
caractères du document PDF comme dans la phase d'insertion.
la valeur de $L$ est définie comme précédemment.
-\item le même générateur pseudo aléatoire (initialisé avec la même clef)
+\item le même générateur pseudo-aléatoire (initialisé avec la même clef)
construit les $k$ mêmes ensembles $M_1$, \ldots, $M_k$
de taille $L$ mutuellement disjoints dans $[1,N]$.
\begin{proof}
La preuve est directe pour $t=0$.
Supposons qu'elle est établie jusqu'en $t$ valant un certain $t_0$.
- On considère des stratégies pseudo périodiques.
+ 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'itération $t$.
\end{proof}
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 correspondantes du
- système dynamique, dont la stratégie est pseudo périodique en raison
+ système dynamique, dont la stratégie est pseudo-périodique en raison
de la propriété d'équité faible..
% i.e. iterations that are divergent. Executions are
principes. Des neurones modifiant leur état en suivant une fonction non
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.
+(MLP) n'itèrent quant à eux classiquement pas de fonction chaotique:
+leurs fonctions d'activation sont usuellement choisies parmi les sigmoïdes
+(la fonction tangeante hyperbolique par exemple).
Il a cependant été démontré que ce sont des approximateurs
universels~\cite{Cybenko89,DBLP:journals/nn/HornikSW89}.
Ils permettent, dans certains cas, de simuler des comportements
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érations 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}.
chaotiques.
Comme il est difficile (voir impossible) d'apprendre le comportement
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
+utilisées pour générer des nombres pseudo-aléatoires, ce que propose la partie
suivante.
Dans cette partie, les définitions fondamentales liées au chaos dans les
-systèmes booléens sont rappelées et plusieurs résultats théoriques sont montrés.
+systèmes dynamiques
+ sont rappelées et plusieurs résultats théoriques sont montrés.
\begin{Def}[Chaos (Devaney)]
Une fonction $k$ continue sur un espace métrique $(\mathcal{X},d)$ est \textbf{chaotique}
Les informations traitées par un ordinateur ne sont, \textit{in fine},
que discrètes: les flottants (sur un nombre fini de bits) sont une
interprétation des réels, les \textit{longs} une interprétation finie
-des entiers\ldots.
+des entiers\ldots
Les phénomènes physiques ou naturels peuvent aussi être modélisés par des
approches discrètes:
il n'est parfois pas nécessaire de suivre exactement tous les états par
Une fonction qui admet un attracteur cyclique égal à l'ensemble
des sommets diverge. Admet-il cependant un comportement chaotique?
Les théories mathématiques du chaos ont énoncé des critères permettant
-de décider si une fonction est chaotique ou non, et plus récemment
+de décider si le comportement d'une fonction est chaotique
+ou non, et plus récemment
si certains réseaux booléens l'étaient. Se pose légitimement
-la question de savoir si cette caractérisation s'étend quelques soient
+la question de savoir si cette caractérisation s'étend quels que 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 sait engendrer
uniforme.
Comme annoncé dans les motivations à ce travail, les itérations chaotiques
-peuvent s'appliquer auz marquage de média et plus généralement
+peuvent s'appliquer au 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
\\ %\hline
%journaux
-
+\cite{ccgh16}
&
% conf inter
\cite{bcgr11:ip,bcgw11:ip,cds12:ip,chgw+14:oip,fccg15:ip}
%%--------------------
%% Set the University where HDR was made
-\hdrpreparedin{l'Université de Franche-Comté}
+\hdrpreparedin{Université Bourgone Franche-Comté}
%%--------------------
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
+last method permits to produce a large number of Pseudorandom 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
%%--------------------
%% Set the English keywords. They only appear if
%% there is an English abstract
-\hdrkeywords[english]{discrete dynamical systems, pseudo random number
+\hdrkeywords[english]{discrete dynamical systems, pseudorandom number
generators, information hiding.}
-%%--------------------
-%% Set the French abstract
-\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
- 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, plusieurs méthodes permettant
-d'obtenir de telles fonctions seront proposées,
- dont une basée sur les codes de Gray,
-permettant d'avoir en plus une chaîne de Markov doublement
-stochastique. Cette dernière méthode nous permettra notamment
-d'engendrer une grande famille 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 dans l'équipe) 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 montrerons 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 abstract
+\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 s'intègrent dans cette
+thématique. Dans cette habilitation, nous montrerons 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 d'avancées autour des fonctions dont les
+itérations peuvent être chaotiques. Particulièrement, plusieurs
+méthodes permettant d'obtenir de telles fonctions seront proposées,
+dont une basée sur les codes de Gray, permettant d'avoir en plus une
+chaîne de Markov doublement stochastique. Cette dernière méthode nous
+permettra notamment d'engendrer une grande famille de générateurs de
+nombres pseudo-aléatoires (PRNG). Des contributions théoriques et
+pratiques autour de ces PRNGs seront mises en avant. La thématique de
+masquage d'information (déjà présente dans l'équipe) a été renforcée
+et des avancées significatives sur ce sujet seront présentées. Des
+instances de ces algorithmes seront formalisées en sélectionnant les
+fonctions à itérer pour garantir une robustesse élevée. Finalement,
+nous montrerons 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]{systèmes dynamiques discrets, générateurs de nombres
-pseudo aléatoires, masquage d'information.}
+pseudo-aléatoires, masquage d'information.}
%%--------------------
%% Change the layout and the style of the text of the "primary" abstract.
d'exécution global, mais peut aussi introduire de la divergence.
Dans ce chapitre, après avoir introduit les bases sur les réseaux booléens,
nous avons exposé comment construire un mode combinant les
-avantages du synchronisme en terme de convergence avec les avantages
-de l'asynchronisme en terme de vitesse de convergence.
+avantages du synchronisme en termes de convergence avec les avantages
+de l'asynchronisme en termes de vitesse de convergence.
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 leurs caractéristiques.
-La section~\ref{sec:TIPE12}, qui est une reformulation de~\cite{guyeux10},
+La section~\ref{sec:TIPE12}, qui est une reformulation de~\cite{guyeuxphd},
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,
-\part{Applications à la génération de nombres pseudo aléatoires}
+\part{Applications à la génération de nombres
+pseudo-aléatoires}
\chapter{Caractérisation des générateurs chaotiques}\label{chap:PRNG:chao}
\input{15RairoGen}
% respectively an element of some $E_i$ and a matrix of elements in some $E_i$.
% The components may be updated (in a random order) according to a
% strategy $s$, as in the synchronous mode.
-Dans le mode asynchrone, a chaque itération $t$, chaque composant peut
+Dans le mode asynchrone, à chaque itération $t$, chaque composant peut
mettre à jour son état en
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
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$
+Soit $(D^{t})^{t \in \Nats}$ la suite de matrices de taille $n \times n$
dont chaque élément $D_{ij}^{t}$ représente la date (inférieure ou égale à $t$)
à laquelle la valeur $x_j$ produite par le composant $j$ devient
disponible au composant $i$.
On considère que le délai entre l'émission par $j$ et la réception par $i$,
-défini par $\delta_{ij}^t = t - D_{ij}^{t}$ est borné par une constante $\delta_0$ pour tous les $i$, $j$.
+défini par $\delta_{ij}^t = t - D_{ij}^{t}$, est borné par une constante $\delta_0$ pour tous les $i$, $j$.
Le \emph{mode des itérations généralisées asynchrone}
est défini pour chaque $i
\in \{1,\ldots,n\}$ et chaque $t=0,1,2,...$ par:
Sinon les itérations sont dites \emph{divergentes}.
De plus, si $ (x^{(t)})^{t \in \mathbb{N}}$ défini selon l'équation
\Equ{eq:async} satisfait \Equ{eq:conv} pour tous les $x^{(0)}
-\in E$, pour toutes les stratégies pseudo périodiques
+\in E$, pour toutes les stratégies pseudo-périodiques
$s$ et pour toutes les matrices de dates,
$(D^{(t)})^{t \in \Nats}$, alors les itérations de $f$ sont
\emph{universellement convergentes}.
Un extrait du graphe des itérations unaires est donné à
la~\Fig{fig:mix:xplchaoFig}. Les libellés des arcs correspondent aux éléments
activés. Les itérations unaires ne convergent pas pour la stratégie
-pseudo périodique donnée à l'équation~\Equ{eq:pseudo}:
+pseudo-périodique donnée à l'équation~\Equ{eq:pseudo}:
le système peut infiniment boucler entre 11 et 3, entre 15 et 7.
Comme les itérations unaires ne convergent pas pour certaines stratégies,
\begin{theorem}\label{th:cvg}
Soit une fonction $f$ possédant un unique point fixe $x^*$ et une stratégie
- pseudo périodique $s$.
+ pseudo-périodique $s$.
Si les itérations synchrones convergent vers $x^*$ pour cette stratégie,
alors les itérations mixtes à délai uniforme convergent aussi vers $x^*$
pour cette stratégie.
\subsection{Le mode unaire asynchrone}
\label{sec:evalasync}
-En terme de durée de convergence, ce mode peut être vu comme un
+En termes de durée de convergence, ce mode peut être vu comme un
cas particulier du mode mixte où toutes les classes sont des singletons.
La borne minimale peut donc s'exprimer comme:
\begin{equation}
-L'étude de convergence de systèmes dynamiques discrets est simple à vérifier
+Sur des petits exemples, 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és, 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 mixtes prenant de plus en compte les délais.
convergent vers $2$ soit $(010)$; celles initialisées avec
$x^0=7$ restent en 7.
Pour les modes unaires ou généralisés avec une
-stratégie pseudo périodique, on a des comportements qui dépendent
+stratégie pseudo-périodique, on a des comportements qui dépendent
de la configuration initiale:
\begin{itemize}
\item initialisées avec 7, les itérations restent en 7;
}
\end{lstlisting}
\end{tiny}
-\caption{Process scheduler pour la stratégie pseudo périodique.
+\caption{Process scheduler pour la stratégie pseudo-périodique.
\label{fig:scheduler}}
\end{minipage}
\begin{minipage}[h]{.30\linewidth}
\subsection{La stratégie}\label{sub:spin:strat}
-Regardons comment une stratégie pseudo périodique peut être représentée en PROMELA.
+Regardons comment une stratégie pseudo-périodique peut être représentée en PROMELA.
Intuitivement, un process \verb+scheduler+ (comme représenté à la {\sc Figure}~\ref{fig:scheduler})
est itérativement appelé pour construire chaque $s^t$ représentant
les éléments possiblement mis à jour à l'itération $t$.
}
\end{lstlisting}
\end{tiny}
-\caption{Mise à jour des éléments.}\label{fig:proc}
+\caption{Mise à jour des éléments}\label{fig:proc}
\end{minipage}\hfill%
%\end{figure}
%\begin{figure}
}
\end{lstlisting}
\end{tiny}
-\caption{Application de la fonction $f$.}\label{fig:p}
+\caption{Application de la fonction $f$}\label{fig:p}
\end{minipage}
\end{figure}
\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é (
- c'est l'instruction \verb+skip+) ou n'est pas utile; ce dernier cas apparaît
+ \item depuis la perspective de $j$ la valeur de $i$ peut ne pas avoir changé (c'est l'instruction \verb+skip+) ou n'est pas utile; ce dernier cas apparaît
lorsqu'il n'y a pas d'arc de $i$ à $j$ dans le graphe d'incidence, \textit{i.e.}, lorsque
la valeur de \verb+is_succ+ qui est calculée par \verb+hasnext(i,j)+ est 0;
dans ce cas, la valeur de \verb+Xd[j].v[i]+ n'est pas modifiée;
est de stocker les valeurs de $x$ (représenté
dans le modèle par \verb+Xp+) dans le canal \verb+channels+.
Il permet au model-checker SPIN d'exécuter
-le modèle PROMELA comme s'il pouvait y avoir des délais entre processus
+le modèle PROMELA comme s'il pouvait y avoir des délais entre processus.
Il y a deux cas différents pour la valeur de $X_{j}$:
\begin{itemize}
\item soit elle est \og perdue\fg{}, \og oubliée\fg{} pour permettre à $i$ de ne pas tenir compte d'une
Rappelons tout d'abord que les variables \verb+X+ et \verb+Xp+
contiennent respectivement la valeur de $x$ avant et après la mise à jour.
Ainsi, si l'on effectue une initialisation non déterministe de
-\verb+Xp+ et si l'on applique une stratégie pseudo périodique,
+\verb+Xp+ et si l'on applique une stratégie pseudo-périodique,
il est nécessaire et suffisant
de prouver la formule temporelle linéaire (LTL) suivante:
\begin{equation}
\section{Correction et complétude de la démarche}\label{sec:spin:proof}
Cette section présente les théorèmes
-de correction et de complétude de l'approche.
+de correction et de complétude de l'approche
(Théorèmes~\ref{Theo:sound} et~\ref{Theo:completeness}).
Toutes les preuves sont déplacées en
-annexes~\ref{anx:promela}.
+annexe~\ref{anx:promela}.
\begin{restatable}[Correction de la traduction vers Promela]{theorem}{promelasound}
Cette section donne tout d'abord quelques mesures de complexité de l'approche
puis présente ensuite les expérimentations issues de ce travail.
-\begin{theorem}[Nombre d'états ]
+\begin{theorem}[Nombre d'états]
Soit $\phi$ un modèle de système dynamique discret à ${\mathsf{N}}$ éléments, $m$
arcs dans le graphe d'incidence
et $\psi$ sa traduction en PROMELA. Le nombre de configurations
- de l'exécution en SPIN de $\psi$ est bornée par $2^{m(\delta_0+1)+n(n+2)}$.
+ de l'exécution en SPIN de $\psi$ est borné par $2^{m(\delta_0+1)+n(n+2)}$.
\end{theorem}
\begin{proof}
Une configuration est une évaluation des variables globales.
pour prouver formellement sa convergence universelle.
On peut remarquer que SPIN n'impose l'équité faible qu'entre les process
-alors que les preuves des deux théorèmes précédentes reposent sur le fait que
+alors que les preuves des deux théorèmes précédents reposent sur le fait que
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
-La propriété de régularité des fonctions chaotiques est à l'origine du marquage de documents numériques: de tout média, même tronqué, on peut réextraire la
-marque.
+La propriété de transitivité des fonctions chaotiques est à l'origine du marquage de documents numériques: grâce à cette propriété, la marque est diffusée
+sur tout le support. Ainsi, de tout média, même tronqué,
+on peut la réextraire.
Dans ce chapitre, le processus d'embarquement d'un message dans
un média est formalisé en section~\ref{sec:watermarking:formulation}.
-La sécurité des approches de watermarking est étudiée selon deux approches:
-l'approche probabiliste (section~\ref{sec:watermarking:security:probas})
-et l'approche chaotique (section~\ref{sec:watermarking:security:chaos}).
+La sécurité des approches de watermarking est étudiée selon deux critères:
+probabiliste d'une part (section~\ref{sec:watermarking:security:probas})
+et chaotique (section~\ref{sec:watermarking:security:chaos}) d'autre part.
Une proposition d'embarquement dans le domaine fréquentiel est abordée
en section~\ref{sec:watermarking:frequentiel}.
propose une solution à ce problème.
Les trois premières sections de ce chapitre sont une reformulation
-du chapitre 22 de~\cite{guyeux10}. Elles ont été publiées à~\cite{bcg11:ij}.
+du chapitre 22 de~\cite{guyeuxphd}. Elles ont été publiées à~\cite{bcg11:ij}.
L'extension a quant à elle été publiée dans~\cite{bcfg+13:ip}.
C'est l'objectif de l'algorithme présenté dans cette section et introduit
dans~\cite{fgb11:ip}.
Pour des raisons de lisibilité, il n'est pas
-présenté pas dans le formalisme de la première section et
+présenté dans le formalisme de la première section et
est grandement synthétisé.
Il a cependant été prouvé comme étant chaos-sécure~\cite{fgb11:ip}.
Commençons par quelques conventions de notations:
\begin{itemize}
-\item $\mathbb{S}_\mathsf{k}$ est l'ensemble des stratégies unaire sur $[k]$;
+\item $\mathbb{S}_\mathsf{k}$ est l'ensemble des stratégies unairesx sur $[k]$;
\item $m^0 \in \mathbb{B}^{\mathsf{P}}$ est un vecteur de $\mathsf{P}$ bits
représentant la marque;
\item comme précédemment,
-\begin{xpl}
-On reprend notre exemple illustratif
-détaillé à la page~\pageref{xpl:1} avec sa table
-d'images (\textsc{Table}~\ref{table:xpl:images}).
-La \textsc{Figure}~\ref{fig:xpl:graphs} donne les trois graphes d'itérations
-associés à $f$.
-\begin{figure}%[ht]
+\begin{figure}[ht]
\begin{center}
\subfigure[$\textsc{gis}(f)$]{
- \begin{minipage}{0.33\textwidth}
+ \begin{minipage}{0.3\textwidth}
\begin{center}
\includegraphics[scale=0.4]{fsig}
\end{center}
\label{fig:fsig}
}
\subfigure[$\textsc{giu}(f)$]{
- \begin{minipage}{0.33\textwidth}
+ \begin{minipage}{0.3\textwidth}
\begin{center}
\includegraphics[scale=0.4]{faig}
\end{center}
\label{fig:faig}
}
\subfigure[$\textsc{gig}(f)$]{
- \begin{minipage}{0.33\textwidth}
+ \begin{minipage}{0.3\textwidth}
\begin{center}
\includegraphics[scale=0.4]{fgig}
\end{center}
On remarque le cycle $((101,111),(111,011),(011,101))$
à la \textsc{Figure}~(\ref{fig:fsig}).}
\end{figure}
+
+\begin{xpl}
+On reprend notre exemple illustratif
+détaillé à la page~\pageref{xpl:1} avec sa table
+d'images (\textsc{Table}~\ref{table:xpl:images}).
+La \textsc{Figure}~\ref{fig:xpl:graphs} donne les trois graphes d'itérations
+associés à $f$.
\end{xpl}
sont les points fixes de $f$.
Ainsi pour chaque $x\in \Bool^{\mathsf{N}}$, il existe au moins un chemin
depuis $x$ qui atteint un attracteur.
-Ainsi tout graphe d'itérations contient toujours au moins un attracteur.
+Tout graphe d'itérations contient donc toujours au moins un attracteur.
\end{theorem}
Ainsi la seconde ligne (resp. la troisième ligne) de $B(f)$ est $1~0~1$ (resp. est $1~1~1$).
La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complète.
-\begin{figure}%[ht]
+\begin{figure}[ht]
\begin{center}
\subfigure[Matrice jacobienne]{
- \begin{minipage}{0.90\textwidth}
+ \begin{minipage}{0.65\textwidth}
+ \begin{scriptsize}
\begin{center}
$
\left(
\right)
$
\end{center}
- \end{minipage}
+ \end{scriptsize}
+ \end{minipage}
\label{fig:f:jacobienne}
}
- ~
- \subfigure[Graphe d'interaction]{
- \begin{minipage}{0.45\textwidth}
- \begin{center}
- \includegraphics[scale=0.5]{gf}
- \end{center}
- \label{fig:f:interaction}
- \end{minipage}
- }
-
- \subfigure[Matrice d'incidence]{
- \begin{minipage}{0.45\textwidth}
+ \subfigure[Matrice d'incidence]{
+ \begin{minipage}{0.25\textwidth}
\begin{center}
$
B(f) =
\label{fig:f:incidence}
\end{minipage}
}
+
+ ~
+ \subfigure[Graphe d'interaction]{
+ \begin{minipage}{0.45\textwidth}
+ \begin{center}
+ \includegraphics[scale=0.5]{gf}
+ \end{center}
+ \label{fig:f:interaction}
+ \end{minipage}
+ }
\end{center}
\caption{Représentations des dépendances entre les éléments
de la fonction
\section{Présentation de l'approche}
-Le diagramme de flux donnés à la Fig.~\ref{fig:sch} résume l'approche
+Le diagramme de flux donné à la Fig.~\ref{fig:sch} résume l'approche
du schéma STABYLO (pour STeganography with Adaptive, Bbs, binarY embedding
at LOw cost). L'embarquement est synthétisé à la Fig.~\ref{fig:sch:emb} et
l'extraction à la Fig.~\ref{fig:sch:ext}.
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.
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
+itérativement 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
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
à gauche la valeur des variations horizontales de $\dfrac{\partial P}{\partial x}$:
-Le pixel central $(0,0)$ reçoit exactement la valeur
+le pixel central $(0,0)$ reçoit exactement la valeur
$\dfrac{P(0,2)-P(0,1)}{1} - \dfrac{P(0,1)-P(0,0)}{1}$,
qui est une approximation de
$\dfrac{\partial P}{\partial x}(0,1)$ et non de
La section suivante propose une autre approche pour calculer les lignes de niveau avec une précision accrue.
\section{Des noyaux pour des lignes de niveau}\label{sec:second}
-On ne restreint pas aux noyaux de taille fixe (comme $3\times3$ or $5 \times 5$
+On ne se
+restreint pas aux noyaux de taille fixe (comme $3\times3$ or $5 \times 5$
dans les schémas précédents). Au contraire, on considère des noyaux de taille variable
$(2n+1)\times (2n+1)$, $n \in \{1,2,\dots,N\}$, où
$N$ est un paramètre de l'approche.
et de
$\dfrac{\partial^2 P}{\partial y^2}$.
-La section suivante étudie la pertinence d'interpoler une image par un polynome
+La section suivante étudie la pertinence d'interpoler une image par un polynôme
lorsqu'on cherche à obtenir ces dérivées secondes.
\section{Interpolation polynomiale pour le calcul de la matrice hessienne}\label{sec:poly}
Soit $P(x,y)$ la valeur du pixel $(x,y)$ et soit $n$, $1 \le n \le N$,
-tel que l'objectif est de trouver un polynome d'interpolation dans la fenêtre de taille
+tel que l'objectif est de trouver un polynôme d'interpolation dans la fenêtre de taille
$(2n+1)\times(2n+1)$ dont le pixel central a pour indice $(0,0)$.
Il existe un unique polynôme $L : \R\times \R \to \R$
de degré $(2n+1)\times(2n+1)$ tel que $L(x,y)=P(x,y)$ pour chaque pixel
-$(x,y)$ de cette fenêtre et ce polynome est défini par
+$(x,y)$ de cette fenêtre et ce polynôme est défini par
\begin{equation}
\begin{array}{l}
L(x,y) =
Ici c'est cependant l'ensemble des 10000 images qui a été utilisé pour évaluer
la sécurité.
C'est aussi les caractéristiques SRM et Ensemble Classifier qui ont été utilisées
-pour évaluer la sécurité de l'approche..
+pour évaluer la sécurité de l'approche.
Quatre taux d'embarquement 0.1, 0.2, 0.3 et 0.4
ont été retenus. Pour chaque expérience,
l'aire sous la courbe de ROC (AUC),
