Andreas Hasselberg

Rene Zimmermann

Christian Kraetzer

Tobias Scheidat

Claus Vielhauer

Karl Kümmel

Security of Features Describing the Visual Appearance of Handwriting Samples Using the Bio-hash Algorithm of Vielhauer against an Evolutionary Algorithm Attack

Keywords: bio-hash, evolutionary algorithm, handwriting, biometrics

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The most common approach to efficiently protect the biometric templates in a system (i.e. the reference data) is to transform the data using a one-way-function. An example for this kind of function is the biometric hash algorithm for dynamic handwriting (hereafter called Bio-Hash algorithm) from Vielhauer [START_REF] Vielhauer | Biometric User Authentication for IT Security: From Fundamentals to Handwriting[END_REF].

In [START_REF] Kümmel | Handwriting Biometric Hash Attack: A Genetic Algorithm with User Interaction for Raw Data Reconstruction[END_REF] Kümmel et al. introduce an evolutionary algorithm based attack to the template space of the Bio-Hash algorithm. The main drawbacks to this rather successful attack are the fact that it relies on user interaction and the strongly artificial look of its output.

In this paper we make two contributions to the research in this field: A) We extend the feature space used by the Bio-Hash algorithm for dynamic handwriting based user authentication. Our new features aim at the description of the visual appearance of the sample itself, something that is amiss amongst the features used until now.

B) We extend the attack from [START_REF] Kümmel | Handwriting Biometric Hash Attack: A Genetic Algorithm with User Interaction for Raw Data Reconstruction[END_REF] to a completely automated (i.e. without the user interaction required in [START_REF] Kümmel | Handwriting Biometric Hash Attack: A Genetic Algorithm with User Interaction for Raw Data Reconstruction[END_REF]) means to create synthetic handwritings which, on one hand, produces a Bio-Hash similar to the reference Bio-Hash and, on the other hand, look natural enough to be able to fool visual inspection of the input in an authentication scenario.

Our results imply for the first contribution that we introduce two (of the 13 new features) which show a strong potential to increase the attack resilience of the Bio-Hash algorithm, because they have been exceptionally hard to successfully attack in our evaluations. For the second main contribution, our improved attack generates much more realistic looking synthetic handwritings.

The paper is structured as follows: Section 2 summarizes some required basics. In section 3 the prerequisites, ideas and the algorithms to compute the 13 new features describing the visual appearance of online captured handwriting samples are presented. In section 4 the attack approach used for evaluation is described with its prerequisites and its implementation. Section 5 contains the evaluation results, while the final section 6 draws a conclusion and presents possible direction for future work.

Related Work

The template used in biometric authentication systems has to be protected for various security, legal and ethical reasons. For handwriting data, one very strong motivation for such protection is the fact that the template might contain enough information for re-engineering parts of the original biometric data, e.g. a handwritten signature. Amongst the various protection approaches one of the most prominent is the Bio-Hash algorithm of Vielhauer [START_REF] Vielhauer | Biometric User Authentication for IT Security: From Fundamentals to Handwriting[END_REF], which has been developed for handwriting, but could also be used for different biometrics (e.g. voice).

The Biometric Hash (short: Bio-Hash) algorithm was introduced by Vielhauer in [START_REF] Vielhauer | Biometric User Authentication for IT Security: From Fundamentals to Handwriting[END_REF] to generate individual, stable hash values from dynamic handwriting data as well as to perform biometric verification based on these hashes. Generally, the raw data of each dynamic handwriting sample derived from a handwriting digitizer device (e.g. Tablet PC) consists of a time-dependent sequence of physical values. Each sample point of such a sequence contains the five values horizontal pen tip position, vertical pen tip position, pen tip pressure and pen orientation angles altitude and azimuth.

During the enrollment process, n handwriting raw data samples are acquired per person. From each of n-1 raw data samples, one k-dimensional statistical feature vector containing static and dynamic features is calculated. The individual Interval Matrix (IM) consists of a vector containing a mapping interval length for each feature and an offset value vector. Both are calculated based on the analysis of intra-class variability of the person using the n-1 statistical feature vectors acquired during enrollment session. There are two parameters to influence the Bio-Hash generation by scaling the mapping intervals stored in the IM: the tolerance factor TF and tolerance vector TV. TF is a global hash generation parameter, which is a scalar value. Using the TF, the mapping intervals of all features are scaled by the same global factor. In contrast, TV provides an individual scaling of the mapping interval of every single statistical feature. Based on the statistical feature vector derived from the remaining enrollment sample of the person and its individual IM, the interval mapping function determines the reference Bio-Hash vector b ref of this user. Therefore, the feature dependent interval lengths and offsets provided by IM are used to map each of the corresponding statistical features to a hash value. Each further biometric hash is calculated in the same manner, whether it is used for biometric verification or hash generation. In case of verification, a Bio-Hash vector b, which is derived from the currently presented handwriting sample, is compared against the reference hash vector b ref by using the Hamming distance and a predefined threshold. For more details of the particular calculation steps, the interested reader is referred to [START_REF] Vielhauer | Biometric User Authentication for IT Security: From Fundamentals to Handwriting[END_REF].

In order to build the feature vector, 131 features are extracted from each raw data sample. As described in [START_REF] Makrushin | Improving reliability of biometric hash generation through the selection of dynamic handwriting features[END_REF] by Makrushin et al. the features can be classified by the signals required for calculation: 3 time based statistics features, 88 static spatial statistics features (time and order independent), 8 dynamic spatial statistics features, 22 pressure-based statistics features and 10 angles-based statistics features.

In [START_REF] Kümmel | Handwriting Biometric Hash Attack: A Genetic Algorithm with User Interaction for Raw Data Reconstruction[END_REF] Kümmel et al. introduce an attack that uses a genetic algorithm for raw handwriting data reconstruction. In a Kerckhoffs' compliant setup it assumes that the attacker gains access to the Bio-Hash b ref of a user and the corresponding IM and can therefore evaluate the fitness of artificially created handwritings by computing the Hamming distance to b ref . Despite the fact that this attack works quite well, as shown in [START_REF] Kümmel | Handwriting Biometric Hash Attack: A Genetic Algorithm with User Interaction for Raw Data Reconstruction[END_REF], it suffers from two rather severe drawbacks that are addressed in this paper: first, the attack in [START_REF] Kümmel | Handwriting Biometric Hash Attack: A Genetic Algorithm with User Interaction for Raw Data Reconstruction[END_REF] is requiring user interaction for the implementation of selected features, and second, its output looks artificial to a human observer (see an comparison between a real handwriting and the outputs of the attack tool from [START_REF] Kümmel | Handwriting Biometric Hash Attack: A Genetic Algorithm with User Interaction for Raw Data Reconstruction[END_REF] and our attack in figure 2 at the end of the document). Both drawbacks are addressed here, by introducing a new, fully automated, genetic algorithm based attack that aims at the generation of natural looking artificial handwritings.

Description of the New features

The feature extraction follows a pipeline which is reflected in the following four points summarised below: The necessary preprocessing, the determination of the baseline as well as the slope correction, the estimation of the reference lines and the approximation of the dominant slant of the written sample.

For the preprocessing, the majority of the following algorithms has its origin in OCR and is rather based on continuous handwritten samples than the discrete point sets returned by online systems for capturing of handwriting samples. Therefore, to adapt these algorithms the output generated by such systems is preprocessed in our approach by connecting the points using the Bresenham-algorithm [START_REF] Bresenham | Algorithm for computer control of a digital plotter[END_REF]. The algorithm capitalizes on the available online information from the sensor device, specifically the fact that the order of points and their coordinates are known. After this preprocessing, the sample from an online system looks much more like a real continuous writing and is usable for OCR approaches.

The line on which most of the lower ends of written letters align is called the baseline. It allows for a determination of the orientation of the writing direction. Our idea for the computation of the baseline is derived from the approach of Senior and Robinson [START_REF] Senior | An Off-Line Cursive Handwriting Recognition System[END_REF]. In contrast to [START_REF] Senior | An Off-Line Cursive Handwriting Recognition System[END_REF], our algorithm abstains from cutting descenders in the first step, because for our test samples no horizontal slope for the sample can be guaranteed. Instead our first step is to identify the point with the smallest y-coordinate in each column (of the x-y matrix representing the handwritten sample), i.e. for each distinct x-coordinate with points. Through the connection of points performed in the preprocessing, the need for an identification of unrequired points is kept to a minimum. In the worst case, every point of the sample might have been returned, as long as they were in different columns of the x-y matrix. The next step is to compute the local minima. All points except for the local minima will be discarded for the further baseline computation steps. This reduces the set of points to only the ones relevant for the baseline computation.

As starting point for further optimization a first baseline approximation is computed via linear regression on the remaining points. For these, their distance to the regression line is calculated using the Hesse normal form. Depending on whether the points lay above or below the regression line, their distances have either a positive or a negative sign. Given that only local minima were used in the computation of the first approximation of the baseline, it is safe to assume that most of these points lay close to the actual baseline and only a minority possesses a larger deviation. Therefore, we assume that with the first linear regression we already found a suitable first baseline approximation, i.e. we assume that the calculated distances have a zero mean Gaussian distribution. For this sample and the expected value it is possible to calculate the standard deviation so that all necessary parameters for the description of a Gaussian distribution are in place. Usually, the processing steps described above leave only a small number of points for further processing. Thus we approximate the Gaussian distribution with a Student's t-distribution. To compensate for outliers in distances before performing another linear regression, we cut off the outer 20 % of the distribution. For the remaining points we compute again a linear regression line, which is the final baseline returned by our approach. Here, it has to be mentioned that the baseline is already conceptually considered in [START_REF] Vielhauer | Biometric User Authentication for IT Security: From Fundamentals to Handwriting[END_REF] and used there for a preprocessing of the evaluation samples.

Finding the baseline allows for the extraction of the first seven features describing the appearance of the sample: (1) slope of the baseline, (2) angle between baseline and x-axis, (3) y-coordinate of interception of baseline and y-axis, (4) x-and (5) ycoordinate of the left interception point of baseline and bounding box, [START_REF] Kümmel | Handwriting Biometric Hash Attack: A Genetic Algorithm with User Interaction for Raw Data Reconstruction[END_REF] x-and (7) y-coordinate of the right interception point of baseline and bounding box. After the extraction of these features, all points of the sample are rotated using the angle between baseline and x-axis to create a sample aligned parallel with the x-axis.

When learning to write in a language using the Latin alphabet in school, often special paper with four helper lines is used to help the pupils to keep the letter sizes relatively constant during the writing process. These four lines are called reference lines and even without them preprinted on a sheet of paper handwriting in languages using the Latin alphabet usually aligns itself on these (trained) lines. Our approach to compute the reference lines follows in parts the histogram based approach of Yanikoglu and Sandon [START_REF] Yanikoglu | Off-Line Cursive Handwriting Recognition Using Style Parameters[END_REF]. The first step is to determine the histogram h 0 of the horizontal pixel density; one distinct x-coordinate is one distinct class in the histogram.

Step two is to smooth the resulting histogram. This is done by accumulating the sum from the two previous classes, the class itself and the two subsequent classes.

This smoothing results in a far more stable computation, since it becomes more infrequent to observe single empty classes, i.e. with the value zeros in the histogram. In contrast to Yanikoglu and Sandon [START_REF] Yanikoglu | Off-Line Cursive Handwriting Recognition Using Style Parameters[END_REF] we abstain from doing another smoothing step because the determination of the two inner reference lines is implemented here in a different way and the results using a second smoothing were too unstable in our experiments.

In cursive handwriting it is possible for the dot over an "i" to be at a higher position than the upper end of the word boundary or to even protrude in upper text lines. Therefore, starting from the center of the smoothed histogram s 0 , moving upwards and downwards, the first class not equaling null, is the upper respectively lower reference line. As we already determined the baseline in the previous pipeline step it is enough to simply rotate this line using the angle between baseline and x-axis to obtain the rotated baseline.

To approximate the core line, we use an approach similar to the approach for determining the baseline, but instead of identifying column minima we are looking for column maxima and their peak values. Unfortunately, the existence of ascenders in normal handwritten text complicates our approach. Under the assumption that letters without ascenders are more common than letters with, the majority of the maxima should be somewhere around the core line. That is why we use a sliding window of size of 15 % of the sample height (after correcting the slope) to identify the area with the majority of local maxima. For the points within this window we calculate the arithmetic mean, which is assumed to be the y-coordinate of the core line. With this all reference lines are in place and the following features can be extracted: (8) ycoordinate of the rotated baseline, (9) y-coordinate of the core line, (10) the height of ascenders, e.g. the distance between the upper reference line and the core line, (11) the height of the letter core, e.g. the distance between the core line and the baseline, (12) the height of descenders, e.g. the distance between baseline and the lower reference line.

Letters in words in cursive handwriting have the characteristic of displaying a certain slant. This slant usually lies somewhere between 20° and 130° [START_REF] Koppenhaver | Forensic Document Examination: Principles and Practices[END_REF], depending on whether the characters are more slanted to the left or the right. To determine the dominant slant, a histogram, describing the distribution of angles between a line through two consecutive points and the x-axis, is computed. The class width for this histogram is defined by us to be 1 degree. All angles not contained in the interval [20°, 130°] are neglected. For the remaining angles the arithmetic mean is calculated and returned as feature (13) -our approximation of the dominant slant of the written sample, which is also the final new feature considered in this paper.

Our Attack Approach

Like in [START_REF] Kümmel | Handwriting Biometric Hash Attack: A Genetic Algorithm with User Interaction for Raw Data Reconstruction[END_REF], which is the basis for our attack considerations, the goal of the performed attack is to create raw data of handwriting which will produce the same Bio-Hash as a specific real handwriting sample. In addition to this potential authentication impact, the attack should be fully automated (in contrast to [START_REF] Kümmel | Handwriting Biometric Hash Attack: A Genetic Algorithm with User Interaction for Raw Data Reconstruction[END_REF] where user interaction is required) and the created raw data should look like real handwriting -which does not mean to create a handwriting which looks like the original sample, because there is not enough information left in the Bio-Hash to re-create the original. The targets for our attack are on one hand an extended version of Vielhauers Bio-Hash algorithm (see [START_REF] Makrushin | Improving reliability of biometric hash generation through the selection of dynamic handwriting features[END_REF]), and on the other hand our version of this algorithm which is even further extended by the 13 new features described in section 3. Regarding the version that extracts 131 features out of the online writing sample, here our attack concentrates only on the features which are solely positional dependent, meaning features which can be calculated directly from the horizontal (x) and vertical (y) positions, plus three features which can be used to compute the bounding box of the writing. This reduces the number of features considered in this version of the Bio-Hash algorithm to 83 (out of 131).

Requirements of the attack

The attack has certain requirements: In order to create raw data, which will produce the same Bio-Hash as a specific real handwriting, some information about the chosen real handwriting is necessary (see [START_REF] Kümmel | Handwriting Biometric Hash Attack: A Genetic Algorithm with User Interaction for Raw Data Reconstruction[END_REF]). These required inputs to the attack are the Interval matrix (see section 2) and the corresponding reference Bio-Hash. This data is used to calculate a Bio-Hash vector representation of the actual synthetic raw data and also to determine the Hamming distance between this Bio-Hash and the reference Bio-Hash. That means the attacker will be able to evaluate how similar the Bio-Hash from the synthetic writing will be in regard to the reference Bio-Hash.

Algorithm layout of the attack

The attack presented here uses an evolutionary algorithm to compute improved synthetic handwritings. It extends the attack presented in [START_REF] Kümmel | Handwriting Biometric Hash Attack: A Genetic Algorithm with User Interaction for Raw Data Reconstruction[END_REF] by removing the dependence on user input and creating much more natural looking raw handwriting samples.

The initial step for the approach used in this paper is to generate the synthetic handwriting required as input for the evolutionary algorithm. We choose to let a subject write a text and extract the single characters as raw sample data to compose a dictionary that we call in the following the basic set. With such a basic set it is possible to create own words by simply concatenating individual characters drawn from the basic set. Several rules can be specified for the creation. Here, the following set of basic rules is applied:

1. Scale the character in a way that they have a similar height as the reference 2. Alignment of the characters to their base line with respect to their position on the y-axis 3. Use a fixed distance between the characters with respect to their position on the x-axis 4. Start a word with an upper-case character followed by lower case characters 5. Try to create a word with a bounding box as similar as possible to the bounding box derived from the reference Bio-Hash

The advantage of our approach is that it is possible to use the handwriting style of the basic set. Therefore, the newly created synthetic handwriting as input for the evolutionary algorithm is by design looking very natural. It has to be admitted that there are some deviations from this rule. For example the connections between letters can look unnatural since they are created by simply connecting the last point of a letter with a straight line to the first point of his successor.

In an evolutionary algorithm there are two general types of operations to change data: Mutation (1:1 operations) and recombination (n:n operations). A recombination tries to combine the positive features of different individuals together in one. The problem in this case is the computation of the features: Most of them are dependent on every single data point in the raw data, which means if two individuals are combined; the result would not have features partially of one and partially of another individual, but completely new ones. For this reason recombinations are excluded from our work and only mutations are used for our attack approach. Nevertheless, it has to be ensured that the applied mutations are capable of producing results across the whole sample space. This means especially:

-A data point can move by mutations to any location -A sample can have any number of data points -There can be any number of pen-ups in a handwriting and they can be everywhere Additionally, mutations should not impose strong degradations to the naturalness of the original synthetic handwriting. The set of mutation operations used by us is: Point change (controlled by a radius), add or remove pen up, exchange a character (from the basic set) by another, dilation of a handwriting in width and/or height, rotation (of writing or character), changes of the slant (writing or character) and slight movements of a whole character. It has to be admitted that the sample space would only fully covered if the char-change-mutation would be able to create any number of data points, which is not the case in our work. Even so, the sample space is covered enough which is why there is no need for the implementation of add-character or delete-character mutations.

In the evolutionary algorithm, the fitness function for the rating of a generated synthetic writing is the hamming distance to the reference Bio-Hash and as selection method elitism is applied with parameterization of 50%. Thereby, only the best 80 individuals out of a generation of a total of 160 synthetic writing samples are carried over into the next generation.

Results

The goal of our evaluations is to determine, whether the new features introduced in section 3 improve the security in regards to the attack introduced in section 4. Due to the fact that the current Matlab implementation of the attack is not optimized for fast processing, the computation time for an attack can take over three days of time, depending on the number of sample points in the writings and the performance of the hardware. Since we only had a limited amount of time to conduct our evaluation; only attacks on seven sample signatures are performed here. Every attack is parameterized with 350 generations to compute the final synthetic writing.

For evaluation purposes we log the fitness of every individual per generation (i.e. the hamming distance to the reference Bio-Hash) and for every feature per generation the number of synthetic handwriting samples which implement the feature incorrectly, i.e. which do not achieve a feature value close enough to the reference Bio-Hash to successfully authenticate this feature.

A first approach to evaluate the usefulness of the new features against the attack presented in this paper is to survey if and how often a feature could be successfully created / implemented in the generated synthetic samples. This is of great interest because if a feature cannot be implemented in a synthetic writing it is very secure. In contrast, if most mutations lead to a correct implementation it would be very insecure. Using the number of incorrect implementations for every feature, a hit-score is computed in every generation. For the list of hit scores computed for a feature, a tendency indicator is created for every generation by subtracting the value for the current generation by its successor. A positive value for this tendency indicator signals an improvement for the new generation. A negative number implies degradation. At the end, out of the computed tendency indicators a global tendency for the feature is computed. Since only the correct implementations are of interest, only positive value tendency indicators are added up. The computed number is not the number of correct implementations of this feature, but gives nevertheless a value to compare the old and the new features in regards to their reachability. The hit-score average for the old features is 287.62 while the average for the new features is 349.40. These values lead to a first impression that the new features are far worse than the old ones. However there is a special case which can distort the basis data, which is when a feature was correctly implemented in every individual of the first generation and the implementation rate never degraded. In such a case the feature was correct in every instance of a synthetic writing, but never added something to the hit-score. To take a closer look onto this problem; these cases are counted for every feature in every of the seven attack simulations, class-divided for old and new features and normalized, i.e. divided by the number of attack simulations and number of features. The resulting values are 1.08 for the old and 0.62 for the new features. This leads to the conclusion that, although the hit score is far worse for the new features, we cannot conclude that the new features are performing worse than the old ones.

The hit-score is an attempt to compare the two categories: old features and the new features introduced in this paper. However, one could take a single feature and compare it to the rest of the features. In this case two of the new features are very noticeable: While most of the features seem to be reproducible with average difficulty, the third (y-coordinate of interception of baseline and y-axis) and the fifth feature (ycoordinate of the left interception point of baseline and bounding box) create in a considerable proportion of the attack simulations the special case that not a single synthetic writing implemented them correctly. While in case of the fifth feature three out of seven attacked hashes resulted in not a single correct implementation; the third feature showed no correct implantation in five out of seven attacked hashes. Based on our evaluation data no other feature, neither in the old nor in the new set, created such a special case this often. This indicates that these two new features show a strong potential to increase the attack resilience of the Bio-Hash algorithm.

6

Summary and Future Work

Our evaluations show, that like the old feature set described in [START_REF] Makrushin | Improving reliability of biometric hash generation through the selection of dynamic handwriting features[END_REF], every new feature can be implemented correctly in a synthetic writing created with our attack. However, we cannot say that the older features are more secure than the new ones in regards to the presented attack, or otherwise. Nevertheless, it was shown, that two features of the new ones seem to be exceptionally secure. Further tests should be done to support or reject this observation and to evaluate what makes these features more secure than the rest.

In regards to the outcomes of the attacks: The synthetic handwriting as output of the attack looks for the most part very naturally. An example for such a synthetic writing is shown in Figure 1. Nevertheless, it has to be admitted that in some cases unnatural characteristics, e.g. a straight linking line between two letters, are created. Regarding open issues for future work, the first step should be the extension of the evaluation set used. The number of seven sample signatures used as attack target here are suitable for first indications on the performance of the new features and attack, but statistically significant evaluations would require larger variance.

Also, a wider variety in the basic set used as input for the evolutionary algorithm (and therefore a more diverse starting point for the attack) should be considered. This could be achieved by using handwriting samples from different persons in contrast to only one person used in this paper. A drawback might be that the output artificial writing might show a much stronger divergence regarding different instances of the same latter and would therefore lose some of its natural look.

Figure 1 :

 1 Figure 1: Examples for real (left) and artificially created handwriting -in the middle an output of the attack tool from [6] and right an output of the attack introduced here

Acknowledgements

This work is supported by the German Federal Ministry of Education and Research (BMBF), project "OptiBioHashEmbedded" under grant number 17N3109. The content of this document is under the sole responsibility of the authors. We also like to thank Prof. Jana Dittmann of the Otto-von-Guericke University Magdeburg and the StepOver GmbH for supporting the project "OptiBioHashEmbedded".


Hieu Cuong Nguyen

Stefan Katzenbeisser

Detecting Resized Double JPEG Compressed Images -Using Support Vector Machine

Keywords: SVM, classification, image forensics, re-sampling

Since JPEG is the most widely used compression standard, detection of forgeries in JPEG images is necessary. In order to create a forged JPEG image, the image is usually loaded into a photo editing software, manipulated and then re-saved as JPEG. This yields to double JPEG compression artifacts, which can possibly reveal the forgery. Many techniques for the detection of double JPEG compressed images have been proposed. However, when the image is resized before the second compression step, the blocking artifacts of the first JPEG compression are destroyed. Therefore, most reported techniques for detecting double JPEG compression do not work for this case. In this paper, we propose a technique for detecting resized double JPEG compressed (called RD-JPEG) images. We first identify features that can discriminate RD-JPEG images from JPEG images and then use Support Vector Machines (SVM) as a classification tool. Experiments with many RD-JPEG images with different quality and scaling factors indicate that our technique works well.

Introduction

Due to the large number of available image processing tools, digital images can easily be altered without leaving visual evidence. Therefore, developing techniques for judging the authenticity of digital images became an urgent need. There are many types of image forgeries, which can be detected by different image forensic methods [START_REF] Farid | Image forgery detection[END_REF]. Since JPEG is the most popular image type and it is supported by many applications, it is worthwhile to develop forensic techniques for JPEG images.

Although there are many ways of making forgeries in a JPEG image, most share three main steps: 1) loading the JPEG image which is compressed by quality factor QF 1 to a photo editing software, 2) manipulating this image and 3) re-compressing it as a JPEG file with quality factor QF 2 . Consequently, the forged image is doubly JPEG compressed (called D-JPEG). Detecting artifacts of double JPEG compression is an important step to judge whether a JPEG image is authentic. To this end, several techniques have been developed [START_REF] Lukáš | Estimation of Primary Quantization Matrix in Double Compressed JPEG Images[END_REF][START_REF] Popescu | Statistical Tools for Digital Image Forensics[END_REF][START_REF] Lin | Fast, automatic and fine-grained tampered JPEG image detection via DCT coefficient analysis[END_REF][START_REF] Bianchi | Improved DCT coefficient analysis for forgery localization in JPEG images[END_REF][START_REF] Fu | A generalized Benford's law for JPEG coefficients and its applications in image forensics[END_REF][START_REF] Li | Detecting doubly compressed JPEG images by using Mode Based First Digit Features[END_REF][START_REF] Chen | A machine learning based scheme for double JPEG compression detection[END_REF]. The authors in [START_REF] Lukáš | Estimation of Primary Quantization Matrix in Double Compressed JPEG Images[END_REF][START_REF] Popescu | Statistical Tools for Digital Image Forensics[END_REF] found that when QF 1 is different from QF 2 , periodic artifacts are present in the histograms of the DCT coeffi-cients of D-JPEG images. The periodicity can be recognized in the Fourier transform through peaks in the spectrum. Lin et al. [START_REF] Lin | Fast, automatic and fine-grained tampered JPEG image detection via DCT coefficient analysis[END_REF] expanded the global approach of [START_REF] Popescu | Statistical Tools for Digital Image Forensics[END_REF] by locating the tampered regions in D-JPEG images. Bianchi et al. [START_REF] Bianchi | Improved DCT coefficient analysis for forgery localization in JPEG images[END_REF] proposed an enhanced version of [START_REF] Lin | Fast, automatic and fine-grained tampered JPEG image detection via DCT coefficient analysis[END_REF], leading to an improvement of the accuracy of the algorithm. The authors in [START_REF] Fu | A generalized Benford's law for JPEG coefficients and its applications in image forensics[END_REF][START_REF] Li | Detecting doubly compressed JPEG images by using Mode Based First Digit Features[END_REF] showed that the distribution of the most significant digit of the DCT coefficients in JPEG images follows the generalized Benford distribution. This distribution is very sensitive to double JPEG compression and this property can be applied to detect D-JPEG images. Chen et al. [START_REF] Chen | A machine learning based scheme for double JPEG compression detection[END_REF] proposed a set of image features, which have subsequently been evaluated by a SVM based classifier.

A limitation of these techniques is that they cannot detect D-JPEG images if the JPEG images are cropped before the second compression step is applied. The reason is that the corresponding blocking grids in the first compression and in the second compression are no longer aligned. In order to overcome this limitation, some other techniques have been proposed [START_REF] Luo | A Novel Method for Detecting Cropped and Recompressed Image Block[END_REF][START_REF] Chen | Image Tampering Detection by Blocking Periodicity Analysis in JPEG Compressed Images[END_REF][START_REF] Bianchi | Detection of Nonaligned Double JPEG Compression Based on Integer Periodicity Maps[END_REF]. In [START_REF] Luo | A Novel Method for Detecting Cropped and Recompressed Image Block[END_REF] a blocking artifact characteristic matrix (BACM) is computed to measure the symmetric representation of the blocking artifacts introduced by JPEG compression. Since the symmetry of the BACM of a JPEG image is destroyed after the image is cropped, the BACM can be used as evidence for detecting cropped double JPEG compressed images. The authors of [START_REF] Chen | Image Tampering Detection by Blocking Periodicity Analysis in JPEG Compressed Images[END_REF] model the linear dependency of the "within-block" pixels (pixels that are not on the border of segmented 8×8 image blocks), compute the probability of the pixel being linearly correlated to its neighbors and form the map of the probabilities of all pixels in the image. The map is converted to Fourier domain and several statistical features from the different peak energy distribution are extracted in order to discriminate cropped D-JPEG images from non-cropped D-JPEG images. A simple yet reliable technique to detect the presence of cropped double JPEG compression has been introduced in [START_REF] Bianchi | Detection of Nonaligned Double JPEG Compression Based on Integer Periodicity Maps[END_REF]. This technique is based on the observation that the DCT coefficients exhibit an integer periodicity when they are computed according to the grids of the primary JPEG compression.

Although [START_REF] Luo | A Novel Method for Detecting Cropped and Recompressed Image Block[END_REF][START_REF] Chen | Image Tampering Detection by Blocking Periodicity Analysis in JPEG Compressed Images[END_REF][START_REF] Bianchi | Detection of Nonaligned Double JPEG Compression Based on Integer Periodicity Maps[END_REF] work well for detecting cropped double JPEG compressed images, they are defeated if the images are resized before the second compression. The reason is that due to the effect of re-sampling, the blocking artifacts will be broken. The authors of [START_REF] Sutthiwan | Anti-Forensics of Double JPEG Compression Detection[END_REF] demonstrated the influence of resizing on the detection results of [START_REF] Li | Detecting doubly compressed JPEG images by using Mode Based First Digit Features[END_REF][START_REF] Chen | A machine learning based scheme for double JPEG compression detection[END_REF]. To the best of our knowledge, there are only a few techniques for detecting resized double JPEG compressed (RD-JPEG) images [START_REF] Kirchner | On resampling detection in re-compressed images[END_REF][START_REF] Liu | A new approach for JPEG resize and image splicing detection[END_REF][START_REF] Bianchi | Reverse engineering of double JPEG compression in the presence of image resizing[END_REF]. Kirchner and Gloe [START_REF] Kirchner | On resampling detection in re-compressed images[END_REF] apply a re-sampling detection technique (which was originally designed to work with uncompressed images) to JPEG images and analyze how the JPEG compression affects the detection output. A limitation of [START_REF] Kirchner | On resampling detection in re-compressed images[END_REF] is that the detection rates when applied to RD-JPEG images are very low if QF 1 is much larger than QF 2 . Besides, if the JPEG images are down-sampled before the second compression, the technique is mostly defeated. The technique [START_REF] Liu | A new approach for JPEG resize and image splicing detection[END_REF] extracts neighboring joint density features and applies SVM to them. Although this technique works for both up-sampled images and down-sampled images by different interpolation methods, it is analyzed by the authors only for quality factors (both QF 1 and QF 2 ) of 75 and no information on false positives is given. Bianchi and Piva [START_REF] Bianchi | Reverse engineering of double JPEG compression in the presence of image resizing[END_REF] proposed an algorithm, which can be sum-marized by some steps: 1) estimate the candidate resizing factor; 2) for each candidate factor, undo the image resizing operation and measure the NLDP (near lattice distribution property); 3) if the result is greater than a predefined threshold, label the image as resized double JPEG compressed. Furthermore, the technique [START_REF] Bianchi | Reverse engineering of double JPEG compression in the presence of image resizing[END_REF] can estimate both the resize factor and the quality factor of the first JPEG compression of the analyzed image. The experimental results in [START_REF] Bianchi | Reverse engineering of double JPEG compression in the presence of image resizing[END_REF] show that it surpasses [START_REF] Kirchner | On resampling detection in re-compressed images[END_REF] in the same test condition, but similar to [START_REF] Kirchner | On resampling detection in re-compressed images[END_REF], it seems more difficult to detect when QF 1 is much larger than QF 2 .

In this paper, we propose a new technique to detect RD-JPEG images. The technique first reveals specific features of JPEG images by using a re-sampling detector. These features are subsequently fed to SVM-based classifiers in order to discriminate RD-JPEG images from JPEG images. In comparison to [START_REF] Kirchner | On resampling detection in re-compressed images[END_REF], our technique does not require to distinguish in detail the peaks caused by JPEG compression from the peaks caused by re-sampling. In comparison to [START_REF] Liu | A new approach for JPEG resize and image splicing detection[END_REF], our approach does not need to extract complex image features for classification. The technique [START_REF] Bianchi | Reverse engineering of double JPEG compression in the presence of image resizing[END_REF] consists of some intricate steps, which mostly use for the purpose of reverse engineering of resized double JPEG compressed images.

In Section 2, we briefly introduce state-of-the-art re-sampling detection techniques. Re-sampling detection is an important step of our technique and any of the mentioned re-sampling detectors can be used in our construction. The proposed detection algorithm for RD-JPEG images is explained in Section 3 and experimental results are shown in Section 4. Lastly, the paper is concluded in Section 5.

Techniques for Image Re-sampling Detection

To create a convincing forged image, the geometry of the image or some portions of it is often transformed. Once a geometric transformation (such as resizing or rotation) is applied to an image, a re-sampling process is involved. Interpolation is the central step of re-sampling in order to estimate the value of the image signal at intermediate positions to the original samples. Based on specific artifacts created by interpolation, there are several techniques to detect traces of re-sampling in digital images.

Gallagher [START_REF] Gallagher | Detection of Linear and Cubic Interpolation in JPEG Compressed Images[END_REF] realized that low-order interpolated signals introduce periodicity in the variance function of their second derivatives. Based on this observation, the author proposed a technique to detect whether an image has been re-sampled. A limitation of this technique is that it works only in the case of image resizing. Using the Radon transform, Mahdian and Saic [START_REF] Mahdian | Blind Authentication Using Periodic Properties of Interpolation[END_REF] improved [START_REF] Gallagher | Detection of Linear and Cubic Interpolation in JPEG Compressed Images[END_REF] so that their technique can detect not only image resizing, but also image rotation. Popescu [START_REF] Popescu | Exposing digital forgeries by detecting traces of resampling[END_REF] noted that there are linear dependencies between neighboring pixels in re-sampled images. These correlations can be determined by using the Expectation/Maximization (EM) algorithm. The output of the algorithm is a matrix indicating the probability of every image sample being correlated to its neighbors (called p-map). The p-map of a resampled image usually contains periodic patterns, which are visible in the Fourier domain.

A drawback of [START_REF] Popescu | Exposing digital forgeries by detecting traces of resampling[END_REF] is that its computational complexity due to the use of the EM algorithm. Based on [START_REF] Popescu | Exposing digital forgeries by detecting traces of resampling[END_REF] some improved techniques have been introduced in [START_REF] Kirchner | Fast and reliable resampling detection by spectral analysis of fixed linear predictor residue[END_REF] and [START_REF] Nguyen | Robust Resampling Detection in Digital Images[END_REF]. The author in [START_REF] Kirchner | Fast and reliable resampling detection by spectral analysis of fixed linear predictor residue[END_REF] showed that the p-map of a re-sampled image is periodic and this periodicity does not depend on the prediction weights that are used to compute the correlations of neighboring pixels. Therefore, he used a predefined set of prediction weights to compute the correlation probability of every image sample and designed a fast re-sampling detection technique which bypasses the EM algorithm.

Although the values of prediction weights do not affect the periodicity of the pmap in theory, the authors in [START_REF] Nguyen | Robust Resampling Detection in Digital Images[END_REF] found that the selected set of predefined weights can strongly affect the obtained results: using one predefined set of weights for detection, peaks can be recognized in the transformed p-map, but using another set, peaks are not evident (though the periodicity exists in theory). Therefore, they use a predefined set, which is chosen through experimentation and apply the Radon transformation to the probability map of the analyzed image in order to enhance the frequency peaks and consequently the robustness of the overall technique. An example for detection of (uncompressed) re-sampled images by using [START_REF] Nguyen | Robust Resampling Detection in Digital Images[END_REF] is presented in Fig. 1. The techniques [START_REF] Gallagher | Detection of Linear and Cubic Interpolation in JPEG Compressed Images[END_REF][START_REF] Mahdian | Blind Authentication Using Periodic Properties of Interpolation[END_REF][START_REF] Popescu | Exposing digital forgeries by detecting traces of resampling[END_REF][START_REF] Kirchner | Fast and reliable resampling detection by spectral analysis of fixed linear predictor residue[END_REF][START_REF] Nguyen | Robust Resampling Detection in Digital Images[END_REF] work well for detecting traces of re-sampling in uncompressed images. However, they fail when applied to JPEG images. The reason is that JPEG compression has an effect similar to nearest neighbors interpolation and the resampling detector will get confused [START_REF] Gallagher | Detection of Linear and Cubic Interpolation in JPEG Compressed Images[END_REF]. An example can be seen in Fig. 2, which shows a JPEG image that has not been re-sampled, yet the spectrum when applying the re-sampling detector [START_REF] Mahdian | Blind Authentication Using Periodic Properties of Interpolation[END_REF] contains strong peaks.

In the next section, we propose a technique which uses one of these re-sampling detectors as the first step for detecting RD-JPEG images. Although any mentioned resampling detection technique in this section can be used, we choose [START_REF] Mahdian | Blind Authentication Using Periodic Properties of Interpolation[END_REF] because of its efficiency as well as its speed.

Proposed Technique for Detecting RD-JPEG Images

When using [START_REF] Mahdian | Blind Authentication Using Periodic Properties of Interpolation[END_REF] to detect re-sampling in both JPEG images and RD-JPEG images, we empirically found that the detection results of RD-JPEG images seem to have more peaks than those of JPEG images. An example is shown in Fig. 3. This is because the detection result of a RD-JPEG image contains not only the peaks introduced by JPEG compression, but also the peaks due to re-sampling. Nevertheless, the difference is not always easy to recognize by human eyes. Besides, it is necessary to automatically classify RD-JPEG images from JPEG images. To this end, we first apply the technique [START_REF] Mahdian | Blind Authentication Using Periodic Properties of Interpolation[END_REF] to JPEG images, and then extract the values of maximal peaks from the normalized Fourier spectrum. The extracted features are subsequently fed to SVM-based classifiers in order to discriminate RD-JPEG images from JPEG images. Since SVM is only a binary classifier, we use two different approaches to design SVM classifiers for detecting RD-JPEG images.

In the first approach, we design a single SVM classifier for directly distinguishing JPEG and RD-JPEG images, compressed by different quality factors. To this end, the features of a set of JPEG images and their re-sampled versions (the number of JPEG and re-sampled JPEG images are the same) are extracted for training a SVM classifier. This approach is simple and suitable for many situations in practice when we do not know the quality factors of the analyzed images. However, through experiments, reported in Section 4, we find that this technique works well mostly when QF 1 is lower than the QF 2 .

The second approach is based on the idea that while QF 1 of a double JPEG compressed image is usually not known to the analyst, QF 2 can reliably be computed from the bitstream of the JPEG image (see Appendix A). Thus, instead of using one single classifier for all quality factors, we design several different SVM classifiers, each of which distinguishes JPEG and RD-JPEG images for one specific value of QF 2 . Once the last quality factor of an analyzed JPEG image is known, the corresponding classifier will be applied to it. The method to design a classifier for a particular QF 2 is similar to the first approach: we first use a set of JPEG images and another set of RD-JPEG images (the numbers of images in both sets are the same and every image is compressed by QF 2 ) and then extract image features for training. In other words, the last quality factor of a tested image is first identified, and then the image will be analyzed by the corresponding qualifier. In next section, we discuss experimental results for both approaches.

Experimental Results

First, we randomly choose 200 uncompressed images from the UCID image database [START_REF] Schaefer | UCID: an uncompressed color image database[END_REF]. We create 5 datasets of JPEG images by compressing the uncompressed images with the quality factors of 40, 50, 60, 70, and 80. The JPEG images are subsequently resized by a scaling factor of 1.2 and recompressed by different factors of 40, 50, 60, 70, and 80. As a result, we obtained 5 datasets of 1000 RD-JPEG images corresponding to each dataset of JPEG images.

To test the first approach, we create a single SVM classifier by using two groups of JPEG images and RD-JPEG images (with the scaling factor of 1.2) for training. After the training process (presented in Section 3) we apply the classifier to test RD-JPEG images. In training, we consider two cases of different quality factors: 1) 100 JPEG images compressed by a quality factor of 50 and 100 RD-JPEG images re-compressed by a quality factor of 70 (QF 1 =50, QF 2 =70 and scaling factor =1.2) and 2) 100 JPEG images compressed by a quality factor of 70 and 100 RD-JPEG images re-compressed by a quality factor of 80 (QF 1 =70, QF 2 =80 and scaling factor =1.2). Analyzing the detection results (see Table 1 andTable 2), we found that the technique works well for detecting RD-JPEG images where QF 1 is smaller than QF 2 . Otherwise, when QF 1 is larger than QF 2 , the detection rate is reduced. In our experiments, the false positive rates (computed by testing the classifier on datasets of JPEG images which have been compressed by different quality factors of 40, 50, 60, 70, and 80) are lower than 10% in the first case and lower than 8% in the second case.

In a more realistic scenario, we test the techniques on the RD-JPEG images, which have been resized with a different scaling factor than the factors are used in the training process. The datasets are created in the same way as above, except the scaling factor 1.1 is used instead of 1.2 (i.e. QF 1 =70, QF 2 =80 and scaling factor =1.1). Although the detection results (in Table 3) are clearly worse compare with Table 1 and Table 2, we found that the degradation is not significant; therefore, the technique can potentially work in case the scaling factor is unknown.

In the second approach, we consider 5 different cases corresponding to a QF 2 of 40, 50, 60, 70, and 80. The case of QF 2 =40, we organize the training images into two groups: a group of 100 JPEG images (the quality factor of 40) and the other group of 100 RD-JPEG images (QF 1 =50, QF 2 =40 and scaling factor=1.2). The extracted features are used to train a SVM classifier that can be used to detect RD-JPEG images which compressed by the QF 2 of 40. We repeat this process for the other cases when QF 2 is 50, 60, 70, and 80. The detection results in testing RD-JPEG datasets are presented in Table 4. We noticed that following the second approach, the technique works well even if QF 1 is larger than QF 2 . The false positive rates are lower than 10% (9%, 8%, 5%, 6% and 3% when testing JPEG images compressed by the quality fac-tors of 40, 50, 60, 70, and 80 respectively). Since JPEG compression with a lower factor produces stronger peaks in the Fourier spectrum, it obtains higher false positives. In order to assess the influence of scaling factor, we test the proposed technique for detection of RD-JPEG images with various scaling factors. The RD-JPEG images are created by resizing JPEG images (firstly compressed by QF 1 ) of different scaling factors (from 0.6 to 1.9) and then they are recompressed (by a different quality factor QF 2 ). We consider three cases: 1) QF 1 =50 and QF 2 =70, 2) QF 1 =70 and QF 2 =80 and 3) QF 1 =70 and QF 2 =50. We create different datasets of JPEG images and RD-JPEG images and in each case, the training and testing processes of the classifiers are conducted as described before. The detection results in various scaling factors are shown in Fig. 4a. Due to missing information in the down-sampling process, the detection rates of the down-sampled images are very low. Detecting up-sampled images is possible with much higher rates. In some cases, the detection rates even reach about 100%. In this scenario, the test images are compressed with the same quality factors as the training images (but with different scaling factor). We found that scaling factors affect the detection results: typically the detection rates tend to increase.

Lastly, in a more realistic scenario, we apply the technique trained by one image type (QF 1 =70, QF 2 =80, scaling factor = 1.2) to images with different types (QF 1 =50 and QF 2 =70, QF 1 =70 and QF 2 =50, and scaling factor ranges from 0.6 to 1.9). The detection results are presented in Fig. 4b. Although the results deteriorate (compare with Fig. 4a), we found that the degradation is not significant; therefore, the technique can potentially work in a real condition.

Conclusion

In this paper, we designed a technique for detecting resized double JPEG compressed images. The technique is based on applying a re-sampling detector to JPEG images, and extracting features from strong peaks of the normalized Fourier transformation.

Then the extracted features are fed into a SVM-based classifier in order to discriminate RD-JPEG images from JPEG images. We propose two methods to design SVM classifiers: one single global classifier and several classifiers depending on the quality factor of the last compression. Although the first approach is simple and easy to use, the second approach achieves higher detection rates. In comparison with some existing techniques our technique has higher detection rates when the quality factor of the first compression is larger than the quality factor of the last compression and when detecting down-sampled images. We apply the technique to test RD-JPEG images resized with different scaling factors and found that the scaling factors can affect the detection results. In future, we will apply the technique for the detection of rotated double JPEG compressed images and use other re-sampling detectors in our technique so that we can compare their efficiency in the detector of RD-JPEG images.

Fig. 1 .

 1 Fig. 1. Shown in the top row is the original image and shown in the bottom row is the resampled image by a factor of 1.2. Shown in the left most column are the original image and the re-sampled image. Shown in the middle columns are the p-maps and the magnitudes of the Fourier transforms of the p-maps. Shown in the right most column are the Fourier transformations of the Radon transforms of the p-maps.

Fig. 2 .

 2 Fig. 2. Shown in the left is a JPEG image of Lena and in the right is the detection result by using a re-sampling detection technique.

Fig. 3 .

 3 Fig. 3. Shown in the left is the detection result of the JPEG image of Lena and in the right the detection result of the RD-JPEG version of the same image.

Fig. 4 .

 4 Detection results for RD-JPEG images by different scaling factors: (a) the quality factors of the trained images and the test images are the same, (b) the quality factors of the trained images and the test images are different.

Table 1 .

 1 Detection results using a single SVM classifier (training JPEG images compressed by QF=50 and RD-JPEG images re-compressed by QF 1 =50, QF 2 =70) for RD-JPEG images by the scaling factor of 1.2 and by different quality factors (QF 1 in rows and QF 2 in columns).

		40	50	60	70	80
	40	65.5% 91.0% 99.5% 99.5% 84.5%
	50	52.5% 80.0% 97.0% 99.0% 87.0%
	60	35.5% 77.5% 92.5% 98.5% 88.0%
	70	19.5% 67.5% 87.0% 99.0% 84.0%
	80	10.5% 45.0% 79.5% 91.5% 78.0%

Table 2 .

 2 Detection results using a single SVM classifier (training JPEG images compressed by QF=70 and RD-JPEG images re-compressed by QF 1 =70, QF 2 =80) for RD-JPEG images by the scaling factor of 1.2 and by different quality factors (QF 1 in rows and QF 2 in columns).

		40	50	60	70	80
	40	70.0% 94.0% 98.5% 99.0% 95.0%
	50	62.0% 80.0% 92.5% 98.5% 98.0%
	60	48.0% 76.0% 87.5% 96.5% 99.0%
	70	33.5% 68.0% 83.0% 93.5% 99.0%
	80	24.0% 57.0% 69.0% 81.0% 92.0%

Table 3 .

 3 Detection results using a single SVM classifier (training JPEG images compressed by QF=70 and RD-JPEG images re-compressed by QF 1 =70, QF 2 =80) for RD-JPEG images by the scaling factor of 1.1 and by different quality factors (QF 1 in rows and QF 2 in columns).

		40	50	60	70	80
	40	37.0% 57.0% 63.5% 78.0% 82.5%
	50	37.0% 58.0% 63.5% 78.5% 83.0%
	60	26.0% 48.0% 66.5% 77.5% 87.0%
	70	13.5% 43.5% 68.0% 77.5% 73.0%
	80	10.5% 39.0% 62.5% 77.0% 86.5%

Table 4 .

 4 Detection results using dedicated SVM classifiers for RD-JPEG images (depending on the quality factor of the second compression) by the scaling factor of 1.2 and by different quality factors (QF 1 in rows and QF 2 in columns).

		40	50	60	70	80
	40	95.0% 91.5% 89.5% 99.0% 98.0%
	50	90.0% 90.0% 88.5% 98.5% 99.5%
	60	89.5% 91.0% 97.5% 98.0% 100%
	70	87.5% 85.0% 95.0% 99.5% 98.0%
	80	85.0% 80.0% 96.0% 100% 99.0%

Appendix A. Determining the last quality factor of a JPEG images

The compression ratios of JPEG images are controlled by the quantization tables which used in the compression process. In this paper, we focus on images stored in the JPEG Interchange File Format (JFIF). The JFIF is the most commonly used format for JPEG data [START_REF] Kornblum | Using JPEG quantization tables to identify imagery processed by software[END_REF]. The quantization table that was used to compress an image is stored in the JFIF header [START_REF] Chandra | JPEG Compression Metric as a Quality Aware Image Transcoding[END_REF]. This table (called Ts) can be identified by using the JPEG Toolbox [START_REF] Sallee | Matlab JPEG Toolbox[END_REF].

The most commonly used standard quantization tables are published by the International JPEG Group (IJG). Based on the standard table (Tb), and the quality factor (Q), the quantization table can be computed as follows:

Conversely, when the tables Tb and Ts are known, the approximate value of the quality factor can be computed as follows [START_REF] Chandra | JPEG Compression Metric as a Quality Aware Image Transcoding[END_REF]:

Note that the function to predict the quality factor involves integer computation on the quantization table (Ts) that introduce integer rounding errors, so the value of Q' is close to Q. Following a suggestion in [START_REF] Chandra | JPEG Compression Metric as a Quality Aware Image Transcoding[END_REF], then the computed quality factor (Q') should be off by one or two.


Boris Assanovich

William Puech
email: william.puech@lirmm.fr

Iuliia Tkachenko
email: iuliia.tkachenko@lirmm.fr

Use of Linear Error-Correcting Subcodes in Flow Watermarking for Channels with Substitution and Deletion Errors

Keywords: Flow watermarking, inter-packet-delay, deletion and substitution errors, linear error-correcting codes, VT-codes, quantization index modulation. 1

An invisible flow watermarking QIM scheme based on linear errorcorrecting subcodes for channels with substitution and deletion errors is proposed in this paper. The evaluation of scheme demonstrates similar to known scheme performance but with lower complexity as soon as its implementation is mainly based on linear decoding operations.

Introduction

Recently, an active approach of traffic analysis called "flow watermarking" has been considered. This approach attempts to manipulate the statistical properties of packets flow to insert a watermark making it easier to detect the flow after passing through one or more relay hosts. To prevent an attacker to tolerate the packet delays and to eliminate embedded watermark, recent schemes have concentrated on making them "invisible". This technique has been the subject of increased interest in the past decade, because it requires low computational and communication cost while providing high accuracy in linking traffic flows. Flow watermarking is also classified as interval-based and inter-packet-delay (IPD)-based. The first type of watermarking technique is robust to packet losses but is vulnerable to the multi-flow attack [START_REF] Kiyavash | Multi-flow attacks against network flow watermarking schemes[END_REF]. The IPD-based flow watermarking, in which the watermarks are embedded into the time intervals between arrivals of packets, resists this attack [START_REF] Gong | Invisible flow watermarks for channels with dependent substitution and deletion errors[END_REF]. The drawback of this scheme is that it can cause a lot of errors in decoding during the loss of packet synchronization in the watermark detection process. A novel IPD-based flow watermarking scheme that can withstand packet losses has been done in [START_REF] Gong | Invisible flow watermarks for channels with dependent substitution and deletion errors[END_REF]. In this scheme the watermark embedding has been done with the use of quantization index modulation (QIM) [START_REF] Chen | Quantization index modulation: A class of provably good methods for digital watermarking and information embedding[END_REF]. In this approach the embedded marks are invisible. To withstand packet losses authors develop a Hidden-Markov Model (HMM) decoding scheme considering the communication channel with dependent deletion and substitution errors. However, the proposed watermark detector based on a maximum likelihood decoding algorithm paired with a forwardbackward is of high complexity and requires a lot of computational resources. In this paper we propose the alternative IPD-flow watermarking QIM scheme, based on the use of linear error-correcting codes and Varshamov-Tenengol'ts (VT) codes [START_REF] Tenengol | ts. Class of codes correcting bit loss and errors in the preceding bit[END_REF] to reduce the complexity of flow watermarking method [START_REF] Gong | Invisible flow watermarks for channels with dependent substitution and deletion errors[END_REF].

2.

Error Correcting Codes

Linear Error-Correcting Codes

Most practical error-correcting codes used today in watermarking are binary. Linearity is an important structural property of codes, allowing a concise representation of codes, the accompanying encoding and decoding rules as well as the determination of the errors are correctable/detectable. A very good survey of the theory of error-correcting codes is done in [START_REF] Sklar | Digital Communications: Fundamentals and Applications[END_REF] and the only necessary definitions are used throughout a paper. The symbols of binary linear codes are the elements of a field GF(2)={0;1} which is a code alphabet. Generally, a binary code C is defined as a set of finite sequences (vectors) ) ... Linear [n,k,d]-code is defined by following parameters: Hamming distance between any binary codewords d(x i ;x j ), weight of a codeword wt(x i ) and a code rate R=k/n. Any linear code C is completely defined by generator matrix G and parity-check matrix H whose columns and rows are respectively linearly independent. Every codeword of a linear block code C is a linear combination of the rows of a generator matrix G. The error correction capacity t of linear error-correcting codes strictly depends on its minimum distance d min =min{d(x i ;x j )} and weight distribution of a code. To perform an error correction in codeword y, corrupted by t or less errors, a rather simple method of bounded distance decoding with syndrome could be applied. It consists of following steps: the calculation of syndrome for a received word

y T H y S ⋅ = , (1)
search for a most plausible error pattern e, the estimation of transmitted codeword '

x . Decoder picks error pattern e of smallest weight satisfying S H e T = ⋅ . All procedures of decoding with syndrome are linear and only the second step requires a nonlinear operation that can be performed by look-up tables. For example, the linear [START_REF] Abdel-Ghaffar | Correcting Deletions Using Linear and Cyclic Codes[END_REF][START_REF] Chen | Quantization index modulation: A class of provably good methods for digital watermarking and information embedding[END_REF][START_REF] Chen | Quantization index modulation: A class of provably good methods for digital watermarking and information embedding[END_REF]-code С={(000000), (110100), (011010), (101110), (101001), (011101), (110011), (000111)} is completely defined by its generator matrix G [5, p.357-367]. To change its properties, a binary code can be easily modified by different techniques [START_REF] Sklar | Digital Communications: Fundamentals and Applications[END_REF]. The number of its codewords can be increased or decreased. The process of deleting a codeword from the basis of C to obtain a new code ' С , where the minimum weight of remains the same, is referred to as taking a subcode of C. It is known that linear codes as the other error correcting are applied for channels with substitution errors when transmitted symbols are received as the other symbols. However, there are channels that suffer from synchronization errors, which are associated with not receiving transmitted symbols leading to deletion errors. Therefore, there is a compelling reason to consider codes that, not only correct substitution errors, but can also recover from deletion errors. Recently it has been proved [START_REF] Abdel-Ghaffar | Correcting Deletions Using Linear and Cyclic Codes[END_REF] that linear codes and all cyclic codes can correct a single deletion or insertion error but not by both types of errors [START_REF] Abdel-Ghaffar | Correcting Deletions Using Linear and Cyclic Codes[END_REF].

As opposed to [START_REF] Abdel-Ghaffar | Correcting Deletions Using Linear and Cyclic Codes[END_REF] the application of binary linear codes for the correction of both types of errors by the same subcodes with the use of two different decoders will be proposed. In Section 2.2, we define the VT-codes and show how to get a subcode of a linear error-correcting code to combat with substitution and deletion errors.

VT-Codes for Deletion and Substitution Errors Correction

Given a parameter a, with n a ≤ ≤ 0 , the Varshamov-Tenegol'ts (VT) code VT a (n) is the set of binary words x=(x 1 …. x n ) of length n so that the equality satisfies [START_REF] Tenengol | ts. Class of codes correcting bit loss and errors in the preceding bit[END_REF]:

∑ = + ≡ n i i n a ix 1 )) 1 (mod( . ( 2
)
These codes are single error correcting codes and optimal for a=0 as it was conjectured in [START_REF] Tenengol | ts. Class of codes correcting bit loss and errors in the preceding bit[END_REF][START_REF] Varshamov | Correction code for single asymmetric errors[END_REF] and will be discussed in this paper.

For example, after calculation 000000),(001100),(010010);(011110),( 100001),( 101101),( 110011),( 110100),(111111)}. Any code VT 0 (n) can be used to communicate reliably over a channel that introduces at most one deletion in a block of length n. Levenshtein proposed a simple decoding algorithm [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions and reversals[END_REF] based on the deficiency in checksum and weight calculation for a VT code. Assume the channel code VT 0 (n) is used.

) 7 (mod 0 1 ≡ ∑ = n i i ix the code VT 0 (6) with block length n = 6 is VT 0 (6)={(
As an example, assume the code VT 0 ( 6) is used and x=(110100)∈VT 0 ( 6) is transmitted over the channel. If the first bit in x is deleted and y=(10100) is received, then the new checksum is 4, and the deficiency D=7-4=3>wt(y)=2. The decoder inserts a 1 after n-D=3 0's from the right to get (110100). Thus a very simple algorithm of low complexity can be used to decode VT 0 (n) with deletion correction.

However, in general the VT 0 (n) codes are nonlinear and the dimension k is to get a linear [n,k] is bounded by

  2 / n k ≤ [6]
. We use this result and propose an approach to find a linear substitution and deletion correction code from VT-code. The algorithm contains of the following steps: organize the codewords of VT 0 (n) code in a lexicographically order; choose the k linear independent codewords of maximum weight preserving d(x i ;x j ) ≥ d min ; produce G and H of C making the linear combinations of chosen VT-codewords. The use of this algorithm results in a subcode ' С that has at least k+1 codewords of VT 0 (n) code as soon as the linear combination of any codeword with itself makes a codeword (0…0), which is also a codeword of VT 0 (n) code. Considering the use of the proposed above algorithm, the flowing generator and parity check matrixes for a modified [6,3,3]code ' С have been made:

          = 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 ' G ,           = 1 1 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 ' H . (3)
The use of G' and H' from (3) results in a code set ' С with an increased number of codewords that belong to VT 0 (6), compared with C. If we prune the codewords that are not the codewords of VT 0 [START_REF] Abdel-Ghaffar | Correcting Deletions Using Linear and Cyclic Codes[END_REF] and a codeword with all zeros, we can make a subcode with the necessary properties * С ={(110100), (011110), (101101), (110011)} consisting of 4 codewords. * С is a linear subcode with d min =3, at the same time it is a VT 0 [START_REF] Abdel-Ghaffar | Correcting Deletions Using Linear and Cyclic Codes[END_REF] code and it can be used for error correction of one substitution and one deletion error. The examination of * С has shown, that its code rate is reduced to approximately by ½ relatively to the code rate of C. The algorithm proposed below can be applied to an arbitrary code to find the error-correcting VT-code (EC-VTC) that is a subcode * С of a linear code. For example, there is a EC-VTC, coinciding with linear error correcting code [8,2,5] [5, p.378], consisting of 4 codewords and subcoding VT 0 [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions and reversals[END_REF]. It is easily seen that it corrects one deletion and two substitution errors. It is known that the size of any VT 0 (n) is about n n 2 [START_REF] Abdel-Ghaffar | Correcting Deletions Using Linear and Cyclic Codes[END_REF], then an additional limitation on its linear properties leads to a reduction in its rate of at least by ½. However, to perform the independent decoding of codewords from EC-VTC placed in a continuous bit stream the boundaries of codewords must be known. We implement the independent decoding of them by accurately making a set of codewords r С from EC-VTC with possible reduction of a code rate R and inserting the periodic markers between the codewords as discussed in Section 3.

System Model

Scheme for Flow Watermarking

We use the described above linear codes in a flow watermarking [START_REF] Kiyavash | Multi-flow attacks against network flow watermarking schemes[END_REF], [START_REF] Gong | Invisible flow watermarks for channels with dependent substitution and deletion errors[END_REF] considering the channel with deletion and substitution errors. The proposed watermark embedding scheme, depicted in Figure 1, has the same embedder and extractor based on QIM [START_REF] Gong | Invisible flow watermarks for channels with dependent substitution and deletion errors[END_REF], but the different coding and decoding principles are used.

QIM Embedder and Extractor

For the watermark embedding the flow of IPDs is modified with the use of QIM watermaking (Fig. 1). A quantization step size ∆ , which is the distance between two quantizers, is used for QIM modulation:

   = ∆ + = ∆ = 1 if , ) 5 . 0 ( 0 if , i i w i s c s c I . ( 4
)
As packets can only be delayed by QIM Embedder, we choose parameter c to be the smallest integer so that the change in w i I would delay the i-th packet. Then w I is transmitted and after the transfer over the network it is received in the form of estimated sequence of IPDs I ˆ and received by the QIM Extractor. For the flow I ˆ processed by QIM Extractor, the following QIM demodulation function is used to recover the embedded bits s ˆ:

             > ∆ - ∆ ∆ ≤ ∆ - ∆ ∆ = 5 . 0 2 2 if ) 2 , 2 mod( 5 . 0 2 2 if ) 2 , 2 mod( ˆi i i i i i i I I I I I I s . ( 5
)
The embedding and extracting steps with possible IPDs distortion are presented in Figure 2.

Fig. 2. An example of IPDs distortion caused by jitters

As it was discussed, the scheme in Figure 1 may be regarded as a communication channel with two types of errors: substitutions and deletions. The substitution error refers to bit flips due to network jitters or packet deletions that result in merger of two IPDs. Since during QIM demodulation we map each IPD to its closest quantizer, any jitter over ∆/4 would possibly result in a substitution error (see Figure 2). The channel model developed in [START_REF] Gong | Invisible flow watermarks for channels with dependent substitution and deletion errors[END_REF] handles the dependent substitution and deletion errors. However, to simplify the decoding we assume that the dependence exists only inside the received codeword, which is a reasonable limitation, as soon as any number of packet deletions results only in the presence or in the absence of a substitution error.

For example, in Figure 2 four packets 0, 1, 2, 3 are sent, three packets 0, 2, 3 are received and packet 1 is lost. The first two IPDs 1 I and 2 I are transformed into 1 Î and the size of last IPD 2 I is changed and evaluated as 2 Î . Hence the result of channel noise is the bit received before Packet 2 that is the merged of the two intervals

∑ + = = i r j j i s s 1 ˆ
and can take only 0 or 1 binary values, where r is the index of the last successfully received packet before i-th one.

Without loss of generality, we consider the packet deletion probability P d and the packet substitution probability P s to be identical for all packets and assume that Packet 0 is always synchronized. This assumption can be easily performed by the use of so-called frame synchronization based on special markers [START_REF] Abdel-Ghaffar | Correcting Deletions Using Linear and Cyclic Codes[END_REF][START_REF] Chen | Concatenated codes for deletion channels[END_REF] or on one or more codewords received without errors. This allows the scheme to be in the synchronized state before the decoding procedure and further evaluate the distance between w and of w ˆ to decide whether the watermark is present. Considering that EC-VTC decoder is synchronized prior to decoding of a received sequence s ˆ we describe its operation principles below.

EC-VTC Decoder

The original watermark w=w 1 w 2 …w N is a sequence of bits with each element from GF(2). This sequence is divided into blocks b=(b 1 …b l ) to produce the VT-codewords x of length n by VTC Encoder. Then a codeword x is concatenated with predefined marker pattern z=z 1 z 2 …z m of length m making x m and xored with pseudo-random key sequence k w , forming a sequence s, as depicted in Fig. 1. The used key k w is a sparse sequence containing a binary 1 only in one position of block with length n+m and is applied for security and frame synchronization. Actually sequence s is made from concatenation of N codewords x m , has length

N m n M ) ( + =
and is embedded in flow IPDs. w I is transmitted and after transversing the network is received in the form of estimated sequence I ˆ and demodulated. The result sequence s ˆ is xored with key sequence k w , separated into codewords m y by marker detection [START_REF] Chen | Concatenated codes for deletion channels[END_REF] and further converted into VT-codewords y containing possible substitution or/and deletion errors. The EC-VTC Decoder performs the error-correcting decoding using one of two algorithms, depending on the number of errors in y occurred. The decision about the decoder type to be applied is based on the estimation of y length. If the only one deletion is found, the Levenshtein's decoding algorithm [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions and reversals[END_REF] is used, and if the number of deletion errors is greater than one, the maximum likelihood decoding (MLD) maximizing ) Pr(

x/y x* = is applied. The bounded distance decoding with the use of syndrome calculation is performed in case of absence of deletion errors or after their correction as well in process of frame synchronization. For example, consider that a key generator outputs the sequence of digits g=03… and a key sequence is made according to the expression k w =g mod (n+1). The received and extracted by demodulator sequence s ˆ=110100000.11110000 is then xored with key sequence k w =000000000.001000000 and decoded with the use of mapping the subcode C r ={(110100), (110011), (011110), (101101)} to data blocks b={00,01,10,11}. Hence, after marker detection, 2 codewords are obtained y 1 =110100, y 2 =11010. The calculation of (1) gives S=0 that can be used to indicate about the correct boundaries of received error-free codeword y 1 , infer the presence of synchronization and allow to start decoding by applying the Levenshtein's algorithm for the deleted zero bit in the last position of y 2 . However, if the second bit is also deleted and y 2 =1101, the evaluation of its length results in the use of MLD decoding. The use of VT-code as a subcode of any linear code preserves its minimum distance d min and does not change code performance in channel with substitution errors which is well analyzed in [START_REF] Sklar | Digital Communications: Fundamentals and Applications[END_REF]. However, the reduction in probability of codeword error when using MLD strictly depends on subcode used and on weight distribution wt(x i ) of its codewords.

Performance Evaluation

In this section we evaluate the robustness to packet losses. The proposed watermarking scheme has been evaluated by simulation of packets, generated from independent Poisson process of rate 3 packets per second and length of about 4000 packets with shifted mean of 25 ms and standard deviation of 10 ms. Network jitters was simulated as Laplace distribution with zero mean and the same deviation. The pseudorandom bits of watermarks have been encoded by subcode C r with added uniform marker z=000 and randomly embedded into 3600 flows with the use QIM modulation (4). The watermark parameters were taken similar to the values from [START_REF] Gong | Invisible flow watermarks for channels with dependent substitution and deletion errors[END_REF] to get the approximately the same number of watermark bits as N=50, n=9, M=450. Note, that the block length of EC-VTC [START_REF] Abdel-Ghaffar | Correcting Deletions Using Linear and Cyclic Codes[END_REF][START_REF] Chen | Quantization index modulation: A class of provably good methods for digital watermarking and information embedding[END_REF][START_REF] Chen | Quantization index modulation: A class of provably good methods for digital watermarking and information embedding[END_REF] with appended z marker bits results in n=9 and close to the sparsified version [START_REF] Gong | Invisible flow watermarks for channels with dependent substitution and deletion errors[END_REF] of watermark. The watermark extraction was made with the use of QIM demodulation function [START_REF] Sklar | Digital Communications: Fundamentals and Applications[END_REF] and the decoding was performed with the use of Levenshtein's, MLD and syndrome decoders.

The evaluation of the proposed scheme against packet deletions by considering the varying packet deletion probabilities P d ={0.01, 0.02, 0.03, 0.1, 0.2} has been done. The watermarks were randomly embeddered into 3600 flows. Also the other 3660 unmarked flows were used to obtain the false positive rates. The detection threshold was chosen so that the false positive rate was kept below 1% for all deletion probabilities. True Positive (TP) detection rates for deletion ratios P d gave corresponding values: 1% -0.9999, 2% -0.9998, 3% -0.9998, 10% -0.9951; 20% -0.6655.

We see that the detector has rather high true positive rates, maintaining true positive rate (TP) up to 99%, even when less than 10% of packets were deleted. However the value of TP drops to 66% when packet deletion ratio is at 20%, which is rare in a network environment. Thus, in comparison with the other IPD-based watermarking schemes [START_REF] Kiyavash | Multi-flow attacks against network flow watermarking schemes[END_REF], [START_REF] Houmansadr | RAINBOW: A Robust and Invisible Non-Blind watermark for network flows[END_REF] which suffer from desynchronization, the proposed scheme is robust against packet losses and network jitters presented as deletion and substitution errors. The use of pseudo-random key sequence on transmission side improves the security of overall scheme and provides the frame synchronization in watermarking system. To examine the visibility of proposed scheme, the Kolmogorov-Smirnov (K-S) has been performed on 4500 watermarked flows against 4500 unwatermarked flows and demonstrated the statistical invisibility of watermark according to the values of K-S distances that are below 0.03. Obviously, to defeat the multi-flow attack, as suggested in [START_REF] Kiyavash | Multi-flow attacks against network flow watermarking schemes[END_REF] the use of random function position of embedding positions can selected within the described above synchronization method.

Conclusion

An invisible flow watermarking scheme based on linear error correcting codes for channels with substitution and deletion errors, representing network jitter and packet drops, has been developed. The described scheme is based on relatively low-rate linear code, formed on the basis of proposed algorithm to create a linear error-correcting code that is a subcode of VT-code. Statistical and computational experiments demonstrate that proposed scheme is of similar to [START_REF] Gong | Invisible flow watermarks for channels with dependent substitution and deletion errors[END_REF] performance, but has a much lower complexity, as soon as it uses a simpler implementation mainly based on linear decoding operations with much less space and time complexity and only perform MLD with the use of look-up tables when the packet loss increases significantly.

  x i , b i ∈GF(2).

Fig. 1 .

 1 Fig. 1. System model