[hdrcouchot.git] / oxford.tex

\JFC{Dire que c'est une synthèse du chapitre 22 de la thèse de Tof}

This section has focused on security with regards to probabilistic behaviors. 
Next section studies it in the perspective of topological ones.



\section{Processus de marquage}

Par la suite, le message numérique qu'on cherche à embarquer est 
noté $y$ et le support dans lequel se fait l'insertion est noté $x$. 

Le processus de marquage est fondé sur les itérations unaires d'une fonction 
selon une stratégie donnée.  Cette fonction et cette stratégie 
sont paramétrées par un entier naturel permettant à la méthode d'être
appliquable à un média de n'importe quelle taille.
On parle alors respectivement de \emph{mode} et d'\emph{adapteur de stratégies} 

\subsection{Embarquement}


\begin{Def}[Mode]
\label{def:mode}
Soit $\mathsf{N}$ un entier naturel. 
Un mode est une application de $\mathds{B}^{\mathsf{N}}$
dans lui même.
\end{Def}



\begin{Def}[Adapteur de Stratégie]
  \label{def:strategy-adapter}
  
  Un  \emph{adapteur de stratégie} est une fonction $\mathcal{S}$ 
  de  $\Nats$ dans l'ensemble des séquences d'entiers 
  qui associe à chaque entier naturel
  $\mathsf{N}$ la suite 
  $S \in  \llbracket 1, n\rrbracket^{\mathds{N}}$.
\end{Def}


On définit par exemple  l'adapteur CIIS (\emph{Chaotic Iterations with Independent Strategy})
paramétré par $(K,y,\alpha,l) \in [0,1]\times [0,1] \times ]0, 0.5[ \times \mathds{N}$
qui associe à chque entier  $n \in \Nats$  la suite
$(S^t)^{t \in \mathds{N}}$ définie par:
 \begin{itemize}
 \item $K^0 = \textit{bin}(y) \oplus \textit{bin}(K)$: $K^0$ est le nombre binaire (sur 32 bits)
   égal au ou exclusif (xor) 
   entre les décompositions binaires sur 32 bits des réels $y$ et  $K$
   (il est aussi compris entre 0 et 1),
 \item $\forall t \leqslant l, K^{t+1} = F(K^t,\alpha)$,
 \item $\forall t \leqslant l, S^t = \left \lfloor n \times K^t \right \rfloor + 1$,
 \item $\forall t > l, S^t = 0$,
 \end{itemize}
où  est la fonction chaotique linéaire par morceau~\cite{Shujun1}.
Les paramètres $K$ et $\alpha$ de cet adapteur de stratégie peuvent être vus
comme des clefs. 
On remarque que cette stratégie est unaire.




On peut attribuer à chaque bit du média hôte $x$ sa valeur d'importance 
sous la forme d'un réel.
Ceci se fait à l'aide d'une fonction de signification. 


\begin{Def}[Fonction de signification ]
Une  \emph{fonction de signification } 
est une fonction $u$ qui a toute 
séquence finie de bit $x$ associe la séquence 
$(u^k(x))$ de taille $\mid x \mid$ à valeur dans les réels.
Cette fonction peut dépendre du message $y$ à embarquer, ou non.
\end{Def}

Pour alléger le discours, par la suite, on nottera $(u^k(x))$ pour $(u^k)$ 
lorsque cela n'est pas ambigüe.
Il reste à partionner les bits  de $x$ selon qu'ils sont 
peu, moyennement ou très significatifs. 

\begin{Def}[Signification des bits]\label{def:msc,lsc}
Soit $u$ une fonction de signification, 
$m$ et  $M$ deux réels  t.q. $m < M$.  Alors:
$u_M$, $u_m$ et $u_p$ sont les vecteurs finis respectivements des 
\emph{bits les plus significatifs  (MSBs)} de $x$,
\emph{bits les moins significatifs (LSBs)} de $x$ 
\emph{bits passifs} of $x$ définis par:
\begin{eqnarray*}
  u_M &=& \left( k ~ \big|~ k \in \mathds{N} \textrm{ et } u^k 
    \geqslant M \textrm{ et }  k \le \mid x \mid \right) \\
  u_m &=& \left( k ~ \big|~ k \in \mathds{N} \textrm{ et } u^k 
  \le m \textrm{ et }  k \le \mid x \mid \right) \\
   u_p &=& \left( k ~ \big|~ k \in \mathds{N} \textrm{ et } 
u^k \in ]m;M[ \textrm{ et }  k \le \mid x \mid \right)
\end{eqnarray*}
 \end{Def}

On peut alors définir une fonction de décompostion  
puis de recomposition pour un hôte $x$:


\begin{Def}[Fonction de décomposition ]
Soit $u$ une fonction de signification, 
$m$ et $M$ deux réels t.q  $m < M$.  
Tout hôte $x$ peut se décomposer en
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$
avec 
\begin{itemize}
\item $u_M$, $u_m$, et  $u_p$ construits comme à la définition~\label{def:msc,lsc},
\item $\phi_{M} = \left( x^{u^1_M}, x^{u^2_M}, \ldots,x^{u^{|u_M|}_M}\right)$,
\item $\phi_{m} = \left( x^{u^1_m}, x^{u^2_m}, \ldots,x^{u^{|u_m|}_m} \right)$,
\item $\phi_{p} =\left( x^{u^1_p}, x^{u^2_p}, \ldots,x^{u^{|u_p|}_p}\right) $.
\end{itemize}
La fonction qui associe $(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$
pour chaque hôte $x$ est la  \emph{fonction de décomposition}, plus tard notée 
$\textit{dec}(u,m,M)$ puisqu'elle est paramétrée par 
$u$, $m$ and $M$. 
\end{Def} 


\begin{Def}[Recomposition]
Soit un sextuplet 
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p}) \in 
\mathfrak{N} \times 
\mathfrak{N} \times 
\mathfrak{N} \times 
\mathfrak{B} \times 
\mathfrak{B} \times 
\mathfrak{B} 
$ tel que
\begin{itemize}
\item les ensembles $u_M$, $u_m$ et  $u_p$ forment une partition de  $[n]$;
\item $|u_M| = |\varphi_M|$, $|u_m| = |\varphi_m|$ et $|u_p| = |\varphi_p|$.  
\end{itemize}
Soit la base canonique sur l'espace vectoriel $\mathds{R}^{\mid x \mid}$ composée des vecteurs 
 $e_1, \ldots, e_{\mid x \mid}$.
On peut construire le vecteur 
\[
x = 
\sum_{i=1}^{|u_M|} \varphi^i_M . e_{{u^i_M}} +  
\sum_{i=1}^{|u_m|} \varphi^i_m .e_{{u^i_m}} +  
\sum_{i=1}^{|u_p|} \varphi^i_p. e_{{u^i_p}} 
\]
La fonction qui associe $x$ à chaque sextuplet 
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ défini comme ci-dessus est appelée 
\emph{fonction de recomposition}.
\end{Def}

Un embarquement consiste à modifier les valeurs de  
$\phi_{m}$ (de $x$) en tenant compte de $y$. 
Cela se formalise comme suit:

\begin{Def}[Embarquement de message]
Soit une fonction de décomposition  $\textit{dec}(u,m,M)$,  
$x$ un support, 
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ son image par $\textit{dec}(u,m,M)$, 
et $y$ un média numérique de taille $|u_m|$.
Le média $z$ résultant de l'embarquement d'$y$ dans $x$ est l'image de 
$(u_M,u_m,u_p,\phi_{M},y,\phi_{p})$
par la fonction de recomposition $\textit{rec}$.
%  avec 
% $g : \Bool^{|u_m|} \times \Bool^{|u_m|} \to \Bool^{|u_m|} $
% est la fonction de modification des bits de $u_m$ selon $y$.
\end{Def}

 
On peut étendre l'algorithme dhCI~\cite{gfb10:ip} d'embarquement de message comme suit:  

\begin{Def}[Embarquement dhCI étendu]
 \label{def:dhCI:ext}
Soit $\textit{dec}(u,m,M)$ une function de décomposition,
$f$ un mode, 
$\mathcal{S}$ un adapteur de stratégie,
$x$ un hôte, 
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ 
sont image par  $\textit{dec}(u,m,M)$,
$q$ un entier naturel positif
et $y$ un média numérique de taille $l=|u_m|$.

L'algorithme d'embarquement de message associe à chaque 
couple $(x,y)$  le média  $z$ résultat de l'embarquement de 
$\hat{y}$ dans $x$, t. q.:

\begin{itemize}
\item le mode $f$ est instancié avec le paramètre $l=|u_m|$, engendrant la 
  fonction $f_{l}:\Bool^{l} \rightarrow \Bool^{l}$;
\item l'adapteur de stratégie $\mathcal{S}$ est intancié avec le paramètre
$y$, engendrant une stratégie $S_y \in [l]$;
\item on itère la fonction $G_{f_l}$ en prenant la configuration
  initiale $(S_y,\phi_{m})$ selon le schéma défini 
  à l'équation~(\ref{eq:sch:unaire}). 
\item $\hat{y}$ est le second membre du $q^{\textrm{ème}}$ terme obtenu.
\end{itemize}
\end{Def}


La figure~\ref{fig:organigramme} synthétise la démarche.

\begin{figure}[ht]
\centering
%\includegraphics[width=8.5cm]{organigramme2.pdf}
\includegraphics[width=8.5cm]{organigramme22}
\caption{The dhCI dissimulation scheme}
\label{fig:organigramme}
\end{figure}




\subsection{Détection d'un media marqué}\label{sub:wmdecoding}

On caractérise d'abord ce qu'est un média marqué selon la méthode énoncée 
à la section précédente. On considère que l'on connaît
la marque à embarquer $y$, le support $x$ et que l'on a face à soit un média 
$z$.


\begin{definition}[Média marqué]
Soit $\textit{dec}(u,m,M)$ une fonction de décomposition
$f$ un  mode, 
$\mathcal{S}$ un adapteur de stratégie
$q$ un entier naturel strictement positif,
$y$ un média digital et soit  
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ l'image par 
$\textit{dec}(u,m,M)$  du média  $x$. 
Alors, $z$ est \emph{marqué} avec $y$ si l'image 
par $\textit{dec}(u,m,M)$ of $z$ is 
$(u_M,u_m,u_p,\phi_{M},\hat{y},\phi_{p})$, où
$\hat{y}$ est le second membre de  $G_{f_l}^q(S_y,\phi_{m})$.
\end{definition}

% Plusieurs stratégies peuvent être utilisées pour déterminer si une image $z$ 
% est marquée, en particulier si l'image a été attaquée entre temps.
% On s'intéressera aux mesures de similarité entre $x$ et $z$.

\section{Analyse de sécurité (probabilistes)}\label{sec:watermarking:security:probas}


Récemment~\cite{Cayre2005,Perez06} ont proposé des classes de sécurité pour le
marquage d'information. Parmis celles-ci, la stego-sécurité a été au centre 
des travaux puisqu'elle représente la classe la plus élevée dans le contexte où
l'attaquant n'a accès qu'à l'hôte marqué $z$.

Cette définition probabiliste est rappelée ci-après.
Soit $\mathds{K}$ un ensemble de clefs, $p(X)$ un modèle porbabiliste 
de $N_0$ hôtes,  et $p(Y|K)$ le modèle probabiliste de $N_0$ contenus marqués avec la 
même clé $K$ et le même algorithme d'embarquement.

\begin{definition}[Stégo-Sécurité~\cite{Cayre2008}]
\label{Def:Stego-security} 
La fonction d'embarquement is \emph{stégo-sécure}
si la propriété $\forall K \in \mathds{K}, p(Y|K)=p(X)$ est établie.
\end{definition}

Il a déjà été démontré~\cite{guyeuxphd,gfb10:ip}
que l'algorithme de marquage dont le mode est la fonction 
négation est stégo-sécure. 
Un des intérêts de l'algorithme présenté ici est qu'il est paramétré par un mode.
Lorsque celui-ci a les même propriétés que celles vues pour la création de PRNG (\textit{i.e.} graphe des itérations fortement connexes et matrice de Markov doublement 
stochastique), on a un marquage qui peut être rendu stego-secure à $\epsilon$ pret,
ce que précise le théorème suivant:

\begin{theorem}\label{th:stego}
Soit  $\epsilon$ un nombre positif, 
$l$ un nombre de LSBs, 
$X   \sim \mathbf{U}\left(\mathbb{B}^l\right)$,
un adapteur de stratégie uniformémement distribué indépendant de $X$
$f_l$ un mode tel que  
$\textsc{giu}(f_l)$ est fortement connexe et la 
matrice de Markov associée à  $f_l$ est doublement stochastique.
Il existe un nombre $q$ d'itérations tel que 
$|p(Y|K)- p(X)| < \epsilon$. 
\end{theorem}



\section{Analyse de sécurité (chaos)}\label{sec:watermarking:security:chaos}
On rappelle uniquement la définition de chaos-sécurité
introduite dans~\cite{guyeuxphd}.


\begin{definition}[Chaos-sécurité]
\label{DefinitionChaosSecure}
Un schéma de marquage $S$ est chaos-sécure sur un espace topologique
$(\mathcal{X},\tau)$
si sa version itérative 
a un comprtement chaotique sur celui-ci.
\end{definition}

Tout repose ainsi sur la capacité que l'on a à produire des fonctions 
dont le graphe des itérations unaires sera fortement connexe.
Ceci a déjà été traité au chapitre~\ref{chap:carachaos}.
La seule complexité est l'adaptabilité de la fonction au  nombre $l$ de LSBs.

On considère par exemple le  mode
$f_l: \Bool^l \rightarrow \Bool^l$ t.q. le $i^{\textrm{ème}}$ composant 
est défini par 
\begin{equation}
{f_l}(x)_i =
\left\{
\begin{array}{l}
\overline{x_i} \textrm{ si $i$ est impair} \\
x_i \oplus x_{i-1} \textrm{ si $i$ est pair}
\end{array}
\right.
\end{equation}\label{eq:fqq}

on peut déduire imédiatement du théorème~\ref{th:Adrien} (chap.~\ref{chap:carachaos})
que le graphe $\textsc{giu}(f_l)$ est fortement connexe.
La preuve de double-stochasiticité de la matrice associée 
à $f_l$ est donnée en annexes~\ref{anx:marquage:dblesto}.
On dispose ainsi d'un nouvel algorithme de marquage $\epsilon$-stego-secure et 
chaos-sécure.

\section{Applications aux domaines fréquentiels}
Le schéma d'algorithme présenté dans ce chapitre a été appliqué au marquage d'images 
dans les coefficients DCT et les DWT.

\subsection{Fonction de signification pour l'embarquement dans les DCT} 
 
On considère un hôte $x$ de taille $H \times L$ dans le domaine fréqentiel DCT.
Dans chaque bloc de taille $8\times 8$, à chaque bit
la fonction de signification $u$ associe

\begin{itemize}
\item 1 si c'est un bit appraissant dans la représentation binaire de la valeur d'un coefficient dont les coordonnées appartiennent à $\{(1,1),(2,1),(1,2)\}$,
\item 1 si c'est un bit appraissant dans la représentation binaire de la valeur 
  d'un coefficient dont les 
  coordonnées appartiennent à $\{(3,1),(2,2),(1,3)\}$ et qui n'est pas un des trois 
  bits de poids faible de cette représentation,
\item -1 si c'est un bit appraissant dans la représentation binaire
de la valeur d'un coefficient dont les 
  coordonnées appartiennent à $\{(3,1),(2,2),(1,3)\}$ et qui est un des 
 des trois bits de poids faible  de cette valeur,
\item 0 sinon.
\end{itemize}
Le choix de l'importance de chaque coefficient est défini grâce aux seuils  
$(m,M)=(-0.5,0.5)$ 
permetant d'engendrer les MSBs, LSBs, et bits passifs.


\subsection{Fonction de signification pour l'embarquement dans les DWT} 

On considère un hôte dnas le domaine des DWT. La fonction de signification 
se concentre sur les seconds niveaux de détail (\textit{i.e.}, LH2, HL2 et HH2).
Pour chaque bit, on dit qu'il est peu significatif si c'est un des trois bits de 
poids faible d'un coefficient de  LH2, HL2 ou de  HH2.
Formellement  à chaque bit
la fonction de signification $u$ associe

\begin{itemize}
\item 1 si c'est un bit appraissant dans la représentation binaire de la valeur d'un coefficient de type LL2, 
\item 1 si c'est un bit appraissant dans la représentation binaire de la valeur d'un coefficient de type LH2, HL2, HH2 et qui n'est pas un des trois 
  bits de poids faible de cette représentation,
\item 1 si c'est un bit appraissant dans la représentation binaire de la valeur d'un coefficient de type LH2, HL2, HH2 et qui est un des trois 
  bits de poids faible de cette représentation,
\item 0 sinon.
\end{itemize}
Le choix de l'importance de chaque coefficient est encore défini grâce aux seuils  
$(m,M)=(-0.5,0.5)$ 
permetant d'engendrer les MSBs, LSBs, et bits passifs.


\subsection{Etude de robustesse}
Cette partie synthétise une étude de robustesse de la démarche présentée ci-avant.
Dans ce qui suit, {dwt}(neg), 
{dwt}(fl), {dct}(neg), {dct}(fl) 
correpondent respectivement aux embarquements en fréquenciel 
dans les domaines  DWT et  DCT 
avec le mode de négation et celui issu de la fonction $f_l$
détaillé à l'équation~\ref{eq:fqq}.

A chaque série d'expériences, un ensemble de 50 images est choisi aléatoirement 
de la base du concours BOSS~\cite{Boss10}. Chaque hôte est une image 
en $512\times 512$ en niveau de gris et la marque $y$ est une suite de
4096 bits.
La resistance à la robustesse est évaluée en appliquant successivement
sur l'image marquée des attaques de découpage, de compression, de 
transformations géométriques. 
Si les différences entre  $\hat{y}$ and $\varphi_m(z)$.
sont en desous d'un seuil(que l'on définit), 
l'image est dite marquée (et non marquée dans le cas contraire).
Cette différence exprimée en pourcentage est rappellée pour chacune des ataques
à la figure~\ref{fig:atq:dhc}.


\begin{figure}[ht]
  \centering
  \subfigure[Découpage]{
    \includegraphics[width=0.5\textwidth]{atq-dec}\label{Fig:atq:dec:curves}
  }
  \subfigure[Compression JPEG]{
    \includegraphics[width=0.45\textwidth]{atq-jpg}\label{Fig:atq:jpg:curves}
  }
  \subfigure[Compression JPEG 2000]{
    \includegraphics[width=0.45\textwidth]{atq-jp2}\label{Fig:atq:jp2:curves}
  }
  \subfigure[Modification du contrast]{
    % \includegraphics[width=0.45\textwidth]{atq-contrast.pdf}\label{Fig:atq:cont:curve}}
    \includegraphics[width=0.45\textwidth]{atq-contrast}\label{Fig:atq:cont:curve}
  }
  \subfigure[Accentuation des bords]{
    % \includegraphics[width=0.45\textwidth]{atq-flou.pdf}\label{Fig:atq:sh:curve}}
    \includegraphics[width=0.45\textwidth]{atq-flou}\label{Fig:atq:sh:curve}
  }
  \subfigure[Rotation]{
    % \includegraphics[width=0.45\textwidth]{atq-rot.pdf}\label{Fig:atq:rot:curve}}
    \includegraphics[width=0.45\textwidth]{atq-rot}\label{Fig:atq:rot:curve}
  }
\caption{Illustration de la robustesse}\label{fig:atq:dhc}
\end{figure}


\subsection{Evaluation de l'embarquement}\label{sub:roc}
Pour évaluer le seuil qui permet de dire avec la plus grande précision 
si une image est marquée ou non, nous avons appliqué la démarche suivante.
A partir d'un ensemble de 100 images du challenge BOSS, les trois 
ensembles suivants sont construits: celui des images marquées $W$,
celui contenant des imges marquées puis attaquée $\textit{WA}$,
et celui des images uniquement attaquées $A$. Les attaques sont choisiés parmi 
celles données ci dessus.

Pour chaque entier $t$ entre 5 et 55 
et chaque  image $x \in \textit{WA} \cup A$,
on calcule la différence entre  $\hat{y}$ et $\varphi_m(z)$.
L'image est dite marquée si cette différence est en dessous du seuil $t$  considéré  
\begin{itemize}
\item si elle est dite marquée et si $x$ appartient  à $\textit{WA}$
  c'est un vrai cas positif (TP);
\item si elle est dite non marquée et si $x$ appartient cependant à $\textit{WA}$
  c'est un faux cas négatif (FN);
\item si elle est dite marquée et si $x$ appartient cependant à $\textit{A}$
  c'est un faux cas positif (FP);
\item enfin si elle est dite non marquée et si $x$ appartient à $\textit{A}$
  c'est un vrai cas négatif (TN).
\end{itemize}


\begin{figure}[ht]
\begin{center}
\includegraphics[width=7cm]{ROC}
\end{center}
\caption{Courbes ROC de seuils de détection}\label{fig:roc:dwt}
\end{figure}

La courbe ROC construite à partir des points de coordonnées (TP,FP) issus 
de ces seuils est 
donnée à la figure~\ref{fig:roc:dwt}. 
Pour la fonction $f_l$ et pour la fonction négation respectivement, 
la détection est optimale pour le seuil de 45\% correspondant au point (0.01, 0.88)
et pour le seuil de  46\%  correspondant au point (0.04, 0.85) 
dans le domaine DWT.
Pour les deux modes dans le domaine DCT, 
la détection est optimale pour le seuil de 44\% 
(correspondant aux points (0.05, 0.18) et (0.05, 0.28)).
On peut alors donner des intervales de confiance pour les attaques évaluées.
L'approche est résistante à:
\begin{itemize}
\item tous les découpages où le pourcentage est inférieur à 85\%;
\item les compression dont le ratio est supérieur à 82\% dans le domaine 
  DWT et  67\% dans celui des DCT;
\item les modifications du contraste lorsque le renforcement est dans 
  $[0.76,1.2]$ dans le domaine DWT et  $[0.96,1.05]$ dans le domaine DCT;
\item toutes les rotations dont l'angle est inférieur à 20 degrés dans le domaine DCT et 
  celles dont l'angle est inférieur à 13 degrés dans le domaine DWT.
\end{itemize}