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.
Parmi ces travaux, \cite{PD2008} propose la modification du nombre 
d'espaces entre les mots ou entre les paragraphes.
Similairement, les auteurs  de~\cite{DBLP:journals/sigpro/LeeT10}
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
le positionnements des caractères. D'autres éléments de positionnement
sont intégrés dans~\cite{WT08}.
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
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}

\section{Rappels sur la Spread Transform Dither Modulation}
\label{sec:STDM}
Les paramètres de ce schéma sont
\begin{itemize}
\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;
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}
$$
\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}

Soit donc $x$ un vecteur de taille $L$ dans lequel on souhaite embarquer 
le bit $m\in\{0,1\}$. 
Ce vecteur est remplacé par $x'$ défini par 
 
\begin{equation}\label{eq:stdm}
x' = f(x,m) = x+ ((\lfloor(\frac{(x^T p) -d_m}{\Delta})\rfloor\Delta +d_m )~ - x^T p)p
\end{equation}

Avec les mêmes paramètres $\Delta$, $d_0$ , $L$ et $p$ le message 
$\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
\label{eq:stdm:ext}
\end{equation}

Les auteurs de~\cite{CW01} ont montré que la variance de l'erreur 
est égale à $D_s = \Delta^2/12L$ 
lorsque chacun des $L$ éléments de $x$ suit une distribution uniforme 
$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}

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 }
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{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. 


