ahmad.tex

   1 En étudiant les schémas de watermarking,
   2 nous avons constaté que très peu de travaux ciblaient les documents PDF
   3 qui représentent cependant une part non anecdotique des données
   4 échangées en ligne.
   5 Parmi ces travaux, \cite{PD2008} propose la modification du nombre
   6 d'espaces entre les mots ou entre les paragraphes.
   7 Similairement, les auteurs  de~\cite{DBLP:journals/sigpro/LeeT10}
   8 ajoutent des caractères invisibles dans le document.
   9 En supprimant ces espaces ou caractères invisibles, la marque s'enlève
  10 facilement.
  11 Dans~\cite{PD2008}, les auteurs modifient de manière imperceptible
  12 le positionnement des caractères. D'autres éléments de positionnement
  13 sont intégrés dans~\cite{WT08}.
  14 Une attaque qui modifierait  aléatoirement de manière faible ces positions
  15  détruirait la marque dans les deux cas.
  16 La quantification (au sens du traitement du signal) est une réponse
  17 à ces attaques: des positions modifiées de manière mal intentionnée
  18 peuvent grâce à cette démarche être rapprochées (abstraites) en des positions
  19 préétablies et conserver ainsi leur information et donc la marque.
  20 STDM~\cite{CW01} est une instance de ces schémas de marquage.
  21
  22 Ce chapitre présente une application de STDM au marquage de documents PDFs.
  23 La première section fournit quelques rappels sur la STDM. Le schéma basé sur
  24 cette approche est présenté à la section~\ref{sec:stdm:schema}.
  25 Finalement, la démarche expérimentale permettant de trouver un compromis entre
  26 robustesse et qualité visuelle est présentée à la section~\ref{sec:stdm:exp}.
  27 Ce travail a été publié dans~\cite{BDCC16}.
  28
  29
  30
  31 \section{Rappels sur la Spread Transform Dither Modulation}
  32 \label{sec:STDM}
  33 Les paramètres de ce schéma sont
  34 \begin{itemize}
  35 \item le facteur de quantification $\Delta$ qui est un réel positif; plus $\Delta$
  36 est grand, plus la distorsion peut être importante;
  37 \item le niveau d'indécision  $d_0$ qui est un réel dans
  38 $[-\dfrac{\Delta}{2},\dfrac{\Delta}{2}]$; plus ce nombre a une valeur absolue
  39 élevée, plus les erreurs peuvent être corrigées;
  40 on définit $d_1$ par
  41 $$d_1 = \begin{cases}
  42   d_0 + \Delta/2, & \textrm{ si }~~d_0<0 \\
  43   d_0 - \Delta/2, & \textrm{ sinon }
  44 \end{cases}
  45 $$
  46 \item un nombre $L$ d'éléments dans lequel chaque bit de la marque
  47   est embarqué;
  48 \item un vecteur $p$ de projection de taille $L$.
  49
  50 \end{itemize}
  51
  52 Soit donc $x$ un vecteur de taille $L$ dans lequel on souhaite embarquer
  53 le bit $m\in\{0,1\}$.
  54 Ce vecteur est remplacé par $x'$ défini par
  55
  56 \begin{equation}\label{eq:stdm}
  57 x' = f(x,m) = x+ ((\lfloor(\frac{(x^T p) -d_m}{\Delta})\rfloor\Delta +d_m )~ - x^T p)p
  58 \end{equation}
  59
  60 Avec les mêmes paramètres $\Delta$, $d_0$ , $L$ et $p$ le message
  61 $\hat{m}$ extrait de
  62 $x'$ de taille $L$ est défini par:
  63 \begin{equation}
  64 \hat{m} = arg \min_{ m \in \{0, 1\}} \mid x'^T p - f(x,m) \mid
  65 \label{eq:stdm:ext}
  66 \end{equation}
  67
  68 Les auteurs de~\cite{CW01} ont montré que la variance de l'erreur
  69 est égale à $D_s = \Delta^2/12L$
  70 lorsque chacun des $L$ éléments de $x$ suit une distribution uniforme
  71 $U(\Delta)$.
  72 Tous les éléments sont en place pour embarquer une marque
  73 dans un fichier PDF selon le schéma STDM.
  74
  75 \section{Application au marquage de documents PDF}\label{sec:stdm:schema}
  76
  77 On détaille successivement comment insérer une marque dans un document PDF,
  78 puis comment l'extraire.
  79
  80 \subsection{Insertion de la marque}
  81
  82 On cherche à ajouter à un document PDF une marque $m$ de $k$ bits
  83 déjà codée (cryptée, correction d'erreurs incluse).
  84 L'insertion de celle-ci dans le document s'effectue
  85 en quatre étapes.
  86
  87 On considère comme fixés les paramètres
  88 $\Delta$,  $d_0$ , $L$ et la manière de construire le vecteur $p$
  89 pour ce $L$ donné.
  90
  91
  92 \begin{enumerate}
  93 \item Le vecteur hôte $x$ de taille $N$
  94   est constitué de l'abscisse (flottante)
  95   de chaque caractère rencontré dans le document PDF.
  96   La dimension $L$ est calculée comme la partie entière de $N/k$.
  97
  98 \item Un générateur pseudo-aléatoire (initialisé par une clef)
  99 construit $k$ ensembles $M_1$, \ldots, $M_k$
 100 de taille $L$ mutuellement disjoints dans $[1,N]$. Ainsi
 101 $\bigcup_{1\le i \le k} M_i \subseteq [N]$.
 102
 103
 104 \item Pour chacun des ensembles $M_i$, $ 1 \le i \le k$,
 105   de l'étape précédente,  le vecteur $\dot{x} = (x_{j_1}, \ldots ,x_{j_L})$,
 106   est construit où $\{j_1, \ldots, j_L\} = M_i$.
 107   Le vecteur $\dot{x'} = f(\dot{x},m_i)$ est
 108   construit selon l'équation~(\ref{eq:stdm}).
 109   Dans $x$, chacun des $x_{j_1}, \ldots, x_{j_L}$ est remplacé par
 110   $\dot{x'}_{j_1}, \ldots, \dot{x'}_{j_L}$.
 111
 112 \item L'abscisse de chaque caractère est ainsi redéfini
 113   selon le nouveau vecteur de positions ${x'}$.
 114 \end{enumerate}
 115
 116 Voyons comment extraire une marque d'un document PDF.
 117
 118 \subsection{Extraction de la marque}
 119
 120 On considère comme connue la taille de la marque: c'est $k$ bits.
 121 Les paramètres $\Delta$,  $d_0$ et la manière de construire
 122 $p$ en fonction de $L$ sont les mêmes qu'à l'étape précédente d'insertion de
 123 marque.
 124
 125 \begin{enumerate}
 126 \item on récupère le vecteur $x'$ (de taille $N$ lui aussi) des abscisse des
 127   caractères du document PDF comme dans la phase d'insertion.
 128   la valeur de $L$ est définie comme précédemment.
 129
 130 \item le même générateur pseudo-aléatoire (initialisé avec la même clef)
 131 construit les $k$ mêmes ensembles $M_1$, \ldots, $M_k$
 132 de taille $L$ mutuellement disjoints dans $[1,N]$.
 133
 134 \item Pour chacun des ensembles $M_i$, $ 1 \le i \le k$,
 135   de l'étape précédente,  le vecteur $\dot{x'} = (x'_{j_1}, \ldots, x'_{j_L})$,
 136   est construit où $\{j_1, \ldots, j_L\} = M_i$.
 137   Le bit $\hat{m}_i$  est défini selon l'équation~(\ref{eq:stdm:ext})
 138   en remplaçant $x'$ par $\dot{x'}$ .
 139 \end{enumerate}
 140
 141 \section{Expérimentations}\label{sec:stdm:exp}
 142 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$.
 143 Les travaux réalisés se sont focalisés sur l'influence du paramètre
 144 $D_S = \frac{\Delta^2}{12L}$ dans l'algorithme en satisfaisant
 145 les deux contraintes antagonistes
 146 de fournir une marque suffisamment robuste
 147 et suffisamment transparente.
 148 On cherche deux réels $a$ et $b$   tels que
 149 $a$ et $b$ correspondent respectivement
 150 au seuil maximum pour être transparent et
 151 au seuil minimum pour être robuste.
 152 Les études de perceptibilité doivent permettre de déterminer $a$ tandis
 153 que celles sur la robustesse devront fixer le seuil $b$.
 154 Finalement, les contraintes précédentes seront  satisfaites si et seulement si
 155 $a > b$ et $D_s \in [b,a]$.
 156
 157 Concernant la transparence,
 158 les expériences présentées dans l'article~\cite{BDCC16} ont consisté en
 159 choisir un texte d'un nombre fixe de caractères $n$
 160 dans lequel doit être embarqué une marque de taille fixe $k$.
 161 En faisant varier la valeur de $\Delta$, nous avons remarqué que la
 162 valeur $a= 0,01335$ est le seuil au delà duquel il est visuellement
 163 possible de remarquer une différence entre le document original
 164 et le document marqué.
 165
 166 Il nous reste à détailler les expériences d'étude de robustesse de la démarche.
 167 Comme dans l'évaluation de la transparence, il s'est agi de faire
 168 varier le paramètre  $\Delta$.
 169 Pour chacune de ces valeurs, le document a été altéré selon
 170 un flou gaussien (de paramètre 0,1 et 0,25)
 171 et une attaque de type poivre et sel (de paramètre 0,1 et 0,25 aussi).
 172 Le rapport entre le nombre de bits erronés par rapport au nombre total
 173 de bits (nommé BER ci-après) après l'extraction du message est alors calculé.
 174 Le facteur de quantification a été choisi entre 0.1 et 10.
 175 L'expérience a été répétée 500 fois et les moyennes sont représentées
 176 à la figure~\ref{fig:pdf:atq:ber}.
 177 Sur cette figure, on constate que pour peu que la quantification $\Delta$
 178 soit supérieure à 1,  le taux d'erreur est inférieur à 12,5\%. Ce taux peut
 179 être corrigé par un code correcteur usuel.
 180 Avec les paramètres de l'expérimentation, cela revient à considérer un seuil
 181 $b=0,00214$.
 182 Ces expériences ont ainsi pu valider l'existence de seuils de distorsion
 183 permettant d'avoir une méthode à la fois robuste et transparente.
 184
 185
 186
 187 \begin{figure}[ht]
 188 \begin{center}
 189 \begin{tikzpicture}
 190
 191         \begin{axis}[%
 192             axis x line=bottom,
 193             axis y line=left,
 194             xlabel=$\Delta$,
 195             ylabel=$BER~(\%)$,
 196 width=0.66\textwidth,
 197             legend pos=north east]
 198             \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)};
 199
 200  \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)};
 201
 202  \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)};
 203
 204  \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)};
 205
 206             \legend{$Gaussian (0.1)$,$Salt\&pepper (0.1)$,$Gaussian (0.25)$,$Salt\&pepper (0.25)$};
 207         \end{axis}
 208     \end{tikzpicture}
 209 \\
 210 \end{center}
 211 \caption{Représentation du BER pour des attaques de type flou gaussien et
 212 poivre et sel}\label{fig:pdf:atq:ber}
 213 \end{figure}
 214
 215
 216 \section{Conclusion}\label{pdf:s:conclusion}
 217 Ce travail a présenté une démarche outillée
 218 basée sur la Spread Transform Dither Modulation
 219 permettant d'embarquer une marque dans un document PDF.
 220 Les éléments modifiés sont les abscisses des caractères présents
 221 dans le document.
 222
 223 Deux des propriétés essentielles des algorithmes de marquage ont été étudiées:
 224 la transparence et la robustesse. La notion d'intervalle de distorsion
 225 acceptable a été définie et calculée sur un exemple jouet.
 226
 227