]> AND Private Git Repository - hdrcouchot.git/blobdiff - ahmad.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
preuve promela:debut de traduction
[hdrcouchot.git] / ahmad.tex
index 6aed620a340536a45af0af732365278012bdecf6..05d91778f94335d76143054fbc50f9af17e3b52c 100644 (file)
--- a/ahmad.tex
+++ b/ahmad.tex
@@ -1,4 +1,4 @@
-En étudiant le watermarking,
+En étudiant les schémas de watermarking,
 nous avons constaté que très peu de travaux ciblaient les documents PDF
 qui représentent cependant une part non anecdotique des données
 échangées en ligne.
 nous avons constaté que très peu de travaux ciblaient les documents PDF
 qui représentent cependant une part non anecdotique des données
 échangées en ligne.
@@ -9,38 +9,43 @@ ajoutent des caractères invisibles dans le document.
 En supprimant ces espaces ou caractères invisibles, la marque s'enlève
 facilement.
 Dans~\cite{PD2008}, les auteurs modifient de manière imperceptible
 En supprimant ces espaces ou caractères invisibles, la marque s'enlève
 facilement.
 Dans~\cite{PD2008}, les auteurs modifient de manière imperceptible
-le positionnements des caractères. D'autres éléments de postionnement
+le positionnements des caractères. D'autres éléments de positionnement
 sont intégrés dans~\cite{WT08}.
 sont intégrés dans~\cite{WT08}.
-Une attaque qui remodifierait  aléatoirement de manière faible ces positions
+Une attaque qui modifierait  aléatoirement de manière faible ces positions
  détruirait la marque dans les deux cas.
  détruirait la marque dans les deux cas.
-La quantification (au sens du traitemetn du signal) est une réponse
+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
 préétablies et conserver ainsi leur information et donc la marque.
 STDM~\cite{CW01} est une instance de ces schémas de marquage.
 
 Ce chapitre présente une application de STDM au marquage de documents PDFs.
 à 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
 préétablies et conserver ainsi leur information et donc la marque.
 STDM~\cite{CW01} est une instance de ces schémas de marquage.
 
 Ce chapitre présente une application de STDM au marquage de documents PDFs.
-\JFC{annonce du plan}
+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}
+Ce travail a été publié dans~\cite{BDCC16}.
 
 
-\section{Rappels sur STDM}
 
 
-\section{Spread Transform Dither Modulation}
+
+\section{Rappels sur la Spread Transform Dither Modulation}
 \label{sec:STDM}
 Les paramètres de ce schéma sont
 \begin{itemize}
 \label{sec:STDM}
 Les paramètres de ce schéma sont
 \begin{itemize}
-\item le facteur de quantification $\Delta$ est un réel positif; plus $\Delta$
-est grand, plus la distortion peut être importante;
+\item le facteur de quantification $\Delta$ qui est un réel positif; plus $\Delta$
+est grand, plus la distorsion peut être importante;
 \item le niveau d'indécision  $d_0$ qui est un réel dans
 $[-\dfrac{\Delta}{2},\dfrac{\Delta}{2}]$; plus ce nombre a une valeur absolue
 élevée, plus les erreurs peuvent être corrigées;
 \item le niveau d'indécision  $d_0$ qui est un réel dans
 $[-\dfrac{\Delta}{2},\dfrac{\Delta}{2}]$; plus ce nombre a une valeur absolue
 élevée, plus les erreurs peuvent être corrigées;
-On définit $d_1$ par 
+on définit $d_1$ par 
 $$d_1 = \begin{cases} 
   d_0 + \Delta/2, & \textrm{ si }~~d_0<0 \\  
   d_0 - \Delta/2, & \textrm{ sinon } 
 \end{cases}
 $$
 $$d_1 = \begin{cases} 
   d_0 + \Delta/2, & \textrm{ si }~~d_0<0 \\  
   d_0 - \Delta/2, & \textrm{ sinon } 
 \end{cases}
 $$
-\item un nombre $L$ d'éléments dans lequel chaque bit est embarqué;
-\item un vecteur $p$ de projection de taille $L$; 
+\item un nombre $L$ d'éléments dans lequel chaque bit de la marque 
+  est embarqué;
+\item un vecteur $p$ de projection de taille $L$. 
 
 \end{itemize}
 
 
 \end{itemize}
 
@@ -57,15 +62,166 @@ $\hat{m}$ extrait de
 $x'$ de taille $L$ est défini par:
 \begin{equation}
 \hat{m} = arg \min_{ m \in \{0, 1\}} \mid x'^T p - f(x,m) \mid
 $x'$ de taille $L$ est défini par:
 \begin{equation}
 \hat{m} = arg \min_{ m \in \{0, 1\}} \mid x'^T p - f(x,m) \mid
+\label{eq:stdm:ext}
 \end{equation}
 
 Les auteurs de~\cite{CW01} ont montré que la variance de l'erreur 
 \end{equation}
 
 Les auteurs de~\cite{CW01} ont montré que la variance de l'erreur 
-est égale à $\Delta^2/12L$ 
-lorsque chacun des $L$ éléments de $x$ suit une ditribution uniforme 
+est égale à $D_s = \Delta^2/12L$ 
+lorsque chacun des $L$ éléments de $x$ suit une distribution uniforme 
 $U(\Delta)$. 
 $U(\Delta)$. 
+Tous les éléments sont en place pour embarquer une marque 
+dans un fichier PDF selon le schéma STDM.
+
+\section{Application au marquage de documents PDF}\label{sec:stdm:schema}
+
+On détaille successivement comment insérer une marque dans un document PDF, 
+puis comment l'extraire.
+
+\subsection{Insertion de la marque}
+
+On cherche à ajouter à un document PDF une marque $m$ de $k$ bits 
+déjà codée (cryptée, correction d'erreurs incluse). 
+L'insertion de celle-ci dans le document s'effectue 
+en quatre étapes.
+
+On considère comme fixés les paramètres  
+$\Delta$,  $d_0$ , $L$ et la manière de construire le vecteur $p$ 
+pour ce $L$ donné. 
+
+
+\begin{enumerate}
+\item Le vecteur hôte $x$ de taille $N$ 
+  est constitué de l'abscisse (flottante) 
+  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) 
+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]$. 
+
+
+\item Pour chacun des ensembles $M_i$, $ 1 \le i \le k$, 
+  de l'étape précédente,  le vecteur $\dot{x} = (x_{j_1}, \ldots ,x_{j_L})$,
+  est construit où $\{j_1, \ldots, j_L\} = M_i$.
+  Le vecteur $\dot{x'} = f(\dot{x},m_i)$ est
+  construit selon l'équation~(\ref{eq:stdm}).
+  Dans $x$, chacun des $x_{j_1}, \ldots, x_{j_L}$ est remplacé par 
+  $\dot{x'}_{j_1}, \ldots, \dot{x'}_{j_L}$.
+
+\item L'abscisse de chaque caractère est ainsi redéfini 
+  selon le nouveau vecteur de positions ${x'}$. 
+\end{enumerate}
+
+Voyons comment extraire une marque d'une document PDF.
+
+\subsection{Extraction de la marque}
+
+On considère comme connue la taille de la marque: c'est $k$ bits.
+Les paramètres $\Delta$,  $d_0$ et la manière de construire 
+$p$ en fonction de $L$ sont les mêmes qu'à l'étape précédente d'insertion de 
+marque.
+
+\begin{enumerate}
+\item on récupère le vecteur $x'$ (de taille $N$ lui aussi) des abscisse des
+  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) 
+construit les $k$ mêmes ensembles $M_1$, \ldots, $M_k$ 
+de taille $L$ mutuellement disjoints dans $[1,N]$. 
+
+\item Pour chacun des ensembles $M_i$, $ 1 \le i \le k$, 
+  de l'étape précédente,  le vecteur $\dot{x'} = (x'_{j_1}, \ldots, x'_{j_L})$,
+  est construit où $\{j_1, \ldots, j_L\} = M_i$.
+  Le bit $\hat{m}_i$  est défini selon l'équation~(\ref{eq:stdm:ext})
+  en remplaçant $x'$ par $\dot{x'}$ .
+\end{enumerate}
+
+\section{Expérimentations}\label{sec:stdm:exp}
+Le schéma de marquage est paramétré par $\Delta$,  $d_0$ et la manière de construire le vecteur $p$ pour une taille $L$. 
+Les travaux réalisés se sont focalisés sur l'influence du paramètre 
+$D_S = \frac{\Delta^2}{12L}$ dans l'algorithme en satisfaisant 
+les deux contraintes antagonistes
+de fournir une marque suffisamment robuste
+et suffisamment transparente.
+On cherche deux réels $a$ et $b$   tels que
+$a$ et $b$ correspondent respectivement 
+au seuil maximum pour être transparent et 
+au seuil minimum pour être robuste. 
+Les études de perceptibilité doivent permettre de déterminer $a$ tandis 
+que celles sur la robustesse devront fixer le seuil $b$.
+Finalement, les contraintes précédentes seront  satisfaites si et seulement si  
+$a > b$ et $D_s \in [b,a]$.
+
+Concernant la transparence, 
+les expériences présentées dans l'article~\cite{BDCC16} ont consisté en 
+choisir un texte d'un nombre fixe de caractères $n$
+dans lequel doit être embarqué une marque de taille fixe $k$.
+En faisant varier la valeur de $\Delta$, nous avons remarqué que la 
+valeur $a= 0,01335$ est le seuil au delà duquel il est visuellement 
+possible de remarquer une différence entre le document original 
+et le document marqué.
+
+Il nous reste à détailler les expériences d'étude de robustesse de la démarche.
+Comme dans l'évaluation de la transparence, il s'est agit de faire 
+varier le paramètre  $\Delta$.
+Pour chacune de ces valeurs, le document a été altéré selon 
+un flou gaussien (de paramètre 0,1 et 0,25)  
+et une attaque de type poivre et sel (de paramètre 0,1 et 0,25 aussi).
+Le rapport entre le nombre de bits erronés par rapport au nombre total 
+de bits (nommé BER ci-après) après l'extraction du message est alors calculé. 
+Le facteur de quantification a été choisi entre 0.1 et 10. 
+L'expérience a été répétée 500 fois et les moyennes sont représentées 
+à la figure~\ref{fig:pdf:atq:ber}.
+Sur cette figure, on constate que pour peu que la quantification $\Delta$
+soit supérieure à 1,  le taux d'erreur est inférieur à 12,5\%. Ce taux peut 
+être corrigé par un code correcteur usuel.
+Avec les paramètres de l'expérimentation, cela revient à considérer un seuil 
+$b=0,00214$. 
+Ces expériences ont ainsi pu valider l'existence de seuils de distorsion
+permettant d'avoir une méthode à la fois robuste et transparente.
+
+
+
+\begin{figure}[ht]
+\begin{center}
+\begin{tikzpicture}
+
+        \begin{axis}[%
+            axis x line=bottom,
+            axis y line=left,
+            xlabel=$\Delta$,
+            ylabel=$BER~(\%)$,
+width=0.66\textwidth,
+            legend pos=north east]
+            \addplot[mark=none, dashed, red,thick] coordinates {(0.1, 13.8742) (0.5, 12.8721) (1, 8.4680) (1.1, 7.3940) (1.2, 6.5020) (1.3, 5.7960) (1.4, 4.9580) (1.5, 4.1180) (1.6, 3.8080) (1.7, 3.2580) (1.8, 2.8320) (1.9, 2.5000) (2, 2.2100) (2.1, 2.0420) (2.2, 1.8120) (2.3, 1.6080) (2.4, 1.4040) (2.5, 1.3860) (3, 1.1100) (5, 1) (10, 1)};
+
+ \addplot[mark=none, dotted, green,thick] coordinates {(0.1, 10.3501) (0.5, 7.1) (1, 4.7420) (1.1, 4.0580) (1.2, 3.3620) (1.3, 2.8260) (1.4, 2.3900) (1.5, 2.1220) (1.6, 1.9260) (1.7, 1.6540) (1.8, 1.4460) (1.9, 1.3680) (2, 1.3400) (2.1, 1.2460) (2.2, 1.1420) (2.3, 1.0920) (2.4, 1.0600) (2.5, 1.0460) (3, 1.0100) (5, 1) (10, 1)};
+
+ \addplot[mark=none, dashdotted, blue,thick] coordinates {(0.1, 15.3222) (0.5, 13) (1, 11.1560) (1.1, 10.2920) (1.2, 9.8520) (1.3, 8.7860) (1.4, 8.3960) (1.5, 7.3480) (1.6, 7.0880) (1.7, 6.0940) (1.8, 5.2100) (1.9, 4.8860) (2, 4.5940) (2.1, 4.0140) (2.2, 3.6060) (2.3, 3.3520) (2.4, 2.9300) (2.5, 2.6140) (3, 1.7000) (5, 1.0140) (10, 1)};
+
+ \addplot[mark=none, dash pattern=on 10pt off 2pt on 5pt off 6pt, black,thick] coordinates {(0.1, 13) (0.5, 10.7) (1, 9.3340) (1.1, 8.7580) (1.2, 7.7080) (1.3, 6.7580) (1.4, 5.9260) (1.5, 5.4320) (1.6, 4.7260) (1.7, 4.3020) (1.8, 3.6200) (1.9, 3.1380) (2, 2.9920) (2.1, 2.5780) (2.2, 2.4340) (2.3, 2.1240) (2.4, 1.8760) (2.5, 1.7386) (3, 1.2880) (5, 1) (10, 1)};
+
+            \legend{$Gaussian (0.1)$,$Salt\&pepper (0.1)$,$Gaussian (0.25)$,$Salt\&pepper (0.25)$};
+        \end{axis}
+    \end{tikzpicture}
+\\
+\end{center}
+\caption{Représentation du BER pour des attaques de type flou gaussien et
+poivre et sel}\label{fig:pdf:atq:ber}
+\end{figure}
 
 
 
 
-\section{Application au marquage de documents PDF}
+\section{Conclusion}\label{pdf:s:conclusion}
+Ce travail a présenté une démarche outillée
+basée sur la Spread Transform Dither Modulation 
+permettant d'embarquer une marque dans un document PDF.
+Les éléments modifiés sont les abscisses des caractères présents 
+dans le document.
 
 
+Deux des propriétés essentielles des algorithmes de marquage ont été étudiées:
+la transparence et la robustesse. La notion d'intervalle de distorsion 
+acceptable a été définie et calculée sur un exemple jouet.