From ee3d36e30a972a8ed387bd09e148ff498315ae9b Mon Sep 17 00:00:00 2001 From: couchot Date: Thu, 24 Sep 2015 14:23:31 +0200 Subject: [PATCH] stabylo : la suite --- main.tex | 12 +++- stabylo.tex | 171 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 180 insertions(+), 3 deletions(-) diff --git a/main.tex b/main.tex index 0c6234e..7333e05 100644 --- a/main.tex +++ b/main.tex @@ -235,11 +235,11 @@ On montre qu'on a des résultats similaires. % OXFORD \input{oxford} -\chapter{Des démarches plus classiques} -\section{QIM} -\section{STABYLO} +\chapter{Une démarche de marquage de PDF} + +\chapter{Une démarches plus classique de dissimulation: STABYLO} \input{stabylo} @@ -343,6 +343,12 @@ du chapitre 8} \input{annexePreuveMarquageCorrectioncompletude} \backmatter +\section{Complexité d'Algorithmes de stéganographie} +\label{anx:preuve:cplxt} +\input{annexePreuvesComplexiteStego} + + + \bibliographystyle{apalike} \bibliography{abbrev,biblioand} \listoffigures diff --git a/stabylo.tex b/stabylo.tex index 62f203b..e926915 100644 --- a/stabylo.tex +++ b/stabylo.tex @@ -29,6 +29,177 @@ possible. Ceci revient à définir une fonction de signification $u$. La complexité du schéma de stéganographie est peu ou prou celle du calcul de cette carte, et elle est élevée (cf partie~\ref{XXXXXXXX}) dans le cas de ces algorithmes. +Nous avons proposé un algorithme~\cite{ccg15:ij} +de complexité beaucoup plus faible +et dont la détectabilité est satisfaisante. +Ce chapitre détaille les clefs de ce schéma + + + +\section{Présentation de l'approche} + +Le diagramme de flux donnés à la Fig.~\ref{fig:sch} résume l'approche +du schéma STABYLO (pour STeganography with Adaptive, Bbs, binarY embedding +at LOw cost). L'embarquement est synthétisé à la Fig.~\ref{fig:sch:emb} et +l'extraction à la Fig.~\ref{fig:sch:ext}. + +\begin{figure*}%[t] + \begin{center} + \subfigure[Data Embedding]{ + \begin{minipage}{0.4\textwidth} + \begin{center} + %\includegraphics[scale=0.45]{emb} + \includegraphics[scale=0.4]{images/emb} + \end{center} + \end{minipage} + \label{fig:sch:emb} + } +\hfill + \subfigure[Data Extraction]{ + \begin{minipage}{0.49\textwidth} + \begin{center} + \includegraphics[scale=0.4]{images/dec} + \end{center} + \end{minipage} + \label{fig:sch:ext} + }%\hfill + \end{center} + \caption{Présentation générale de STABYLO} + \label{fig:sch} +\end{figure*} + + +La sécurité de l'encryptage est garantie par le système asymmétrique +de Blum-Goldwasser~\cite{Blum:1985:EPP:19478.19501} basé sur le PRNG +Blum Blum Shub~\cite{DBLP:conf/crypto/ShubBB82}. +Ainsi, à partir d'une clef $k$ et un message \textit{mess}, +ce cryptosystem construit +le message $m$. + + +\subsection{Un embarquement dans les bords}\label{sub:edge} +L'idée d'embarquer dans des bords dans une image +repose sur le fait que les pixels de ceux-ci représentent déjà une +rupture de continuité entre pixels voisins. +Une faible modification de ceux-ci n'a donc pas un grand impact sur la qualité +de l'image, condition nécéessaire lorsqu'on prétend être indétectable. + +STABYLO est basé sur les +filtres de Canny~\cite{Canny:1986:CAE:11274.11275}, comme démarche de détection +de bords retenue pour sa complexité faible et ses possibilités d'implantation +sur plusieurs supports (GPU, FPGA notamment). Rien n'interdirait cependant +de l'appliquer à d'autres approches de détection de bord (Sobel, à base de +logique floue~\cite{KF11},\ldots). +Cette détection de bords ne considère que les $b$ +bits les plus significatifs (pratiquement $b$ vaut $6$ ou $7$) +et un masque de sélection $T$ $T=3,5,7$). +Plus élevée est la valeur de ce masque, plus grand est le nombre +de pixels de bors mais plus grossière est l'approche. +Dans le diagramme de flux, cette étape de sélection +est représentée par ``x=Edge Detection(b, T, X)''. +La section suivante montre comment le schéma s'adapte +aux valeurs de $m$ et de $x$. + +\subsection{Un embarquement adaptif}\label{sub:adaptive} +Nous argumentons que le schéma d'embarquement doit s'adapter +au message $m$ et au nombre de bits disponibles pour cet embarquement. +Deux stratégies sont possibles dans STABYLO. +Dans la première, dite \emph{adaptive}, le taux d'embarquement +(rapport entre le nombre de bits embarqués par rapport au nombre de pixels +modifiés) dépend du nombre de bits disponibles à l'issue de l'extraction +des pixels de bords. Si ce nombre de bits est inférieur au double de +la taille du message, celui-ci est découpé en plusieurs parties. +La justification de ce rapport de 1 à 2 à donné ci dessous dans la partie STC. +Dans la seconde dite \emph{fixe}, ce taux est fixe et l'algorithme augmente +iterativement la valeur de $T$ jusqu'à obtenir à nouveau deux fois plus de bits +de bords qu'il n'y en a dans le message. + +STABYLO applique alors +par défaut l'agorithme STC~\cite{DBLP:journals/tifs/FillerJF11} +pour ne modifier aussi peu que posible les bits parmi ceux dont il dispose. +Dans le cas où c'est la stratégie adaptive qui est choisie, le paramètre +$\rho$ de cet algorithme vaut 1 pour chaqun des bits. +Dans le cas contraire, la valeur de ce paramètre varie en +fonction du seuil $T$ de l'algorithme de détection de bord comme suit: +$$ +\rho_X= \left\{ +\begin{array}{l} +1 \textrm{ pour un bord défini par $T=3$,} \\ +10 \textrm{ pour un bord défini par $T=5$,} \\ +100 \textrm{ pour un bord défini par $T=7$.} +\end{array} +\right. +$$ + + + + +\subsection{Extraction du message}\label{sub:extract} +Résumée à la figure~\ref{fig:sch:ext}, l'extraction du message +reproduit le processus d'embarquement dans l'ordre inverse +puisque chaque étape est inversible. + + + +\section{Analyse de Complexité} +Dans cette section, on justifie qualificatif \og LOw cost\fg{} de STABYLO en +comparant l'ordre de grandeur de son temps d'exécution avec ceux des +principaux schémas existants à savoir HUGO~\cite{DBLP:conf/ih/PevnyFB10}, +WOW~\cite{conf/wifs/HolubF12} et UNIWARD~\cite{HFD14}. +Chacune de ces quatre méthodes commence par calculer un carte de distortion +de l'ensemble des pixels et se termine en appliquant l'algorithme STC. +Comme cette dernière étape est commune à toutes les approches, on évalue +sa complexité à part. +Dans tout ce qui suit, on considère une image carrée de taille +$n \times n$. +Les preuves de ces théorèmes sont données en annexes~\ref{anx:preuve:cplxt}. + + +\begin{theorem}\label{th:cplxt:hugo} +Le schéma HUGO a une complexité de l'ordre de +$\theta(2 \times n^2(343^2 + \ln(n)))$ +\end{theorem} + +\begin{theorem}\label{th:cplxt:wow} +Le schéma WOW a une complexité de l'ordre de +$\theta(6n^4\ln(n) + n^2)$. +\end{theorem} + + +\begin{theorem}\label{th:cplxt:uniward} +Le schéma UNIWARD a une complexité dont l'ordre est supérieur à +$\theta(6n^4\ln(n) + n^2)$. +\end{theorem} + +\begin{theorem}\label{th:cplxt:stabylo} +Le schéma STABYLO a une complexité dont l'ordre est +$\theta((5^3+4T+1)n^2)$. +\end{theorem} + + +D'après~\cite{DBLP:journals/tifs/FillerJF11}, la complexité de +STC est le l'ordre de $\theta(2^h.n)$ où $h$ +est la taille de la matrice dupliquée. Cett complexité linéaire +est donc négligeable par rapport au reste. + + +La figure~\ref{fig:compared} représente graphiquement les complexités +des étapes d'embarquement des schémas WOW/UNIWARD, HUGO, and STABYLO en +considérant des images de la taille $n \times n$ où $n$ varie entre +512 et 4096. L'axe des $y$ est exprimé selon une échelle logarithmique. +Cette figure illustre bien le fait que le qualificatif de \og LOw cost\fg{} +attribué à STABYLO. +\begin{figure} +\begin{center} +\includegraphics[scale=0.4]{images/complexity} +\end{center} +\caption{Evaluation de la complexité de WOW/UNIWARD, HUGO et STABYLO} +\label{fig:compared} +\end{figure} + + + + -- 2.39.5