From d4e1bfa4290a182013268daf63d78c1f4fce5b55 Mon Sep 17 00:00:00 2001 From: couchot Date: Tue, 13 Sep 2016 09:19:45 +0200 Subject: [PATCH] ajout d'intro et de conclusion --- annexePreuveGrayEquilibre.tex | 163 ++++++++++++++++++++++++++++++++++ conclusion.tex | 160 +++++++++++++++++++++++++++++++++ intro.tex | 16 ++++ main.tex | 54 ++--------- 4 files changed, 348 insertions(+), 45 deletions(-) create mode 100644 annexePreuveGrayEquilibre.tex create mode 100644 conclusion.tex create mode 100644 intro.tex diff --git a/annexePreuveGrayEquilibre.tex b/annexePreuveGrayEquilibre.tex new file mode 100644 index 0000000..2d351e7 --- /dev/null +++ b/annexePreuveGrayEquilibre.tex @@ -0,0 +1,163 @@ +\theograyequilibre* + + + + +\begin{proof} +La preuve de ce théorème s'effectue par induction sur $\mathsf{N}$. +On peut vérifier aisément que ce théorème est établi pour les +deux plus petites valeurs paires et impaires, \textit{i.e.} pour +$\mathsf{N}=3$ et $\mathsf{N}=4$. + +Pour le cas initial où $\mathsf{N}=3$, \textit{i.e.} $\mathsf{N-2}=1$ +on a: $S_1=1,1$, $l=2$, $u_0 = \emptyset$ et $v=\emptyset$. +Ainsi, l'algorithme produit +$U= 1,2,1$, $V = 3$, $W= 2, 1, 1,3$ et $W' = 1,2,1,3$. +Finalement, $S_3=1,2,1,3,1,2,1,3$ qui vérifie le théorème. + +Pour le cas initial où $\mathsf{N}=4$, \textit{i.e.} $\mathsf{N-2}=2$ +on a: $S_1=1,2,1,2$, $l=4$, +$u_0,u_1,u_2 = \emptyset,\emptyset,\emptyset$ et $v=\emptyset$. +Ainsi, l'algorithme produit +$U= 1,3,2,3,4,1,4,3,2$, $V = 4$, $W= 3, 1, 2, 1,2, 4$ et $W' = 1, 3, 2, 1,2, 4 $. +Finalement, $S_4 = 2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4$ et le code est +totalement équilibré. + +Pour le cas inductif, on définit tout d'abord quelques variables. +Soit $c_{\mathsf{N}}$ (resp. $d_{\mathsf{N}}$) le nombre d'éléments dont le nombre +de transitions est exactement $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$). +Ces deux variables sont caractérisées par le système: + +\[ +\left\{ +\begin{array}{lcl} +c_{\mathsf{N}} + d_{\mathsf{N}} & = & \mathsf{N} \\ +c_{\mathsf{N}}a_{\mathsf{N}} + d_{\mathsf{N}}(a_{\mathsf{N}}+2) & = & 2^{\mathsf{N}} +\end{array} +\right. +\Leftrightarrow +\left\{ +\begin{array}{lcl} +d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N}} -\mathsf{N}.a_{\mathsf{N}}}{2} \\ +c_{\mathsf{N}} &= &\mathsf{N} - d_{\mathsf{N}} +\end{array} +\right. +\] + +Puisque $a_{\mathsf{N}}$ est pair, $d_{\mathsf{N}}$ est un entier. +Prouvons d'abord que $c_{\mathsf{N}}$ et $d_{\mathsf{N}}$ sont des entiers +positifs. +Soit $q_{\mathsf{N}}$ et $r_{\mathsf{N}}$, définis respectivement +comme étant le quotient et le reste dans la division euclidienne de +$2^{\mathsf{N}}$ par $2\mathsf{N}$, \textit{i.e.} +$2^{\mathsf{N}} = q_{\mathsf{N}}.2\mathsf{N} + r_{\mathsf{N}}$, avec $0 \le r_{\mathsf{N}} <2\mathsf{N}$. +Tout d'abord, l'entier $r$ est pair puisque $r_{\mathsf{N}}$ est un multiple de 2: +$ 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 +$0 \le d_{\mathsf{N}} <\mathsf{N}$. +La preuve pour $c_{\mathsf{N}}$ est évidente. + + +Pour chaque $i$, $1 \le i \le \mathsf{N}$, soit $zi_{\mathsf{N}}$ (resp. $ti_{\mathsf{N}}$ et $bi_{\mathsf{N}}$) le nombre d'occurrences de l'élément +$i$ dans la séquence $u_0, \dots, u_{l-2}$ +(resp. dans les séquences $s_{i_1}, \dots , s_{i_l}$ et $v$) +à l'étape (\ref{item:nondet}) de l'algorithme. + +En raison de la définition de $u'$ à l'étape~(\ref{item:u'}), +$3.zi_{\mathsf{N}} + ti_{\mathsf{N}}$ est le nombre + d'occurrences de $i$ dans la séquence $U$. +Il est évident que le nombre d'occurrences de $i$ dans la séquence $V$ est +$2bi_{\mathsf{N}}$ en raison de l'étape (\ref{item:VW}). +On a ainsi le système suivant: +$$ +\left\{ +\begin{array}{lcl} +3.zi_{\mathsf{N}} + ti_{\mathsf{N}} + 2.bi_{\mathsf{N}} + \textit{TC}_{\mathsf{N}-2}(i) &= &\textit{TC}_{\mathsf{N}}(i) \\ +zi_{\mathsf{N}} + ti_{\mathsf{N}} + bi_{\mathsf{N}} & =& \textit{TC}_{\mathsf{N}-2}(i) +\end{array} +\right. +\qquad +\Leftrightarrow +$$ + +\begin{equation} +\left\{ +\begin{array}{lcl} +zi_{\mathsf{N}} &= & +\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) - bi_{\mathsf{N}}}{2}\\ +ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}-bi_{\mathsf{N}} +\end{array} +\right. +\label{eq:sys:zt1} +\end{equation} + +Dans ce système de 2 équations à trois inconnues, on pose $b_i=0$. +Puisque $\textit{TC}_{\mathsf{N}}$ est pair (égal à $a_{\mathsf{N}}$ +ou à $a_{\mathsf{N}}+2$), l'inconnue $zi_{\mathsf{N}}$ est donc un entier. +Prouvons alors que le système résultant admet toujours +une solution positive pour $z_i$ et pour $t_i$ telle $0 \le z_i, t_i \le \textit{TC}_{\mathsf{N}-2}(i)$ et telle que leur somme est égale à + $\textit{TC}_{\mathsf{N}-2}(i)$. +On remarque que cette contrainte est toujours établie si le système admet une solution. On a donc le système suivant: + + + +\begin{equation} +\left\{ +\begin{array}{lcl} +zi_{\mathsf{N}} &= & +\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) }{2}\\ +ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}} +\end{array} +\right. +\label{eq:sys:zt2} +\end{equation} + +La définition de $\textit{TC}_{\mathsf{N}}(i)$ dépend de la valeur de $\mathsf{N}$. Pour $3 \le N \le 7$, on définit celles-ci comme suit: + +\begin{eqnarray*} +\textit{TC}_{3} & = & [2,2,4] \\ +\textit{TC}_{5} & = & [6,6,8,6,6] \\ +\textit{TC}_{7} & = & [18,18,20,18,18,18,18] \\ +\\ +\textit{TC}_{4} & = & [4,4,4,4] \\ +\textit{TC}_{6} & = & [10,10,10,10,12,12] \\ +\end{eqnarray*} +Il n'est pas difficile de vérifier que dans chacun des cas précédents, +le système admet bien une solution. + +Pour $N \ge 8$, on définit $\textit{TC}_{\mathsf{N}}(i)$ comme suit: +\begin{equation} +\textit{TC}_{\mathsf{N}}(i) = \left\{ +\begin{array}{l} +a_{\mathsf{N}} \textrm{ si } 1 \le i \le c_{\mathsf{N}} \\ +a_{\mathsf{N}}+2 \textrm{ si } c_{\mathsf{N}} +1 \le i \le c_{\mathsf{N}} + d_{\mathsf{N}} +\end{array} +\right. +\label{eq:TCN:def} +\end{equation} + + +On a ainsi +\[ +\begin{array}{rcl} +\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) +&\ge& +a_{\mathsf{N}} - 2(a_{\mathsf{N}-2}+2) \\ +&\ge& +\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}} +-2 \left( \frac{2^{\mathsf{N-2}}-r_{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\ +&\ge& +\frac{2^{\mathsf{N}}-2N}{\mathsf{N}} +-2 \left( \frac{2^{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\ +&\ge& +\frac{(\mathsf{N} -2).2^{\mathsf{N}}-2N.2^{\mathsf{N-2}}-6N(N-2)}{\mathsf{N.(N-2)}}\\ +\end{array} +\] + +Une simple étude de variation de la fonction $t:\R \rightarrow \R$ telle que +$x \mapsto t(x) = (x -2).2^{x}-2x.2^{x-2}-6x(x-2)$ montre que +sa dérivée est strictement positive pour $x \ge 6$ et que $t(8)=224$. +L'entier $\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)$ est ainsi positif pour chaque $\mathsf{N} \ge 8$, ce qui termine la preuve. +\end{proof} diff --git a/conclusion.tex b/conclusion.tex new file mode 100644 index 0000000..e2eac3e --- /dev/null +++ b/conclusion.tex @@ -0,0 +1,160 @@ + +\subsection{Synthèses des contributions} + +Les principales contributions gravitent autour des mathématiques discrètes et plus particulièrement +les itérations de systèmes dynamiques discrets. + +Pour chacun des modes et des conditions de synchronisme, +il existe des critères (suffisants) de convergence +globale ou locale. + +Nous avons formalisé le mode des +\emph{itérations mixtes} (introduit par Pr. J. M. Bahi en 2005 notamment) +qui combine synchronisme et asynchronisme (chapitre~\ref{chap:sdd}) +et leur extension les \emph{itérations mixtes avec délais uniformes}. +Nous avons pu ainsi énoncer puis démontrer des résultats +établissant que pour des conditions classiques de convergence des itérations +synchrones, les itérations mixtes à délai uniforme +convergent aussi vers le même point fixe. + +Nous avons de plus démontré (chapitre~\ref{chap:promela}) qu'on peut simuler +des SDDs selon tous les modes avec l'outil SPIN de \emph{Model-Checking} pour établir +formellement leur convergence (ou pas). +Nous avons énoncé puis prouvé ensuite la correction et la complétude de la démarche. +Des données pratiques comme la complexité et des synthèses d'expérimentation +ont aussi été fournies. + +Nous nous sommes ensuite intéressés à l'étude du problème dual +de l'étude de divergence d'un SDD. +Nous avons proposé plusieurs méthodes de construction de +fonctions permettant d'obtenir des itérations chaotiques. +La première non naïve est basée sur des +conditions suffisantes sur le graphe d'interaction à $\mathsf{N}$ sommets +(chapitre~\ref{chap:carachaos}). +Une seconde méthode plus efficace permet en plus de disposer d'une chaîne de Markov doublement +stochastique et s'appuie sur les cycles hamiltoniens du graphe des +itérations. Elle est présentée au chapitre~\ref{chap:PRNG:gray}. +Ces méthodes ont permis d'étendre à l'infini la classe des fonctions +dont les itérations sont chaotiques. + +Nous de plus entrepris d'étudier ces itérations et plus particulièrement leur +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 +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 +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. +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 trouver un majorant du nombre d'itérations suffisant à +l'obtention d'une distribution uniforme + +Nous avons renforcé la thématique de marquage de document numérique de l'équipe AND en +embarquant ces fonctions dans des outils de watermarking. +Nous avons participé à la formalisation de la méthode de +marquage de médias (chapitre~\ref{chap:watermarking}) et particularisé +ceci à des images numériques fournissant un +nouveau contexte pour l'étude théorique et mathématique d'algorithmes de marquage. +Des instances de ces algorithmes ont été présentées en sélectionnant de manière +pertinente les fonctions à itérer pour garantir une robustesse +élevée. + +D'autre méthodes de watermarking ont été investies (mais plus dans le domaine discret), +particulièrement celles basées sur la Quantization Index Modulation (QIM), méthodes +étant supposées comme les plus robustes. Nos principales contributions +sur ce travail ont été +d'intégrer ceci à du marquage de document PDF puis de +présenter ce problème comme un problème d'optimisation (chapitre~\ref{chap:watermarking:pdf}). + +Nous avons de plus conçu l'algorithme STABYLO (chapitre~\ref{chap:stabylo}) +qui est un schéma de stéganographie basé sur l'enfouissement de l'information dans les contours +présents dans une image. Cet algorithme présente un bon compromis entre sécurité +fournie et complexité algorithmique. +Nous avons enfin proposé d'exprimer les fonctions de distorsion classiquement utilisées en stéganographie +comme des méthodes de calcul de gradient +ou de matrice Hessienne. Grâce à l'étude de ces matrices, nous avons proposé un nouveau schéma de +stéganographie sécurisé (chapitre~\ref{chap:th:yousra}). + +\subsection{Quelques perspectives} + +\subsubsection{Étendons les PRNGs} +La démarche actuelle de génération de nombres pseudo-aléatoires +consiste à marcher dans une partie d'un $\mathsf{N}$-cube en choisissant son chemin +à l'aide d'un générateur fourni en entrée. Or ces générateurs sont tous des +fonctions de $\{0,1\}^{\mathsf{N}}$ dans lui-même. Cette approche +semble pouvoir se réécrire comme un produit synchrone de deux automates. +L'intérêt d'une telle réécriture est qu'on pourrait exploiter +les résultats théoriques et pratiques déjà connus dans la communauté +des automates. +Nous pensons investiguer cette voie pour améliorer notre approche, +s'affranchir, à terme, de tout autre générateur et améliorer la +connaissance à ce sujet. + +De plus, marcher dans une partie d'un $\mathsf{N}$-cube est le modèle théorique que +nous avons établi pour notre classe de générateurs. On a vu, via les itérations généralisées +qu'on pouvait modifier plusieurs bits +en une seule itération. Les premiers travaux pratiques réalisés ont montré +que le nombre d'itérations suffisant pour converger vers une distribution uniforme +est plus petit que celui obtenu en marchant et qu'il diminue à mesure que $\mathsf{N}$ +augmente. Pour l'instant, nous n'avons pas réussi à obtenir une majoration du nombre d'itérations +pour le temps d'arrêt, ce qui pourrait être une perspective. + +\subsubsection{Des codes de Gray localement et globalement équilibrés} +Enfin, pour générer une fonction dont la matrice de Markov est doublement +stochastique +--condition nécessaire pour fournir une sortie uniformément distribuée--, +nous avons proposé principalement la méthode de +suppression de chemin hamiltonien dans un $\mathsf{N}$-cube. +Nous avons fait sauter un premier verrou en proposant une méthode déterministe à l'extension +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é. +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 +deux propriétés d'équilibrage. + +\subsubsection{Stéganalyse par deep learning} + +Les démarches de stéganalyse sont souvent composées de 2 étapes: +caractérisation puis classification. +On extrait au préalable une grande quantité des caractéristiques du média +puis on utilise une méthode de +classification basée sur celles-ci. La communauté voit souvent cette +seconde étape comme une boite noire et se concentre +sur la construction de l'ensemble des caractéristiques les plus discriminantes. +Autant que nous sachions, les méthodes algébriques +de réduction de domaine (analyse par composant principaux, SVD) +ont rarement été utilisées comme une étape intermédiaire entre la caractérisation et +la classification. Ces méthodes ont déjà été +appliquées avec succès lorsqu'elles sont combinées avec des méthodes +d'apprentissage, par exemple dans de la reconnaissance faciale. +Je propose d'étudier cette piste dans ce domaine. + + +De plus les résultats obtenus en stéganalyse à l'aide de deep learning à base de convolutions +sont très prometteurs lorsque la clef qui a servi à l'embarquement est constante. +Malheureusement, lorsque la clef varie, nous n'avons pas réussi à généraliser ces avancées. +Les démarches les plus efficaces demeurent +celles obtenues par des approches classiques à base de caractéristiques statistiques (features) +d'images. +Cependant, en étudiant plus finement les features, on constate que nombreuses sont celles qui sont aussi +basées sur des produits de convolution. +Je propose d'étudier exhaustivement ces features pour d'abord traduire +en deep-learning celles qui sont des convolutions directes. Il restera ensuite +à adapter l'outil de deep learning aux caractéristiques restantes ce qui est un autre challenge +scientifique. + diff --git a/intro.tex b/intro.tex new file mode 100644 index 0000000..90611ec --- /dev/null +++ b/intro.tex @@ -0,0 +1,16 @@ + +Introduire mathématiques discrètes + +Systèmes dynamiques discrets + +convergence vs divergence + +chaos <=> aléa + +PRNG + +codes de Gray + +générateur c Sécurité informatique: régularité -> marquage + +Dérivées partielles discrete pour la sétagno diff --git a/main.tex b/main.tex index 86c917e..94edfdb 100644 --- a/main.tex +++ b/main.tex @@ -168,13 +168,13 @@ \chapter*{Introduction} -Blabla blabla. +\input{intro} \mainmatter \part{Réseaux discrets} -\chapter{Iterations discrètes de réseaux booléens} +\chapter{Iterations discrètes de réseaux booléens}\label{chap:sdd} Ce chapitre formalise tout d'abord ce qu'est un réseau booléen (section~\ref{sec:sdd:formalisation}. On y revoit @@ -256,7 +256,7 @@ Le chapitre suivant s'intéresse à essayer de prédire le comportement de telles fonctions. -\chapter{Prédiction des systèmes chaotiques} +\chapter{Prédiction des systèmes chaotiques}\label{chp:ANN} \input{chaosANN} @@ -264,10 +264,10 @@ de telles fonctions. \part{Applications à la génération de nombres pseudo aléatoires} -\chapter{Caractérisation des générateurs chaotiques} +\chapter{Caractérisation des générateurs chaotiques}\label{chap:PRNG:chao} \input{15RairoGen} -\chapter{Les générateurs issus des codes de Gray} +\chapter{Les générateurs issus des codes de Gray}\label{chap:PRNG:gray} \input{14Secrypt} @@ -278,63 +278,27 @@ de telles fonctions. \chapter{Des embarquements préservant le chaos}\label{chap:watermarking} \input{oxford} -\chapter{Une démarche de marquage de PDF} +\chapter{Une démarche de marquage de PDF}\label{chap:watermarking:pdf} \input{ahmad} -\chapter{Une démarches plus classique de dissimulation: STABYLO} +\chapter{Une démarches plus classique de dissimulation: STABYLO}\label{chap:stabylo} \input{stabylo} -\chapter{Schéma de stéganographie: les dérivées du second ordre} +\chapter{Schéma de stéganographie: les dérivées du second ordre}\label{chap:th:yousra} \input{stegoyousra} \part{Conclusion et Perspectives} +\input{conclusion} -\JFC{Perspectives pour SDD->Promela} -Among drawbacks of the method, one can argue that bounded delays is only -realistic in practice for close systems. -However, in real large scale distributed systems where bandwidth is weak, -this restriction is too strong. In that case, one should only consider that -matrix $s^{t}$ follows the iterations of the system, \textit{i.e.}, -for all $i$, $j$, $1 \le i \le j \le n$, we have$ -\lim\limits_{t \to \infty} s_{ij}^t = + \infty$. -One challenge of this work should consist in weakening this constraint. -We plan as future work to take into account other automatic approaches -to discharge proofs notably by deductive analysis~\cite{CGK05}. - -\JFC{Perspective ANN} - -In future work we intend to enlarge the comparison between the -learning of truly chaotic and non-chaotic behaviors. Other -computational intelligence tools such as support vector machines will -be investigated too, to discover which tools are the most relevant -when facing a truly chaotic phenomenon. A comparison between learning -rate success and prediction quality will be realized. Concrete -consequences in biology, physics, and computer science security fields -will then be stated. -Ajouter lefait que le codede gray n'est pas optimal. -On pourrait aussi travailler à établir un classement qui préserverait -le fait que deux configurations voisines seraient représentées -par deux entiers voisins. Par optimisation? - -\JFC{Perspectives pour les générateurs} : marcher ou sauter... comment on -pourrait étendre, ce que l'on a déjà, ce qu'il reste à faire. - - -\JFC{prespectives watermarking : réécrire l'algo nicolas dans le formalisme -du chapitre 8} - -% TSI 2015 -% \chapter{Conclusion} -% Blabla blabla. \appendix -- 2.39.5