From ab1271f8b9509a86f3434c2389be47fe3a1c4d04 Mon Sep 17 00:00:00 2001 From: couchot Date: Wed, 9 Nov 2016 17:03:17 +0100 Subject: [PATCH 1/1] =?utf8?q?apr=C3=A8s=20remarques=20tof?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- 12TIPE.tex | 14 ++++----- 14Secrypt.tex | 15 ++++----- 15RairoGen.tex | 24 +++++++-------- 15TSI.tex | 2 +- ahmad.tex | 8 ++--- annexePromelaProof.tex | 4 +-- chaosANN.tex | 9 ++++-- devaney.tex | 3 +- intro.tex | 11 ++++--- main.tex | 70 +++++++++++++++++++++--------------------- mixage.tex | 14 ++++----- modelchecking.tex | 32 +++++++++---------- oxford.tex | 17 +++++----- sdd.tex | 55 +++++++++++++++++---------------- stabylo.tex | 4 +-- stegoyousra.tex | 13 ++++---- 16 files changed, 153 insertions(+), 142 deletions(-) diff --git a/12TIPE.tex b/12TIPE.tex index e54ed79..4bcec9f 100644 --- a/12TIPE.tex +++ b/12TIPE.tex @@ -105,17 +105,17 @@ les ensembles $\mathcal{T}$ des fonctions topologiquement transitives, $\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. diff --git a/14Secrypt.tex b/14Secrypt.tex index 5e4cafc..84b5302 100644 --- a/14Secrypt.tex +++ b/14Secrypt.tex @@ -20,10 +20,11 @@ une distribution uniforme est étudiée théoriquement et pratiquement à la 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 @@ -49,7 +50,7 @@ On cherche ainsi toutes les matrices $M$ de taille $2^{\mathsf{N}}\times 2^{\ma 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$, @@ -407,7 +408,7 @@ Enfin, les auteurs de~\cite{ZanSup04} présentent une extension de l'algorithme 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 @@ -620,7 +621,7 @@ $\textit{fair}\leftarrow\emptyset$\; } \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} @@ -683,7 +684,7 @@ généralisées. 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. diff --git a/15RairoGen.tex b/15RairoGen.tex index a57e19f..38920d8 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -8,7 +8,7 @@ comme un générateur aléatoire. 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. @@ -17,7 +17,7 @@ section~\ref{prng:unaire:chaos}. 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} @@ -44,8 +44,8 @@ return $x$\; \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$; @@ -56,7 +56,7 @@ la fonction $F_{f_u}$ (équation~\ref{eq:iterations:unaires} 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é. @@ -139,7 +139,7 @@ et les chaînes de Markov. Montrons sur un exemple jouet à deux éléments que ce théorème permet de vérifier si la sortie d'un générateur de -nombres pseudo aléatoires est uniformément distribuée ou non. +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)$. @@ -149,7 +149,7 @@ Leurs graphes d'itérations 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$. @@ -283,10 +283,10 @@ Alors d'après le théorème~\ref{th}, 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 @@ -303,7 +303,7 @@ On énonce directement le théorème suivant dont la preuve est donnée en annex 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. @@ -325,7 +325,7 @@ Expliquons enfin comment a été calculé le nombre de la troisième 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 @@ -431,7 +431,7 @@ $\mathcal{F}_{16}$ &14, 15, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 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. diff --git a/15TSI.tex b/15TSI.tex index 670df80..7f33772 100644 --- a/15TSI.tex +++ b/15TSI.tex @@ -9,7 +9,7 @@ Dans le schéma généralisé, à la $t^{\textrm{ème}}$ itération, 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 \[ diff --git a/ahmad.tex b/ahmad.tex index 3188a74..9a70e96 100644 --- a/ahmad.tex +++ b/ahmad.tex @@ -15,7 +15,7 @@ Une attaque qui modifierait aléatoirement de manière faible ces positions 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. @@ -23,7 +23,7 @@ Ce chapitre présente une application de STDM au marquage de documents PDFs. 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}. @@ -95,7 +95,7 @@ pour ce $L$ donné. 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]$. @@ -127,7 +127,7 @@ marque. 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]$. diff --git a/annexePromelaProof.tex b/annexePromelaProof.tex index ade9df0..3c0724c 100644 --- a/annexePromelaProof.tex +++ b/annexePromelaProof.tex @@ -14,7 +14,7 @@ du chapitre~\ref{chap:promela}. \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} @@ -287,7 +287,7 @@ Grâce à~\Equ{eq:correct_retrieve} déjà prouvée, on peut conclure la preuve. 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 diff --git a/chaosANN.tex b/chaosANN.tex index a818675..143ce23 100644 --- a/chaosANN.tex +++ b/chaosANN.tex @@ -14,7 +14,9 @@ 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 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 @@ -39,7 +41,8 @@ chaotique selon Devanay. La section~\ref{S3} présente l'approche duale de vérification si un réseau de neurones est chaotique ou non. La section~\ref{sec:ann:approx} s'intéresse à étudier pratiquement si un réseau de -neurones peut approximer des ité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}. @@ -419,7 +422,7 @@ 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 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. diff --git a/devaney.tex b/devaney.tex index 2a2a167..850b55c 100644 --- a/devaney.tex +++ b/devaney.tex @@ -1,7 +1,8 @@ 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} diff --git a/intro.tex b/intro.tex index d2bbf98..10072d3 100644 --- a/intro.tex +++ b/intro.tex @@ -4,7 +4,7 @@ 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 @@ -46,9 +46,10 @@ simulation a été prouvée comme exhaustive. 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 @@ -128,7 +129,7 @@ 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 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 @@ -184,7 +185,7 @@ depuis mon intégration en tant qu'enseignant chercheur. \\ %\hline %journaux - +\cite{ccgh16} & % conf inter \cite{bcgr11:ip,bcgw11:ip,cds12:ip,chgw+14:oip,fccg15:ip} diff --git a/main.tex b/main.tex index 47cc2fc..1cad5ec 100644 --- a/main.tex +++ b/main.tex @@ -56,7 +56,7 @@ %%-------------------- %% Set the University where HDR was made -\hdrpreparedin{l'Université de Franche-Comté} +\hdrpreparedin{Université Bourgone Franche-Comté} %%-------------------- @@ -71,7 +71,7 @@ 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 +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 @@ -85,42 +85,41 @@ discrete way.} %%-------------------- %% 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. @@ -243,8 +242,8 @@ 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 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. @@ -268,7 +267,7 @@ 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 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, @@ -309,7 +308,8 @@ de telles fonctions. -\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} diff --git a/mixage.tex b/mixage.tex index 4045262..973305a 100644 --- a/mixage.tex +++ b/mixage.tex @@ -48,7 +48,7 @@ et les quatre derniers éléments (15 est 01111). % 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 @@ -56,12 +56,12 @@ du temps d'acheminement de celles-ci. On parle de latence, de délai. 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: @@ -90,7 +90,7 @@ t \geq t_0 \Rightarrow x^{t}=x^{t_0}). 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}. @@ -150,7 +150,7 @@ qu'il converge vers le point fixe correspondant à l'entier 19. 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, @@ -227,7 +227,7 @@ On a alors le théorème suivant. \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. @@ -419,7 +419,7 @@ ascendants pour converger. On a dans ce cas: \subsection{Le mode unaire asynchrone} \label{sec:evalasync} -En terme de durée de convergence, ce mode peut être vu comme un +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} diff --git a/modelchecking.tex b/modelchecking.tex index 96a8586..dd4bf2e 100644 --- a/modelchecking.tex +++ b/modelchecking.tex @@ -1,7 +1,8 @@ -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. @@ -95,7 +96,7 @@ avec $x^0 \neq 7$ soit $(111)$ 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; @@ -300,7 +301,7 @@ active proctype scheduler(){ } \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} @@ -338,7 +339,7 @@ ces notions est traduite vers un modèle PROMELA. \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$. @@ -405,7 +406,7 @@ active proctype update_elems(){ } \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} @@ -425,7 +426,7 @@ inline F(){ } \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} @@ -540,8 +541,7 @@ Il y a deux cas. \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; @@ -554,7 +554,7 @@ Les valeurs des éléments sont ajoutées dans ce canal au travers de la fonctio 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 @@ -595,7 +595,7 @@ dynamique à ${\mathsf{N}}$ éléments est universellement convergent. 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} @@ -617,10 +617,10 @@ disposer de plusieurs points fixes. \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} @@ -651,11 +651,11 @@ annexes~\ref{anx:promela}. 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. @@ -679,7 +679,7 @@ La méthode détaillée ici a pu être appliquée sur l'exemple 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 diff --git a/oxford.tex b/oxford.tex index 5cc17c0..b440d77 100644 --- a/oxford.tex +++ b/oxford.tex @@ -1,10 +1,11 @@ -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}. @@ -16,7 +17,7 @@ l'image marquée. La section~\ref{sec:watermarking:extension} 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}. @@ -493,7 +494,7 @@ de retrouver le contenu de la marque à partir de l'image marquée. 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}. @@ -501,7 +502,7 @@ 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, diff --git a/sdd.tex b/sdd.tex index ad52238..7a31f0d 100644 --- a/sdd.tex +++ b/sdd.tex @@ -200,17 +200,11 @@ des itérations unaires. -\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} @@ -218,7 +212,7 @@ associés à $f$. \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} @@ -226,7 +220,7 @@ associés à $f$. \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} @@ -243,6 +237,13 @@ x_1 + x_2 + x_3)$.\label{fig:xpl:graphs} 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} @@ -280,7 +281,7 @@ 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 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} @@ -412,10 +413,11 @@ $x_1$ et de $x_3$ 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( @@ -451,21 +453,12 @@ La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complèt \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) = @@ -481,6 +474,16 @@ La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complèt \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 diff --git a/stabylo.tex b/stabylo.tex index 5c9bce5..7a3fad2 100644 --- a/stabylo.tex +++ b/stabylo.tex @@ -38,7 +38,7 @@ Ce chapitre détaille les clefs de ce schéma \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}. @@ -111,7 +111,7 @@ 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. 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 diff --git a/stegoyousra.tex b/stegoyousra.tex index d931298..76a70fb 100644 --- a/stegoyousra.tex +++ b/stegoyousra.tex @@ -252,7 +252,7 @@ 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 à 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 @@ -262,7 +262,8 @@ que les pixels du coin supérieur droit, en perdant toutes les autres informatio 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. @@ -375,17 +376,17 @@ $\dfrac{\partial^2 P}{\partial y \partial x}$ 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) = @@ -658,7 +659,7 @@ Comme dans ce qui précède, la base du challenge BOSS a été retenue. 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), -- 2.39.5