abstract, conclusion

[HindawiJournalOfChaos.git] / IH / di3.tex

\section{The $\mathcal{DI}_3$ Steganographic Process}
\label{di3sec}
In~\cite{bcfg12a:ip,bcfg12b:ip}, a new steganographic algorithm named  $\mathcal{DI}_3$ is presented. It is 
inspired from $\mathcal{CIW}_1$ and $\mathcal{CIS}_2$ respectively published
in~\cite{fgb11:ip} and~\cite{gfb10:ip}, and recalled previously in this article. 
Compared to the first one, $\mathcal{DI}_3$ is a steganographic scheme, 
not just a watermarking technique. That is, in our understanding, it can embed more than one bit. Unlike
$\mathcal{CIS}_2$, which requires embedding keys with three strategies, only one sequence
is required for $\mathcal{DI}_3$, so it is easier to implement. Indeed 
$\mathcal{DI}_3$ is a faster instance of $\mathcal{CIS}_2$, as
there is no message mixing in it.
 $\mathcal{DI}_3$ is well-defined mathematically and its security is evaluated in~\cite{bcfg12a:ip},
whereas~\cite{bcfg12b:ip} provides algorithms and investigates its robustness, comparing it to 
some well-known watermarking schemes, namely the 
YASS~\cite{DBLP:conf/ih/SolankiSM07}, 
 nsF5~\cite{DBLP:conf/mmsec/FridrichPK07}, MMx~\cite{DBLP:conf/ih/KimDR06}, and HUGO~\cite{DBLP:conf/ih/PevnyFB10} algorithms 
 detailed in the Appendix~\ref{AppendixIH}.


\subsection{Mathematical definitions and notations}
\label{sec:math-def}

New notations and terminologies must be introduced another time in order to be able to define 
mathematically the $\mathcal{DI}_3$ steganographic process. They are provided thereafter.


\begin{Def}
The \emph{support of a finite sequence} $S$ of $n$ terms is the finite set
$\mathsf{S}(S)=\left\{ S^k, k < n \right\}$ containing all the distinct
values of $S$. Its cardinality is s.t. $\#\mathsf{S}(S) \leqslant n$.
\end{Def}

\begin{Def}\label{def:injective-sequence}
A finite sequence $S \in \mathds{S}_\mathsf{N}$ of $n$ terms is \emph{injective}
if $n = \#\mathsf{S}(S)$.
It is \emph{onto}
if $N = \#\mathsf{S}(S)$. Finally, it is bijective if and only if it is both
injective and onto, so $n=N = \#\mathsf{S}(S)$.
\end{Def}

 ``$S$ is injective'' reflects the fact that  all the $n$ terms of
the sequence $S$ are distinct, while ``$S$ is onto'' means
that all the values of the set $\llbracket 1;\mathsf{N}\rrbracket$
are reached at least once.




\subsection{The new $\mathcal{DI}_3$ process}
\label{sec:new-process-di-1}

In this section, the new algorithm introduced in~\cite{bcfg12a:ip} and studied 
in~\cite{bcfg12b:ip} is recalled. 
Let $\mathsf{P} \in \mathds{N}^\ast$ be the width, in term of bits, of the
  message to embed into the cover media.
 $\lambda \in \mathds{N}^{\ast}$ is the number of iterations to realize,
 which is s.t. $\lambda > \mathsf{P}$.
 $x^0 \in \mathbb{B}^\mathsf{N}$ is for the $\mathsf{N}$ LSCs of a given
  cover media $C$ supposed to be uniformly distributed.
 $m \in \mathbb{B}^\mathsf{P}$ is the message to hide into $x^0$.
Finally, $S \in \mathbb{S}_\mathsf{P}$ is a strategy such that the
  finite sequence $\left\{S^k, k \in \llbracket \lambda - \mathsf{P}
  +1;\lambda \rrbracket\right\}$ is injective.


\begin{Rem}
The width $\mathsf{P}$ of the message to hide into the LSCs of the cover media
$x^0$ has to be far smaller than the number of LSCs.
\end{Rem}



The proposed information hiding scheme is defined by:
\begin{Def}[$\mathcal{DI}_3$ Data hiding scheme]\ 
\label{def:process-DI-1}
$\forall (n,i,j) \in
\mathds{N}^{\ast} \times \llbracket 0;\mathsf{N-1}\rrbracket \times \llbracket
0;\mathsf{P-1}\rrbracket$:

\begin{equation*}
\begin{array}{l}
x_i^n=\left\{
\begin{array}{ll}
x_i^{n-1} & \text{ if }S^n\neq i \\
m_{S^n} & \text{ if }S^n=i.
\end{array}
\right.
\end{array}
\end{equation*}
\end{Def}


The stego-content is the Boolean vector $y = x^\lambda \in
\mathbb{B}^\mathsf{N}$, which will replace the former LSCs, 
that is, LSCs of the cover media are replaced by the
vector $y$.


\subsection{Security study}

A security study of the $\mathcal{DI}_3$ steganographic process has been realized 
in~\cite{bcfg12a:ip}. Conclusion of this study is summarized thereafter.

\begin{Prop}
$\mathcal{DI}_3$ is stego-secure.
\end{Prop}

This proof of this proposition, provided in~\cite{bcfg12a:ip}, holds for
the following restrictive hypotheses:

\begin{description}
\item[Distribution of LSCs.]
We have supposed that $x^0 \sim
\mathcal{U}\left(\mathbb{B}^\mathsf{N}\right)$
to prove the stego-security of the data hiding process
$\mathcal{DI}_3$.
This hypothesis of the uniform distribution
of the least significant coefficients is obviously
 the most restrictive one, but it can 
be obtained at least partially in two possible manners. 
Either a channel that appears to be random (for instance, when
applying a chi squared test or for test batteries) can be found in the media. Or a systematic process
can be applied on the images to obtain this uniformity, as follows.
Before embedding the hidden message, all the original LSCs must be replaced by randomly
generated ones, hoping so that such cover media will be considered to be noisy by any given attacker. 
Let us remark that, in
the field of data anonymity for privacy on the 
Internet,  we are in the
``watermark-only attack'' framework.
As it has been recalled  in
Table~\ref{table:attack-classification},
in that framework,
the attacker has only access to stego-contents, having so no knowledge
of the original media (\emph{i.e.}, before introducing the message in the LSCs random channel).
% These considerations, which have been
% deepened in later publications, will be discussed more largely at
% the end of this chapter.
\item[Distribution of the messages $m$.]
 In order to prove the stego-security of the data hiding
 process
$\mathcal{DI}_3$, we have supposed that  $m \sim
\mathcal{U}\left(\mathbb{B}^\mathsf{P}\right)$. This hypothesis 
of the uniform distribution of the message to hide is not
really restrictive. Indeed, to encrypt the message before its
embedding into the LSCs of cover media, which is usually required
for obvious security reasons, is sufficient to achieve this goal. To say 
it different, in order to be in the conditions of applications of the process
$\mathcal{DI}_3$, the hidden message must be encrypted.
\item[Distribution of the strategies $S$.]
 To prove the stego-security of the data hiding
 process
$\mathcal{DI}_3$, we have finally supposed that  $S \sim
\mathcal{U}\left(\mathbb{S}_\mathsf{P}\right)$.  This hypothesis is not
restrictive too, as any cryptographically secure
pseudorandom generator (PRNG)
satisfies this property. With such PRNGs, it is impossible in 
polynomial time, to make the distinction between  random numbers and  numbers provided by
these generators. For instance, \emph{Blum Blum Shub
(BBS)}~\cite{junod1999cryptographic}, \emph{Blum Goldwasser (BG)}~\cite{prng-Blum-goldwasser}, 
or \emph{ISAAC}~\cite{Jenkins1996} are convenient here.
\end{description}

After this theoretical study of the 
$\mathcal{DI}_3$ steganographic process realized in~\cite{bcfg12a:ip},
we have investigated practical aspects, discussing about its
concrete implementation and evaluating its robustness in~\cite{bcfg12b:ip},
while article~\cite{bcfg12a:ip} already mentioned deals with its
ability to face steganalyzers. These practical aspects are summarized below.


\subsection{Implementing the $\mathcal{DI}_3$ scheme}


In the algorithms recalled here, the following notations are used:
$S$ denotes the embedding and extraction strategy, 
 $H$ the host content or the stego-content depending of the context.
  $LSC$ stands for the old or new
LSCs of the host or stego-content $H$ depending of the context too.
 $N$ denotes the number of LSCs,
 $\lambda$ the number of iterations to realize,
 $M$ the secret message, and
 $P$ the width of the message (number of bits).


The $\mathcal{DI}_3$ scheme theoretically presented in~\cite{bcfg12a:ip} has been
practically described by three main algorithms in~\cite{bcfg12b:ip}:
\begin{enumerate}
  \item Algorithm~\ref{algo:strategy}
generates the embedding strategy, part of the embedding key (with the LSCs and
the number of iterations).
\item Algorithm~\ref{algo:embed} embeds the message into
the LSCs of the cover media using the strategy. The 
strategy has been generated by the first algorithm and the same number of
iterations is used.
\item Algorithm~\ref{algo:extract} extracts
the secret message from the LSCs of the media (the stego-content) using the
strategy, which constitutes with the message length the extraction key.
\end{enumerate}   

Two other complementary functions must be used:


\begin{enumerate}
  \item Algorithm~\ref{algo:signification-function}, which
  allows to extract MSCs, LSCs, and passive coefficients from the host content.
  Its implementation is based on the concept of signification
  function described previously.
 \item Algorithm~\ref{algo:build-function}
 rebuilds the new host content (the stego-content) from the corresponding MSCs,
 LSCs, and passive coefficients. This function realizes the opposite operation of Algorithm~\ref{algo:signification-function}.
\end{enumerate}

\begin{Rem}
These two algorithms depend of the definition of the MSCs,
 LSCs, and passive coefficients, which can correspond to
a spatial or frequency description of the host content. This is why they are
not documented here.
\end{Rem}



\begin{algorithm}[h]
\tcc{$S$ is a sequence of
integers into $\llbracket 0,P-1 \rrbracket$, such that $(S_{n_0},\ldots,S_{n_0+P-1})$ is injective on
$\llbracket 0,P-1 \rrbracket$.}
\KwResult{$S$: The strategy, integer sequence $(S_0,S_1,\ldots)$.}
\Begin{
$n_0 \longleftarrow L - P + 1$\;
\If{$P > N$ OR $n_0 < 0$}{
\Return{ERROR}}
$S \longleftarrow$ Array of width $\lambda$, all values initialized to 0\;
$cpt \longleftarrow 0$\;
\While{$cpt < n_0$}{
$S_{cpt} \longleftarrow $Random integer in $\llbracket 0,P-1
\rrbracket$.\;
$cpt \longleftarrow cpt + 1$\;}
$A \longleftarrow$ We generate an arrangement of $\llbracket 0,P-1
\rrbracket$\;
\For{$k \in \llbracket 0,P-1\rrbracket$}{
$S_{n_0 + k} \longleftarrow A_k$\;
}
\Return{$S$}
}
\caption{$strategy(N,P,\lambda)$}
\label{algo:strategy}
\end{algorithm}



\begin{algorithm}[h]
\KwResult{New LSCs with embedded message.}
\Begin{
$N \longleftarrow$ Number of LSCs in $LSC$\;
$P \longleftarrow$ Width of the message $M$\;
\For{$k \in \llbracket 0,\lambda\rrbracket$}{
$i \longleftarrow S_k$\;
$LSC_{i} \longleftarrow M_i$\;
}
\Return{$LSC$}
}
\caption{$embed(LSC, M, S, \lambda)$}
\label{algo:embed}
\end{algorithm}

\begin{algorithm}[h]
\KwResult{The message to extract from $LSC$.}
\Begin{
$RS \longleftarrow$ The strategy $S$ written in reverse order.\;
$M \longleftarrow$ Array of width $P$, all values initialized to 0\;
\For{$k \in \llbracket 0,\lambda\rrbracket$}{
$i \longleftarrow RS_k$\;
$M_{i} \longleftarrow LSC_i$\;
}
\Return{$M$}
}
\caption{$extract(LSC, S, \lambda,P)$}
\label{algo:extract}
\end{algorithm}


\begin{algorithm}[h]
\KwData{$H$: The original host content.}
\KwResult{$MSC$: MSCs of the host content $H$.}
\KwResult{$PC$: Passive coefficients of the host content $H$.}
\KwResult{$LSC$: LSCs of the host content $H$.}
\Begin{
\tcc{Implemented by the user.}
\Return{$(MSC,PC,LSC)$}
}
\caption{$significationFunction(H)$}
\label{algo:signification-function}
\end{algorithm}

\begin{algorithm}[h]
\KwResult{$H$: The new rebuilt host content.}
\Begin{
\tcc{Implemented by the user.}
\Return{$(MSC,PC,LSC)$}
}
\caption{$buildFunction(MSC,PC,LSC)$ )\label{algo:build-function}}
\end{algorithm}


\subsection{Evaluation against steganalyzers}\label{section:steganalysis}


The steganographic scheme detailed in~\cite{bcfg12a:ip}
 has been compared to 
state of the art steganographic approaches, namely
YASS~\cite{DBLP:conf/ih/SolankiSM07},
HUGO~\cite{DBLP:conf/ih/PevnyFB10}, and
nsF5~\cite{DBLP:conf/mmsec/FridrichPK07} detailed in the Appendix~\ref{AppendixIH}.
This study, realized in~\cite{bcfg12a:ip}, is summarized thereafter.

The steganalysis is based on the BOSS image
database~\cite{DBLP:conf/ih/BasFP11}, 
which consists in a set of 10 000 512x512 greyscale images. 
We have randomly selected 50 of them to compute the cover set.
Since YASS and nsF5 are dedicated to JPEG 
support, all these images have been firstly translated into JPEG format
thanks to the \verb+mogrify+ command line. 
To allow the comparison between steganographic schemes, the relative payload
is always set with 0.1 bit per pixel. Under that constrain,
the embedded message $m$ is a sequence of 26214 randomly generated bits. 
This step has led to distinguish four sets of stego contents, one for 
each steganographic approach.

We have next used in~\cite{bcfg12a:ip} the steganalysis tool developed by the HugoBreakers 
team~\cite{holmes11,ensemble11} based on AI classifier and which won 
the BOSS competition~\cite{DBLP:conf/ih/BasFP11}. 
Table~\ref{table:holme} summarizes these steganalysis results expressed 
as the error probabilities of the steganalyser, as they are given in~\cite{bcfg12a:ip}. The errors are the mean 
of the false alarms and of the missed detection. An error that is closed 
to 0.5 signifies that deciding whether an image contains 
a stego content is a random choice for the steganalyser. 
Conversely, a tiny error denotes that the steganalyser can easily classify
stego content and non stego content.   

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Steganographic Tool & $\mathcal{DI}_3$ & YASS & HUGO & NsF5 \\
\hline
Error Probability   & 0.4133& 0.0067& 0.495 & 0.47 \\
\hline
\end{tabular}
\end{center}
\caption{Steganalysis results of HugoBreakers steganalyser applied on 
steganographic scheme}\label{table:holme}
\end{table}


The best result is obtained by HUGO, which is closed to the perfect
steganographic approach to the considered steganalyser, since the error is about 0.5. However, even if 
the approach detailed in~\cite{bcfg12a:ip} has no optimization, these 
first experiments shown promising results.
% We finally notice that the HugoBreakers's steganalyser should outperform
% these results  on larger image databases, \textit{e.g.}, when applied on the
% whole BOSS image database.  
% 


\subsection{Robustness study}\label{sec:robustness-study}


This section summarizes the robustness study presented in~\cite{bcfg12b:ip}.
Each experiment is build another time on a set of 50 images, which are randomly selected
among database taken from the BOSS contest~\cite{DBLP:conf/ih/BasFP11}. 
Each cover is a $512\times 512$ greyscale digital image. 
The relative payload
is always set with 0.1 bit per pixel. Under that constrain,
the embedded message $m$ still remains a sequence of 26214 randomly generated bits. 

According to previous similar work in the
field of information hiding, we have conducted in~\cite{bcfg12b:ip} our evaluation 
following a same canvas than other robustness studies documented previously in
 this article.
We have firstly chosen some classical attacks like cropping,
compression, and rotation ones. The robustness of $\mathcal{DI}_3$ has then been tested 
by successively applying on stego content these attacks. Differences 
between the message that is extracted from the attacked image and 
the original one are then computed and expressed as percentage.

 
Different percentage of cropping
(from 1\% to 81\%) have been firstly applied on the stego image in~\cite{bcfg12b:ip}, 
Fig.~\ref{fig:robustness-results}~(c) recalls effects of such attacks.
We have then addressed robustness against JPEG and JPEG 2000 compression, 
and results are summarized in Fig.~\ref{fig:robustness-results}~(a-b). 
Attacks based on geometric transformations have finally been addressed through  
rotations: as presented previously in this article, two opposite rotations 
of angle $\theta$ are successively applied around the center of the image.
In these geometric transformations, angles range from 2 to 20 
degrees. Effects of such attacks are also recalled in
Fig.~\ref{fig:robustness-results}~(d).


\begin{figure*}[htb]

\begin{minipage}[b]{.45\linewidth}
  \centering
    \centerline{\includegraphics[width=7cm]{IH/graphs/atq-jpg}}
    \centerline{(a) JPEG effect.}
\end{minipage}
\hfill
\begin{minipage}[b]{0.45\linewidth}
  \centering
    \centerline{\includegraphics[width=7cm]{IH/graphs/atq-jp2}}
    \centerline{(b) JPEG 2000 effect.}
\end{minipage}
\\
\begin{minipage}[b]{.45\linewidth}
  \centering
    \centerline{\includegraphics[width=7cm]{IH/graphs/atq-dec}}
    \centerline{(c) Cropping attack.}
\end{minipage}
\hfill
\begin{minipage}[b]{0.45\linewidth}
  \centering
    \centerline{\includegraphics[width=7cm]{IH/graphs/atq-rot}}
    \centerline{(d) Rotation attack.}
\end{minipage}
\caption{Robustness of $\mathcal{DI}_3$ scheme facing several attacks (50 images
from the BOSS repository)}
\label{fig:robustness-results}
\end{figure*}




From all these experiments, one can conclude that
the steganographic scheme does not present obvious drawback and
resists to all the attacks:
all the percentage differences are so far less than 50\%.

% The comparison with robustness of other steganographic schemes exposed in the
% work will be realize in a complementary study, and the best utilization of each
% one in several context will be discuss.

\medskip

All researches presented in previous sections have started from the $\mathcal{CIW}_1$
process, proceeding by successively correcting its drawbacks. By doing so, we have had
a retreat from chaotic iterations. At the same time, the chaotic iterations based information
hiding (dhCI) process, whose the $\mathcal{CIW}_1$ scheme historically arises from,
continued to be investigated in parallel. Results of these investigations are detailed
in the next section.