# TATTOOED: A Robust Deep Neural Network Watermarking Scheme based on Spread-
Spectrum Channel Coding

Giulio Pagnotta, Dorjan Hitaj, Briland Hitaj, Fernando Perez-Cruz, and Luigi
V. Mancini Giulio Pagnotta, Dorjan Hitaj, and Luigi V. Mancini are with the
Department of Computer Science, Sapienza University of Rome, Rome, Italy.
e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Hitaj is with the Computer Science Laboratory
at SRI International, New York, NY 10165, USA. e-mail:
<EMAIL_ADDRESS>Perez-Cruz is with the Swiss Data Science
Center. e-mail<EMAIL_ADDRESS>
###### Abstract

The proliferation of deep learning applications in several areas has led to
the rapid adoption of such solutions from an ever-growing number of
institutions and companies. These entities’ deep neural network (DNN) models
are often trained on proprietary data. They require powerful computational
resources, with the resulting DNN models being incorporated in the company’s
work pipeline or provided as a service. Being trained on proprietary
information, these models provide a competitive edge for the owner company. At
the same time, these models can be attractive to competitors (or malicious
entities), which can employ state-of-the-art security attacks to obtain and
use these models for their benefit. As these attacks are hard to prevent, it
becomes imperative to have mechanisms that enable an affected entity to verify
the ownership of its DNN with high confidence.

This paper presents TATTOOED, a robust and efficient DNN watermarking
technique based on spread-spectrum channel coding. TATTOOED has a negligible
effect on the performance of the DNN model and is robust against several
state-of-the-art mechanisms used to remove watermarks from DNNs. Our results
show that TATTOOED is robust to such removal techniques even in extreme
scenarios. For example, if the removal techniques such as fine-tuning and
parameter pruning change as much as 99% of the model parameters, the TATTOOED
watermark is still present in full in the DNN model and ensures ownership
verification.

###### Index Terms:

watermarking, neural networks, IP protection

##  I Introduction

> Software 2.0 is written in much more abstract, human unfriendly language,
> such as the weights of a neural network.
>
> _Andrej Karpathy
>  Director of AI at Tesla_

The presence of vast quantities of data originating from multitudes of sources
in conjunction with powerful computational resources has fueled the last
decade of machine learning (ML) applications. In particular, deep learning
(DL) has demonstrated exceptional results in a growing number of domains,
constantly pushing the boundaries of previously known state-of-the-art
solutions. The abundance of significant volumes of data enables DNNs, the core
ML technique at the heart of many state-of-the-art DL solutions, to
autonomously determine and learn relevant features directly from the input,
removing the need for handcrafted features. In doing so, DNNs have transformed
themselves as the ML-technique of choice for areas such as image
classification [39, 20], natural language processing [14, 2], speech
recognition [18], data (image, text, audio) generation [25, 3], and cyber-
security [9, 13, 12]. Moreover, a growing body of work has achieved impressive
insights obtained from the use of DNNs to mitigate the impact of the currently
ongoing COVID-19 pandemic [30], further emphasizing the benefits resulting
from the adoption of DL.

(a) TATTOOED watermark embedding procedure.

(b) TATTOOED watermark verification procedure.

Figure 1: High level overview of TATTOOED watermarking scheme. To watermark a
DNN (1(a)), TATTOOED uses a secret key K, out of which two separate keys
(ld[k] and sp[k]) are generated. ld[k] is used in the LDPC encoder (and
decoder on verification procedure) and sp[k] is used to generate the spreading
codes (both in CDMA encoder and decoder). The LDPC encoder takes the watermark
M, encodes it and then passes it to the CDMA encoder which spreads the LDPC-
encoded watermark in a wider bandwidth. Afterwards, the encoded watermark is
passed to the marking module where a DNN (W) is watermarked. To verify the
watermark presence (1(b)), a model watermarked using TATTOOED is given as
input, first to the CDMA decoder, and then to the LDPC decoder to recover the
hidden watermark. Afterwards, the verifying module computes the watermark
accuracy using the extracted watermark M’ and the embedded watermark M, and
returns 1 if the accuracy is equal to or above 90% and 0 otherwise.

However, despite their undeniable advantages, training good DL models comes
with quite some challenges: 1) While frameworks such as TensorFlow or PyTorch
make it easy to construct DL pipelines for a target problem, identifying the
right DNN architecture for the task (i.e., the correct number of layers or
hyper-parameters to use) can be a challenging task even for ML experts. 2) The
absence of required computational resources can make it difficult for an
entity to benefit from DL. 3) Large quantities of training data can
incorporate proprietary characteristics, thus requiring additional layers of
protection when the resulting models are made available to the public,
including machine learning as a service (MLaaS). It is therefore
understandable that companies, institutions, and even individuals devising and
training _proprietary_ DNN models, want to protect this new form of
intellectual property (IP) from the prying eyes of competition and malicious
adversaries.

There has been a growing body of work aiming at devising mechanisms that would
enable an entity to verify, with high assurance, the legitimate ownership of a
suspected DNN model. In particular, DNN watermarking, a concept first
introduced by Uchida et al. [43] has gauged significant interest in the
research community, resulting in a surge of watermarking techniques [45, 40,
11, 6, 1, 7, 24, 32, 50, 34, 41]. However, as it commonly happens in security
and privacy works, this has led to the development of novel methods
demonstrating that it is possible to remove [8, 22, 46, 34, 44], overwrite
[46], and forge [49, 15] the watermarks placed in a DNN. Thus, the development
of a robust DNN watermarking strategy remains an open problem.

In this paper, we push forward the state-of-the-art in DNN watermarking,
introducing TATTOOED, a watermarking framework that makes use of spread-
spectrum channel-coding to provide a novel DNN watermarking strategy that is
robust to the existing state-of-the-art watermark removal techniques [48, 22,
38, 8]. TATTOOED can watermark a DNN model without impacting the models
performance on the intended task while requiring as few as one iteration to
complete the watermarking process. Relying on spread-spectrum channel-coding
techniques to watermark a DNN allows TATTOOED to be DNN architecture- and
task-independent allowing to be seamlessly incorporated to watermark different
DNN models without modification.

There is little amount of work that couples spread-spectrum channel coding
with machine learning, and particularly deep learning applications. Prior work
uses such techniques to build a covert communication channel on top of
federated learning schemes [23], a topic which is different to the one
discussed in this paper. To the best of our knowledge, this is the first work
that makes use of spread-spectrum channel coding for watermarking DNN models.

Our contributions can be summarized as follows:

  * •

We introduce TATTOOED, a novel deep neural network watermarking technique
based on CDMA spread-spectrum channel-coding. Figure 1 provides an overview of
the proposed scheme, details of which are further elaborated on Section IV.

  * •

We demonstrate that TATTOOED is domain-independent and conduct an extensive
empirical evaluation under varying conditions: a) diverse watermark sizes; b)
different DNN architectures; c) several benchmark datasets; d) different
classification tasks; and d) multiple domains, including image, text, and
audio.

  * •

We test TATTOOED against state-of-the-art watermark removal techniques such as
fine-tuning and model pruning and demonstrate that the TATTOOED watermark
cannot be removed.

  * •

We show that TATTOOED is significantly more efficient to mark and verify a DNN
model compared to other state-of-the-art watermarking approaches.

  * •

We provide the source code to reproduce the evaluation of TATTOOED at this
link 111https://anonymous.4open.science/r/tattooed.

This paper is organized as follows: Section II provides the necessary
background information on the topics treated in the subsequent sections.
Section III introduces the threat model. Section IV describes TATTOOED, the
novel deep neural network watermarking technique proposed in this paper.
Section V and Section VI provide details about the experimental set up and
evaluation of TATTOOED. Section VII covers the related work, and Section VIII
concludes the paper.

##  II Background

###  II-A Supervised Machine Learning

Similar to previous work on DNN watermarking, we evaluate TATTOOED on
different classification tasks. Classification is a branch of supervised ML
[17], a learning task where ($x,y$)-tuples of input data are used to train
models that learn a mapping of the input value $x$ to the output value $y$,
commonly referred in the literature as the class or the target label. Once the
training is complete, the model is used to predict the labels of new,
previously unseen instances originating from the same domain. This learning
can be expressed using the following equation:

$\widehat{\theta}=\arg\min_{\theta\in\Theta}\sum_{i}l(f(\mathbf{x}_{i};\theta),y_{i})+\Omega(\theta),$
(1)

where $\hat{y}=f(\mathbf{x};\widehat{\theta})$ represents the learning
machine. The learned function $f$ provides an estimate of the label $y$ for an
input $\mathbf{x}$. The learning is guided by the loss function $l(\hat{y},y)$
that measures the error for misclassifying $y$’s, providing useful information
on how the parameters should be tuned in order for the learned machine to
perform better on the task at hand. $\Omega(\theta)$ is a regularizer [17],
independent of the training data, that prevents the model from overfitting.
Examples of supervised learning algorithms include Support Vector Machines
(SVMs) [37], Random Forests [5], and even Deep Neural Networks (DNNs) [17].

###  II-B Model Watermarking

Digital watermarking was introduced to covertly embed a secret message, the
watermark, inside digital data (e.g., an image) to provide proof of ownership
of the watermarked data. This concept can be directly applied to DNNs. To
prove the ownership of a model $W$, the owner needs a way to securely embed a
secret message inside the model parameters $w\subseteq W$, and a way to
reliably extract the message. A DNN watermarking scheme consists of a message
space $\mathbb{M}$, a key space $\mathbb{K}$, and the following Mark and
Verify algorithms:

Mark is a polynomial and deterministic algorithm that given a secret key
$k\in\mathbb{K}$, a model $W$, and a watermark message $m\in\mathbb{M}$,
outputs a model $W_{wtm}$ that contains the watermark $m$.

Verify is a polynomial and deterministic algorithm that, given a secret key
$k\in\mathbb{K}$ and a model $W$, outputs a bit $b\in[0,1]$, where 1 means
that the model contains the watermark $m$, 0 otherwise.

Watermarking Requirements. Prior work in the domain has outlined several
conditions for a DNN watermarking scheme to succeed [4, 1, 6]. In the coming
paragraphs, we expand on each of these requirements.

####  II-B1 Functionality-Preserving

this requirement guarantees that the Mark algorithm does not impair the
learning task of the model, nor alter its performance in a significant way.
Given model $W$ trained on dataset $D$ and a watermarked model
$W_{wtm}\leftarrow Mark(W,k)$, we define the functionality-preserving
requirement as:

$\Pr_{x\in D}[W_{wtm}(x)=f(x)]\approx\Pr_{x\in D}[W(x)=f(x)]$ (2)

####  II-B2 Robustness

this requirement guarantees that, for any functionality preserving
transformation mapping $W_{wtm}$ to $W^{\prime}_{wtm}$ (e.g., fine-tuning),
the Verify algorithm is still able to correctly detect the presence of the
watermark. We define the robustness requirement as :

$\Pr_{x\in D}[W_{wtm}(x)=f(x)]\approx\Pr_{x\in D}[W^{\prime}_{wtm}(x)=f(x)]$
(3)

$Verify(W_{wtm},k)=Verify(W^{\prime}_{wtm},k)$ (4)

####  II-B3 Reliability

this requirement guarantees that the legitimate ownership of a model can be
verified with high probability, i.e., the Verify algorithm outputs 1 if and
only if the model contains our watermark. Given the key $k$, a model W, and a
watermarked model $W_{wtm}\leftarrow Mark(W,k)$, the probability that the
algorithm Verify outputs 1 is:

$\Pr[Verify(W_{wtm},k)=1]\gg\frac{1}{2}$ (5)

####  II-B4 Integrity

this requirement guarantees that the Verify algorithm outputs 0 for each model
$W^{\prime}$ that does not contain our watermark. Given the key $k$, a model
$W$, a watermarked model $W_{wtm}\leftarrow Mark(W,k)$, and a model
$W^{\prime}$, the probability that the algorithm Verify raises a false
positive error is:

$\Pr[Verify(W_{wtm},k)=Verify(W^{\prime},k)]\ll\frac{1}{2}$ (6)

####  II-B5 Capacity

this requirement guarantees that the Mark algorithm can embed into the model a
potentially large amount of information (e.g., the signature of the legitimate
owner).

####  II-B6 Secrecy

this requirement guarantees that the Mark algorithm can embed the watermark in
a way that is not detectable by any polynomial-time adversary $\mathcal{A}$.

Given two models, $W_{0}$, $W_{1}$, one of them watermarked and the other not,
there is no polynomial-time adversary $\mathcal{A}$ such that:

$\Pr\left[\begin{array}[]{l}W_{0};W_{1}\leftarrow Mark(W,k);\\\
b\stackrel{{\scriptstyle\$}}{{\leftarrow}}[0,1];\mathcal{A}(W_{b})=b\end{array}\right]\gg\frac{1}{2}$
(7)

####  II-B7 Efficiency.

This requirement guarantees that the Mark and Verify algorithms can
efficiently embed the watermark and verify its presence in a model without
incurring a large computational overhead.

####  II-B8 Unforgeability.

The watermark should be unforgeable, such that no malicious entity can
overwrite it and claim ownership of the model.

####  II-B9 Authentication.

This requirement guarantees a strong link between the owner of the model and
the used watermark. This could be achieved cryptographically [1] and is
orthogonal to the Mark and Verify algorithms presented in TATTOOED.

####  II-B10 Generality.

This requirement guarantees that the Mark and Verify algorithms can be used on
every kind of model architecture and any learning task.

Watermark accuracy. To verify the presence of the watermark in a model, the
legitimate owner extracts the watermark content (bits) from the model and
calculates the watermark accuracy by comparing the extracted bits with the
actual bits of the original watermark. The watermark accuracy represents the
ratio between correctly extracted watermark bits and the actual bits of the
original watermark. Given the nature of typical watermarks, (i.e., a sequence
of bits that is clearly related to the legitimate owner) even a lower
watermark accuracy (i.e., above 58% [8]) can be considered as a reasonable
proof.

Nevertheless, to highlight the power and robustness of TATTOOED watermark, in
our evaluation we consider that the watermark is in the model only if the
watermark accuracy is above, or equal to 90% (i.e., Verify algorithm returns 1
if the $WTM_{acc}\geq 0.9$).

###  II-C Spread-Spectrum Channel Coding

In digital communications, spread-spectrum techniques [42] are methods by
which an electrical, electromagnetic, or acoustic signal with a particular
bandwidth is deliberately spread in the frequency domain. These techniques
enable the spreading of a narrowband information signal over a wider
bandwidth. On receiving the signal, the receiver knowing the spreading
mechanism can recover the original bandwidth signal.

Two main techniques are used to spread the bandwidth of a signal: frequency
hopping and direct sequence. In frequency hopping, the narrowband signal is
transmitted for a few seconds in a given band, that is constantly changed
using a pseudo-random frequency band that has been agreed with the receiver.
The receiver, in coordination, tunes its filter to the agreed-on frequency
band to recover the message. Direct Sequence, the spreading technique used in
our neural network watermarking technique, works by directly coding the data
at a higher frequency by using pseudo-random generated codes that the receiver
knows.

In the 1990s, Direct Sequence Spread Spectrum was proposed as a multiple-
access technique (i.e., Code Division Multiple Access or CDMA) in the IS-95
standard for mobile communications in the US, and it was adopted worldwide as
the 3G standard. In CDMA, mobile users transmit to the base station at the
same time using the same frequency but with different spreading codes. The
codes should be quasi-orthogonal. The base station correlates the code of each
user with its spreading code to detect the transmitted bits.

When the transmitters use pseudo-random codes to encode their data, the
spread-spectrum appears random and has noise-like properties. By default, this
introduces some level of privacy because the receiver cannot demodulate the
transmitted signal without the knowledge of the pseudo-random sequence or the
method to generate the sequence that was initially used to encode the data.
Another crucial property of CDMA is its resistance to jamming. Typically, a
jamming signal has a finite amount of power available to jam the signal by
either spreading the energy over the entire bandwidth of the signal or only on
a part of it. The wide bandwidths that can be achieved by CDMA require the
jamming signal to have a large amount of power, which is typically not
feasible in practice.

##  III Threat Model

Adversary’s Capabilities. The adversary corresponds to an entity that has
gained illegitimate access on a proprietary ML model. The adversary is aware
of the possibility of the model being watermarked and employs existing state-
of-the-art watermark-removal techniques such as fine tuning and parameter
pruning in an attempt to remove the watermark from the model. The adversary
wins if they can remove the watermark without incurring costs similar to what
the legitimate owner spent to construct the model (e.g., the adversary could
train a comparable model if he had to spend the same resources to remove the
watermark).
Watermark verification. There exist two ways to verify the presence of a
watermark in a deep neural network. Those are white-box and black-box
verification. In white-box watermark verification the verifier (i.e., the
legitimate owner) needs physical access to the model, while in the black-box
watermark verification the verifier does not need such access. In black-box
scenario the watermark verification is performed remotely by querying the
model and observing the outputs returned by it.

We position ourselves in a white-box watermark verification scenario similar
to prior works [33, 43, 40, 11, 6, 47] in the field, where the verifier has
white-box access to the DNN model to be verified.

##  IV Tattooed

This section introduces TATTOOED, our neural network watermarking technique
based on a direct application of CDMA to watermark the model.

In this scenario, a legitimate owner wants to insert a $P$-bits watermark
$\mathbf{b}=[b_{0},\ldots,b_{P-1}]$ into the model parameters. The bits are
encoded as $\pm 1$, and the code for each bit is represented by
$\mathbf{c}_{i}$, which is a vector of $+1$ and $-1$ of length $R$, where $R$
is the number of parameters selected to embed the watermark in model
$\mathbf{W}$. $\mathbf{C}$ is an $R$ by $P$ matrix that collects all the
codes. We assume that the codes have been randomly generated with equal
probabilities for $\pm 1$. The legitimate owner stores a set of weights
$\mathbf{W}_{T}$ prior to watermarking the model being trained and then
watermarks the model as follows:

$\mathbf{W}_{wtm}=\mathbf{W}_{T}+\gamma\mathbf{C}\mathbf{b}$ (8)

where $\gamma$ is a parameter that affects the strength of the watermark
signal. The $\gamma$ parameter has to be selected in an optimal way such that
it does not impact the performance of the trained ML model on the legitimate
task. To select $\gamma$ we performed a grid search among $\gamma$ values in
the range $[1\times 10^{-4},2\times 10^{-4},\dots,9\times 10^{-4},1\times
10^{-3},2\times 10^{-3},\dots,9\times 10^{-3},1\times 10^{-2},2\times
10^{-2},\dots,9\times 10^{-2}]$.

Now, the legitimate owner can recover the watermark that was hidden in
parameters of the model using the spreading code. For example, for bit $i$ of
the watermark, the legitimate owner can recover it as follows:

$y_{i}=\mathbf{c}_{i}^{\top}\left(\mathbf{W}_{wtm}-\mathbf{W}_{T}\right)$ (9)

After obtaining $y_{i}$ from Equation 9 the legitimate owner can recover the
i-th bit as $\widehat{b}_{i}=\text{sign}(y_{i})$.

For moderate size payloads, the spreading codes of the other bits and the
values of $W_{T}$ can result in some bits being decoded erroneously for
moderate values of $\gamma$. For large values of $\gamma$ the watermark might
be easily extracted, but the performance of the network can be affected. To be
able to extract the watermark and keep the value of $\gamma$ in an appropriate
range, in addition to CDMA, we employ the Low-Density Parity-Check (LDPC) [16]
error correction technique. We choose LDPC due to their good properties in
error correction and the ability to perform the error correction in linear
time [36]. In TATTOOED, we use a standard rate, $1/2$ code for all the
available $P$ bits with three ones per column. For LDPC codes to work, they
need an estimate of the noise level. To obtain this value, alongside the
actual watermark, we embed in the model a preamble of 200 random bits in the
first 200 bits of $P$ so that we can use these values to estimate the noise
variance.

The process of watermarking and verifying the presence of the watermark in a
ML model is displayed by the pseudocodes of Mark, Algorithm 1 and Verify,
Algorithm 2.

Input: Model: $W_{T}$, Int: $\gamma$, Str: $message$, Str: $key$

Output: Model: $W_{wtm}$

1 $seed,ldpc\\_seed\leftarrow seed\\_gen(key)$

2 $ldpc\leftarrow init\\_ldpc(ldpc\\_seed)$

3 $c\leftarrow ldpc.encode(message)$

4 $PRNG(seed)$

5 $preamble\leftarrow random([-1,1],size=200)$

6 $b\leftarrow concatenate(preamble,c)$

7 $i\leftarrow 0$

8 while  _$i <len(b)$_ do

9 $code\leftarrow random([-1,1],size=len(W))$

10 $signal\leftarrow gamma*code*b[i]$

11 $W_{wtm}\leftarrow W_{T}+signal$

12 $i\leftarrow i+1$

13

Algorithm 1 Mark

Mark (Algorithm 1) takes as input an ML model to be watermarked, the $\gamma$
value that will affect the power of the watermark signal, the actual watermark
content (message), and a secret key used to ensure the security properties of
the embedded watermark. The secret key consists of 512 bits and is used to
generate two separate secret seeds, one seed is used to generate the spreading
codes, and the other seed for creating the LDPC matrices. Once that is done,
the watermark content (information that clearly correlates the model with the
legitimate owner) is encoded, and the preamble that we will use to estimate
the noise is concatenated to that bit sequence. Then for each bit of this
composite sequence (preamble + LDPC encoded watermark), a spreading code of
the length of the number of the ML model parameters weights considered is
generated. The spreading code is multiplied by the bit value (translated to
$\pm 1$), and the $\gamma$. The resulting vectors are added to the vector of
the selected parameters of $W$.

Input: Model: $W$, Str: $key$

Output: bool: $b$

Data: Int: $wtm\\_length$, Str: $message$, Model: $W_{T}$

1 $seed,ldpc\\_seed\leftarrow seed\\_gen(key)$

2 $ldpc\leftarrow init\\_ldpc(ldpc\\_seed)$

3 $y\leftarrow[]$

4 $PRNG(seed)$

5 $preamble\leftarrow random([-1,1],size=200)$

6 $i\leftarrow 0$

7 while  _$i <wtm\\_length$_ do

8 $code\leftarrow random([-1,1],size=len(W))$

9 $y_{i}\leftarrow transpose(code)*(W-W_{T})$

10 $y.append(y_{i})$

11 $i\leftarrow i+1$

12

13$gain\leftarrow mean(multiply(y[\mathrel{\mathop{\mathchar
58\relax}}200],preamble))$

14 $sigma\leftarrow std(multiply(y[\mathrel{\mathop{\mathchar
58\relax}}200],preamble)/gain)$

15 $snr\leftarrow-20*log_{10}(sigma)$

16

17$m\leftarrow ldpc.decode(y[200\mathrel{\mathop{\mathchar
58\relax}}]/gain,snr)$

18 $err\leftarrow difference(m,message)$

19 $WTM_{acc}\leftarrow 1-err$

20 if  _$WTM_{acc}\geq 0.9$_ then

21 $b\leftarrow 1$

22

23else

24 $b\leftarrow 0$

25

Algorithm 2 Verify

Verify (Algorithm 2) takes as input the model and the secret key and returns
$1$ if the watermark is present and $0$ otherwise. As in the Mark algorithm,
the two seeds are obtained from the secret key, and with them the spreading
codes and the LDPC matrices are generated. Each bit of the composite sequence
(preamble + watermark) is retrieved by multiplying the transpose of the
respective spreading code with the subset of the model parameters $W$. The
first 200 bits of $y$, which correspond to the preamble are correlated with
the actual preamble that was used in Mark. From them, the CDMA gain and
signal-to-noise ratio (SNR) are calculated. The gain and SNR are used by the
LDPC decoder to retrieve the watermark content. Afterwards, using the
retrieved watermark, we compute the watermark accuracy and, if it is above or
equal of 90%, a positive response is returned, see Section II-B.

##  V Experimental Setup

###  V-A Datasets

To conduct our evaluation we chose the following benchmark datasets:

  * •

For the image classification domain we used the MNIST [28] and CIFAR-10 [27]
datasets. The MNIST handwritten digits dataset consists of 60,000 training and
10,000 testing grayscale images of dimensions 28$\times$28-pixels, equally
divided in 10 classes. The CIFAR-10 [27] dataset consists of 50,000 training
and 10,000 testing 32$\times$32 color images equally divided in 10 classes.

  * •

For the language modeling domain, we used a subset of the WikiText [31]
dataset. WikiText [31] subset consists of approximately 2.5 million tokens
representing 720 Wikipedia articles and is divided into 2,088,628 train
tokens, 217,646 validation tokens, and 245,569 testing tokes.

  * •

For the audio recognition domain, we used the ESC-50 [35] dataset. The ESC-50
[35] dataset consists of 2,000 labeled recordings equally divided between 50
classes of 40 clips per class.

###  V-B DNN Architectures

We evaluate TATTOOED watermark performance on different DNN architectures.

  * •

For the image classification tasks on MNIST and CIFAR-10 we employed two model
architectures: The first architecture used consists of a multilayer perceptron
model composed of four fully-connected layers. The other architecture is the
VGG-16 model [39].

  * •

For the text classification task on WikiText-2 dataset we employed an RNN
model composed of 2 LSTM layers.

  * •

For the ESC-50 audio classification task we employed a CNN-block-based model
composed of 4 CNN layers.

###  V-C Watermarks

We used two different watermarks of different sizes for watermarking a model
using TATTOOED, namely a short text watermark and a large image watermark.

  * •

text-watermark corresponds to the _”TATTOOED watermark!”_ text sequence
corresponding to 152 bits.

  * •

image-watermark corresponds to an image of 1KB.

For simplicity, we refer to them as the text and the image watermark,
respectively.

##  VI Evaluation

In this section, we provide a step-by-step, thorough evaluation of TATTOOED
and show that it satisfies all the requirements described earlier in Section
II-B.

###  VI-A Functionality-Preserving

A good watermark should not deteriorate the model’s performance on its
original task. To this end, we compare baseline performance to the TATTOOED
model’s performance on different model architectures and datasets (Section V).

TABLE I: Baseline versus TATTOOED model performance comparison.  Model | Dataset | Baseline | TATTOOED
---|---|---|---
Architecture |  | Performance | Performance
VGG | CIFAR10 | 84.35 | 84.30
MLP | MNIST | 97.57 | 97.45
RNN | WikiText-2 | 155.59 | 154.63
CNN | ESC-50 | 57.77 | 57.32

Table I displays the comparison between the performance of the baseline and
TATTOOED watermarked models on the respective test sets. For CIFAR10, MNIST,
and ESC-50, the performance corresponds to the classification accuracy (in %),
while for Wikitext-2, the performance corresponds to the perplexity. All
models were trained for 60 epochs. The watermark used is the text-watermark
corresponding to 152 bits. We used the $\gamma$-value equal to $9\times
10^{-2}$ to embed the watermark as it allows the watermark accuracy to be 100%
while also allowing the TATTOOED model to have comparable performance with the
baseline in all the considered tasks and models architectures. The TATTOOED
model’s performances shown in Table I demonstrate that the use of CDMA spread-
spectrum technique to perform watermarking does not impact the performance of
the trained ML model on the intended task. This is due to the way CDMA works.
The added signal for each bit of the watermark is spread over the model
parameters using a low $\gamma$ value and the strength of a CDMA-based signal
(like TATTOOED watermark) increases in proportion to the length of the
spreading code. In this way, using a longer code, combined with a small
$\gamma$-value, does not incur significant changes to the model’s weight
parameters or impact the model’s performance on the intended task.

From this evaluation, we can see that the TATTOOED watermark does not
significantly affect model performance, thus it satisfies the Functionality-
Preserving requirement.

###  VI-B Robustness

(a) Multilayer perceptron model trained for 100 epochs on 30,000 MNIST
instances, TATTOOED text-watermark embedded at epoch 100 using $\gamma=9\times
10^{-2}$, retrained (RTAL) on a different set of 30,000 MNIST instances for
1000 epochs.

(b) VGG-16 model trained for 100 epochs on 30,000 CIFAR10 instances, TATTOOED
image-watermark embedded at epoch 100 using $\gamma=9\times 10^{-2}$,
retrained (RTAL) on a different set of 30,000 CIFAR10 instances for 1000
epochs.

Figure 2: The effect of model retraining on TATTOOED watermark using the same
amount of additional data to retrain the model as that used for initial
training.

Robustness is the ability of the watermark to survive removal attacks so that
legitimate owners can still perform a reliable copyright claim on their
models.

The state-of-the-art watermark removal techniques in ML models are based on
two main techniques, fine-tuning and model parameter pruning [8, 44, 29].
_Fine-tuning_ is a way of applying or using transfer learning. Specifically,
fine-tuning is a process that takes a model that has already been trained for
one given task and then tunes or tweaks the model to make it perform a second
similar task. This approach can be used on the same task using other unseen
data to improve the performance of the model. _Parameter pruning_ is a
technique that removes neurons from an already trained neural network while
preserving the performance of the model on the intended task. For
completeness, in this work, we consider also _Parameter Shuffling_ as a method
to disrupt the watermark. _Parameter Shuffling_ consists of reordering the DNN
weight parameters while also maintaining adequate performance on the intended
task.

Fine-tune all layers (FTAL) Fine-tune all layer is a common fine tuning
technique to either boost the performance of a pre-trained model on the task
using new data. To evaluate the robustness of TATTOOED versus a FTAL removal
technique, we performed two experiments: with MNIST and with CIFAR10. First,
we trained the multi-layer perceptron model on 40,000 MNIST instances for 100
epochs, watermarked it using the text-watermark with $\gamma=9\times 10^{-2}$
and then performed FTAL using the remaining 10,000 MNIST instances for another
100 epochs. Then, we trained the VGG-16 model on 40,000 CIFAR10 instances for
100 epochs, watermarked it using the image-watermark with $\gamma=9\times
10^{-2}$ and then performed FTAL using the remaining 10,000 CIFAR10 instances
for another 100 epochs.

Results. After each of the fine-tuning epochs, we used the Verify algorithm to
check the presence of the watermark in the model. In every epoch, the
watermark presence was successfully verified with a watermark accuracy of
100%, showing that the FTAL technique is ineffective in removing the TATTOOED
watermark from the models.

Re-train all layers (RTAL). To evaluate the robustness of TATTOOED watermarks
against RTAL (i.e., fine tuning the model on a dataset that is the same size
as the one used in training), we split MNIST and CIFAR10 into two parts, one
for the initial training and one for retraining. Each of these splits
contained 30,000 images. We trained the multilayer perceptron model on the
first half of the MNIST and CIFAR10 dataset and used TATTOOED to watermark it.
After that, we used the second half of the dataset to train the model for over
1,000 epochs.

Results. Figure 2(a), shows the validation accuracy of the model trained on
the MNIST task. We watermarked the model at epoch 100 (yellow vertical line)
with the text watermark using $\gamma=9\times 10^{-2}$. During the retraining
phase, the validation accuracy of the model increases because it is being
trained on new data. After every epoch, we checked if the watermark was
present in the model, and confirmed that the watermark was unaffected even
after 1,000 epochs. The changes that occurred to the model’s weight parameters
during retraining (RTAL) were not sufficient to eliminate the TATTOOED
watermark.

Figure 2(b) displays the validation accuracy on the CIFAR10 task. Similar to
MINST, we trained the model on the first half of the CIFAR10 dataset for 100
epochs and then watermarked it with the image watermark using $\gamma=9\times
10^{-2}$. Afterwards, we retrained the model using the second half of the
dataset for 1,000 epochs. The retraining (RTAL) phase caused a significant
change on the model parameters (indicated by the large increase in validation
accuracy); however, this change was not sufficient to remove the image-
watermark embedded with TATTOOED. These experiments highlight the ability of
TATTOOED watermark to resist significant changes caused by retraining the
model using a dataset of the same size as the one used in the initial
training. Although these changes can be quite drastic the watermark is
unaffected.

In each of the fine-tuning epochs, we used the Verify algorithm to check the
presence of the watermark in the model. In every epoch, the watermark presence
was successfully verified with a watermark accuracy of 100%, showing that the
RTAL technique is ineffective in removing the TATTOOED watermark from the
models.

TABLE II: REFIT [8] watermark-removal technique impact on prior works and TATTOOED.  | REFIT [8]
---|---
Method | Basic | AU | EWC | EWC+AU
Zhang et al. [51] | ✗ | ✗ | ✗ | ✗
Adi et al. [1] | ✗ | ✗ | ✗ | ✗
Namba et al. [34] | ✗ | ✗ | ✗ | ✗
Wang et al. [47] | ✗ | ✗ | ✗ | ✗
TATTOOED (Ours) | ✓ | ✓ | ✓ | ✓

(a) REFIT basic fine-tuning.
$lr=0.05,lradj=1$,
$extra\\_data=0.2cifar10$.

(b) REFIT AU. $lr=0.1\\\ lradj=15$
$extra\\_data=imagenet32.$

(c) REFIT EWC. $lr=0.15\\\ lradj=1$, $EWC\\_coef=10\\\ EWC\\_samples=10,000.$

(d) REFIT AU+EWC. $lr=0.1\\\ lradj=15,EWC\\_coef=10\\\ EWC\\_samples=10,000$.

Figure 3: The TATTOOED watermark resilience under different REFIT fine-tuning
watermark removal techniques. Each model was watermarked with TATTOOED using
the text-watermark.

Fine Tuning using REFIT [8] To evaluate the robustness of the TATTOOED
watermark, we tested it against REFIT [8], a state-of-the-art watermark
removal technique. REFIT is agnostic to the technique used to watermark a DNN
model, and is able to remove a portion of watermark sufficient to make a wide
range of prior neural network watermarking schemes unreliable, such as [45,
40, 11, 6, 1, 7, 24, 32]. REFIT proposes four separate FTAL-based watermark
removal techniques. The first is based on traditional fine-tuning, the second
relies on unlabeled data augmentation (AU), the third relies on elastic weight
consolidation (EWC), and the fourth simultaneously employs AU and EWC to
remove the watermark. After we trained our model and watermarked it using
TATTOOED, we employed REFIT fine tuning techniques for the same number of
epochs that we used in training to test the robustness of TATTOOED watermark
towards this attack. Typically, fewer fine tuning steps are used; otherwise,
the adversary attempting to remove the watermark would have to spend the same
amount of computation power as that needed to train the network from scratch.
We used the original REFIT implementation in our
experiments.222https://github.com/sunblaze-ucb/REFIT

Results. Figure 3 displays the performance for each of the REFIT watermark
removal techniques against TATTOOED. We trained the VGG-16 on the CIFAR10
dataset for 100 epochs and used TATTOOED to watermark the model with the text-
watermark with a $\gamma=9\times 10^{-2}$. The parameters used to configure
REFIT are the ones suggested in their official repository [8] and are
displayed in the captions of the figure 3.

Beside using Verify 2 algorithm to check the presence of the watermark in each
epoch, we also used the signal-to-noise ratio (SNR) to measure the amount of
disruption that REFIT removal techniques caused to the TATTOOED watermark
signal epoch by epoch. SNR is the ratio of signal power to the noise power,
expressed in decibels. the SNR calculation is displayed in Algorithm 2.

Figure 3(a) shows the impact on the TATTOOED watermark signal from REFIT’s
base fine-tuning techniques. The base fine-tuning slightly decreased the
strength of the watermark signal, but it did not impact the watermark
verification procedure.

Figure 3(b) shows the impact of the REFIT with AU removal technique. In this
case the AU-based fine tuning is able to decrease the strength of TATTOOED
watermark signal more than plain vanilla fine-tuning but not enough such as to
completely destroy the TATTOOED watermark.

Figure 3(c) shows the impact of the EWC-based fine tuning watermark removal
technique. The third approach to slightly decreased the strength of the
signal, but not sufficient enough to prevent watermark verification.

The fourth technique to remove the watermark is the combination of AU and EWC
fine-tuning. Figure 3(d) demonstrates that AU+EWC can not disrupt the signal
of the TATTOOED watermark, even if it spends the same number of epochs as the
training required.

In each of the above-mentioned experiments, in every epoch, the watermark
presence was successfully verified with a watermark accuracy of 100%, showing
that all four of the REFIT [8] watermark removal techniques are ineffective in
removing the TATTOOED watermark from the model.

To highlight that TATTOOED is pushing forward the state-of-the-art in DNN
watermarking, in Table II we compare the impact that REFIT has on prior art
and on TATTOOED. Following REFIT [8], in Table II, we display the performance
of REFIT on the representative works [51, 1, 34, 47] in the different
watermarking embedding schemes. For [51, 1, 34] we report the robustness
results from REFIT [8]. As we can see, REFIT is able to disrupt the watermark
verification of those techniques. Wang et al. [47] report that REFIT is able
to disrupt the watermark accuracy thus hindering the verification process, but
the REFIT parameters to fully remove the watermark from the model are
difficult to find. On the other side, TATTOOED watermark is completely
unaffected by REFIT and the watermark accuracy is always 100%, leading to an
improvement over prior art in terms of robustness.

Parameter Pruning Typically, parameter pruning is performed by zeroing the
weight parameters of the model. To evaluate the robustness of the TATTOOED
watermark against parameter pruning technique, we prune the parameters of the
watermarked model by varying the amount of pruning from 25% to 99.99%.

TABLE III: Parameter Pruning watermark removal technique on VGG16 model and CIFAR10 task trained for 100 epochs and watermarked with TATTOOED using the text-watermark. Pruning | Model Acc. | Watermarking Acc. | SNR
---|---|---|---
$25.00\%$ | $84.32\%$ | $100.00\%$ | 34.61
$50.00\%$ | $80.66\%$ | $100.00\%$ | 34.30
$75.00\%$ | $10.02\%$ | $100.00\%$ | 29.86
$90.00\%$ | $10.00\%$ | $100.00\%$ | 26.17
$95.00\%$ | $10.00\%$ | $100.00\%$ | 22.06
$99.00\%$ | $10.00\%$ | $100.00\%$ | 12.47
$99.75\%$ | $10.00\%$ | $90.32\%$ | 2.07
$99.99\%$ | $10.00\%$ | $0.00\%$ | -6.27

Table III displays the effects that different amounts of pruning have on the
TATTOOED watermark accuracy and on the test accuracy of the VGG16 model
trained on CIFAR10 dataset. Table III shows that after pruning up to 99% of
the model parameters, the TATTOOED watermark accuracy is still 100%. However,
the model performance on the test set deteriorates to 10%, which is no better
than guessing among the 10 classes of CIFAR10, thus the model is unable to
perform its intended task. The inability of parameter pruning to remove the
TATTOOED watermark, even when 99% of the parameters are pruned, is due to the
foundations of the TATTOOED watermarking technique. TATTOOED employs CDMA
spread-spectrum channel coding to embed the watermark in a randomly selected
portion of the models parameters. As mentioned in Section IV, to extract a bit
of the watermark $b_{i}$, the spreading code is multiplied by the vector of
the parameters that were selected for watermarking. Even if 99% of them can be
zeroed by the random pruning, the remaining non-zero weights contribute enough
into correctly decoding $b_{i}$ to allow the detection of the watermark in the
model. This ability derives from the inherent capabilities of the CDMA, where
the adversary cannot prevent the communication without completely destroying
the channel (thus zeroing all the parameters of the model in our case).
Another way to perform parameter pruning is to physically remove the pruned
neurons from the model, resulting in a new model architecture. This technique
is known as model compression [48]. To thwart a removal attack based on model
compression, the legitimate owner can compress the model before using TATTOOED
for watermarking to provide another level of robustness to the watermark,
since once compressed, an ML model size (in terms of parameters) can not be
reduced by a large amount without impairing performance.

Parameter Shuffling An adversary might attempt to reorder the parameters in
each network layer to prevent the watermark verification. Firstly, the
reordering of the parameters should be carefully done to not impact the model
performance. Secondly we can find and reverse back to the original order the
parameters of the networks as follows.

Let $W=\\{W_{1},W_{2},\ldots,W_{k}\\}$ be our original watermarked neural
network. $W’=\\{W’_{1},W’_{2},\ldots,W’_{k}\\}$ represents the resulting
network after the adversary shuffles the parameters. To undo the shuffling we
need to compute the cosine distance between each layer of the network (i.e.,
submatrix).

For simplicity, lets consider the recovery process of $W_{1}$, from the
shuffled version $W_{1}^{{}^{\prime}}$. To compute the cosine distance we
first need to compute the vector norm for $W_{1}$ and $W_{1}^{{}^{\prime}}$:

$Norm_{W_{1}}=\sqrt{Diag(W_{1}^{\top}W_{1})}$ (10)

$Norm_{W_{1}^{{}^{\prime}}}=\sqrt{Diag(W_{1}^{{}^{\prime}\top}W_{1}^{{}^{\prime}})}$
(11)

Where $T$ represents the transpose of the matrices and $Diag$ means that we
keep the diagonal values of the resulting matrix after the matrix
multiplication. Assuming that $Norm_{W_{1}}$ and $Norm_{W_{1}^{{}^{\prime}}}$
are column matrices, then we can compute the cosine distance like this:

$CosDist(W_{1},W_{1}^{{}^{\prime}})=W_{1}^{\top}W_{1}^{{}^{\prime}}\oslash
Norm_{W_{1}}Norm_{W_{1}^{{}^{\prime}}}^{\top}$ (12)

where $\oslash$ represents the element wise division.

The cosine matrix 12 is a squared matrix, in which the rows indicate the
original network order for the neurons in the first hidden layer, and the
columns indicate the order of the neurons in the new network. If the network
has not been shuffled, the diagonal elements of this matrix will be one.
Otherwise, the ones in each row indicate the performed shuffling for that
neuron. For example, if the entry $(1,3)$ in the cosine matrix 12 would be
one, it means that the first neuron in the original network has been moved to
the third position in the shuffled network. There is only one one per column
and row in that matrix. Knowing the shuffled elements, we can undo the
shuffling in this layer and perform the same process for every other layer in
the network, recursively. After unshuffling every layer, we can recover the
watermark using the Verify algorithm 2.

In all the above-mentioned experiments, the watermark accuracy is 100%. From
this evaluation, we can see that FTAL, RTAL, REFIT [8], Parameter Pruning and
Parameter Shuffling are unable to remove the TATTOOED watermark, thus
satisfying the Robustness requirement.

###  VI-C Reliability

A reliable watermarking technique should exhibit a minimal false negative rate
that will allow legitimate owners to identify their intellectual property with
high probability. TATTOOED employs CDMA to watermark the model. CDMA directly
codes the data by using pseudo-random generated codes known only by the
legitimate owner. Typically, the spreading codes are in tens to hundreds of
bits, so the signal is only visible when the spreading code is known and the
gain of using CDMA is proportional to the length of the code. Due to the large
size of DNNs, whose parameters are in the thousands and millions, the gain of
using CDMA is higher when we employ it for watermarking a DNN since we can use
spreading codes that are in the order of hundreds of thousands, allowing the
legitimate owner to reliably identify the presence of the watermark in the
model with no false negatives. Moreover, to empirically support this claim we
trained 100 different VGG-16 models on the CIFAR10 dataset. Afterward, we
randomly choose 50 models and we watermark them using TATTOOED with
$\gamma=9\times 10^{-2}$, the image-watermark and same key to generate the
CDMA spreading codes. The remaining 50 models are left untouched. We run the
Verify algorithm on each of these 100 models and report the results in Figure
4.

From our evaluation, we see that the false negative rate is 0 (as predicted by
CDMA theory). Hereby, based on the theoretical foundations on CDMA and the
empirical evaluation, TATTOOED is able to satisfy the Reliability requirement.

Figure 4: Confusion matrix reporting the Reliability and Integrity of the
TATTOOED Verify algorithm. The evaluation is performed over 100 models (out of
which 50 watermarked using TATTOOED).

###  VI-D Integrity

The integrity of a watermark means that the watermarking technique should
exhibit minimal false alarm rates, to avoid erroneously accusing an honest
party that has a similar model to the one watermarked. TATTOOED, due to its
foundations on CDMA, satisfies this condition. The legitimate owner can
extract the watermark only from its own model. The correlation between the
model weight parameters where the watermark is embedded and the spreading
codes for the extraction of individual bits of the watermark can be performed
only on the watermarked model (see Equation 9). Moreover, to empirically
support this claim we trained 100 different VGG-16 models on the CIFAR10
dataset. Afterward, we randomly choose 50 models and we watermark them using
TATTOOED with $\gamma=9\times 10^{-2}$, the image-watermark and same key to
generate the CDMA spreading codes. The remaining 50 models are left untouched.
We run the Verify algorithm on each of these 100 models and report the results
in Figure 4.

From our evaluation, we see that the false positive rate is 0 (as predicted
also by the CDMA theory). Hereby, based on the theoretical foundations on CDMA
and the empirical evaluation, TATTOOED is able to satisfy the Integrity
requirement.

###  VI-E Capacity

A watermark must be able to undeniably reveal the identity of the legitimate
owner. TATTOOED, by employing CDMA, allows for the inclusion of large amounts
of information in the network without impacting the models performance on the
legitimate task (see section VI-A). We empirically showed that TATTOOED allows
embedding watermarks in orders of thousands of bits for networks with tens of
thousands of parameters. A typical Advanced Encryption Standard (AES) secret
key consists of 256 bits and that alone is sufficient to guarantee that the
model belongs to the user who owns the secret key. For another entity to be
able to claim that they are the legitimate owner of that model, they would
need to provide the 256-bit key and to guess a bit sequence of that size has a
probability of $1/2^{256}$.

In our experiments we employed two different sized watermarks. One of them
consists of 152 bits and the other is 1 kilobyte. Being able to watermark the
models with bit sequences ranging from hundreds to thousands of bits is more
than enough to undeniably reveal the identity of the legitimate owner and thus
satisfy the Capacity requirement.

###  VI-F Secrecy

Figure 5: Comparison between the distribution of the weight parameters the
same model architecture watermarked using TATTOOED and untouched.

Secrecy means the watermark should be undetectable by unauthorized parties.
CDMA, the building block of TATTOOED watermark, ensures secrecy. Only the
legitimate owner has the spreading codes, (s)he is the only one who can detect
the presence of the watermark in the model. The spreading codes for each bit
of the watermark are a random sequence of $\pm 1$ with length $W$ that the
legitimate owner has generated, and any entity without the spreading codes can
see the model parameters, but get no information from them.

Figure 5 shows the distribution of the weight parameters of the same model
with and without the watermark. The model architecture is the multi layer
perceptron trained on the MNIST dataset. The TATTOOED model is watermarked
using the text-watermark using $\gamma=9\times 10^{-2}$. The distribution of
the weight parameters is nearly identical between the watermarked and non-
watermarked model providing no information revealing the presence of the
watermark in the model.

Based on the theoretical foundations of TATTOOED on CDMA and our empirical
evaluation, TATTOOED satisfies the Secrecy requirement.

###  VI-G Efficiency

TATTOOED watermarking consists of two individual computations to embed the
watermark: 1) multiplying the spreading code with the watermark content to
create the watermark signal and 2) adding this signal to the model parameters
selected to carry the watermark (Eq. 8). In today’s computers, matrix
multiplication and addition is extremely fast, especially when exploiting the
parallelism advantages offered by general processing units (GPUs). This allows
TATTOOED watermarking to be embedded and verified in a short amount of time,
typically in few seconds even for watermarks and spreading codes length in the
order of thousands.

TABLE IV: Mark and Verify algorithms performance on the multi-layer perceptron architecture with 198,656 weight parameters and watermarked via TATTOOED using the text-watermark with a $\gamma=9\times 10^{-2}$. Ratio | Time to Mark | Time to Verify
---|---|---
$12.50\%$ | 1.36sec | 0.42sec
$25.00\%$ | 2.73sec | 0.67sec
$50.00\%$ | 5.35sec | 0.94sec
$100.00\%$ | 11.14sec | 1.90sec

Prior watermarking techniques require modifications to the training regime
[43, 1] and multiple epochs for embedding.

To evaluate TATTOOED performance in Mark and Verify procedures, we measured
the time (in seconds) that TATTOOED requires to embed and verify the watermark
from a neural network containing about 200K parameters, while embedding the
watermark using different portions of the network starting from $12.5\%$. The
results in Table IV show that TATTOOED needs less than 12 seconds to watermark
a model with about 200K parameters and less than 2 seconds to verify whether
the watermark is present in the model. In contrast, watermarking methods such
as [43, 1], due to the model modifications they incur to watermark a model,
require multiple training epochs (e.g., an epoch on MNIST requires around 10
seconds on a high end desktop GPU).

Based on our empirical evaluation and the comparison with prior neural network
watermarking techniques, TATTOOED satisfies the Efficiency property.

###  VI-H Unforgeability

Unforgeability means that another entity cannot claim ownership of a
legitimate owner’s model. As previously explained (Section IV), TATTOOED
employs randomly-generated spreading codes in the orders of thousands. Relying
on CDMA theory, the only way to detect (and thus overwrite) the watermark is
to know the original spreading codes. For each watermark bit, another entity
has to guess the correct spreading code used which is impossible due to the
gargantuan dimension of the search space. Another entity can embed another
watermark in the model using TATTOOED or other techniques; however, the CDMA
properties prevent the removal of the original watermark, protecting the
legitimate owner’s copyright claim to the model.

Under copyright law, an author of an original work automatically owns the
copyright to that work, preventing anyone else from using or replicating it.
To circumvent any dispute to ownership created by an adversary inserting a
fraudulent watermark into a model, the legitimate owner can register the
copyright when the watermark is inserted using TATTOOED, providing an upper
hand in the legal system in the event that the need arises.

To this end, the reliance of TATTOOED on CDMA to watermark a DNN model allows
it to satisfy the Unforgeability requirement for digital watermarking.

###  VI-I Authentication

The watermark should provide a strong, easily verifiable link, such as
information directly related to the legitimate owner of the model. TATTOOED
allows arbitrary watermark content to be embedded in the network. Content from
text messages (such as company name, fiscal code, etc.) to images (such as the
legitimate owner’s signature, etc.) can be included in the TATTOOED watermark.
Due to TATTOOED reliance on CDMA to embed the watermark, this content can be
extracted from the ML model only by the legitimate owner who possesses the
spreading code (Section II-C).

The ability of TATTOOED to allow arbitrary watermarks that strongly link the
legitimate owner’s identity with the ML model satisfies the Authentication
requirement for digital watermarking.

###  VI-J Generality

The _generality_ property ensures that the application of a watermarked model
is not restricted to a particular neural network architecture or dataset. We
verified the _generality_ property of the TATTOOED watermark by employing it
on two image classification tasks (MNIST and CIFAR10), one audio
classification task (ESC-50), and one language modelling task (Wikitext-2),
and various model architectures (multi layer perceptron, CNN and RNN).

On our empirical evaluation in multiple datasets and DNN architectures,
TATTOOED was successfully applied without any model- or dataset-specific
requirements, satisfying the watermark generality property.

##  VII Related Work

###  VII-A White-Box Watermarking Techniques

In the early 2000s, spread spectrum techniques were applied to watermark
digital images [21, 10]. Hernández et al. [21], present a spread-spectrum-like
discrete cosine transform domain watermarking technique for copyright
protection of digital images. Cox et al. [10] propose to insert a watermark
into the spectral components of the data using techniques analogous to spread
spectrum communications, hiding a narrow band signal in a wideband channel
(i.e., multimedia data). The work by Uchida et al. [43, 33] is the first
attempt to watermark a DNN. The embedding is made possible by using an extra
regularization term in the cost function that introduces a statistical bias on
the weight parameters of the learned ML model. This statistical bias is then
used to infer information about the ownership of the ML model. Wang et al.
[45] insert an independent neural network that allows the use of selective
weights to watermark another ML model. This independent model is kept secret
and serves as the watermark verification tool. The watermark is embedded by
training the two neural networks simultaneously. In this procedure, the
independent neural network uses selected target parameter weights of the model
to be watermarked to embed the watermark information. To extract the
watermark, the input layer of the independent neural network is connected to
the selective weights of the marked neural network, and the watermark
verification is done by observing the outputs of the independent neural
network. Song et al. [40] present both a white- and black-box watermarking
technique with the goal of embedding information related to the private
training dataset into the trained model’s weight parameters. In the white-box
case, they do this by either encoding sensitive information about the private
training dataset in the least significant bits and the signs of the model’s
weight parameters, or, similarly to Uchida et al. [43, 33], by including an
extra regularization term to the loss function. DeepSigns [11] works by
embedding the watermark in the probability density function of the data
abstraction obtained by a DNN layer. The watermark verification is done by
using a subset of training data, querying the model with them, and computing
the statistical mean value of the activation features obtained by passing
these input data in the model. The acquired mean values are used to extract
the watermark content. DeepMarks [6] improves upon DeepSigns [11] by
constructing the watermarks using anti-collusion codebooks. The watermark,
similar to [6], is embedded in the probability density function of the weights
by incorporating a watermark-specific regularization loss. Along the same line
of thought as Uchida et al. [43, 33], Wang et al. [47], propose a GAN-based
adversarial training technique that encourages the weights distribution of a
watermarked model to be similar to the weights distribution of a non-watermark
model.

###  VII-B Black Box Watermarking Techniques

Black-box watermarking techniques account for the impossibility of physically
accessing the ML model to verify the presence of the watermark. As such, they
rely on querying the ML model and correlating the information from the
predictions the ML model gives to infer if the watermark is present. Adi et
al. [1] watermark construction is based on the concept of backdooring neural
networks [19]. The watermark consists of an unique set of input instances to
which a random label, from the model’s output space, is assigned. Watermarking
the deep neural network requires only training the network, beside the
original training set, also on the watermark instances. Similarly, Chen et al.
[7] encode the watermark using a set of image and label pairs that are
designed using targeted adversarial attacks, each of which representing a bit
of the watermark. Jia et al. [24] leverage the soft nearest neighbor loss to
entangle representations extracted from training data and watermarks, forcing
the model to classify data from the task distribution while simultaneously
being able to predict the pre-chosen watermark instances. Le Merrer et al.
[32] use embed the watermark via adversarial training the ML model along a set
of true and false adversarial examples such that they are correctly
classified. The watermark verification consists of observing the prediction
that the model gives to such adversarial examples. Yang et al. [50] embed the
watermark into the same neural connections that are responsible for
representing the main classification task by adding an in-grainer loss to
normal model’s loss function. Namba et al. [34] watermark a model by selecting
a trigger dataset from training data and assigning wrong labels as watermark
keys and then use exponential weighting to enforce watermark predictions
during training. Szyller et al. [41] aim at defending model extraction attacks
by changing a small amount (e.g., $\leq 0.5\%$) of query answers given by the
prediction API, to introduce a watermark into the extracted model.

###  VII-C Threats to Watermarking Techniques

Several works have been proposed to assess watermark resilience to malicious
adversaries trying to remove [22, 46, 34, 44], overwrite [46], forge [49, 15]
and detect them [46, 38]. Wang et al. [44] propose a generalized technique to
detect and mitigate backdoors in DNNs that can be applied to mitigate
backdoor-based watermarking schemes. Chen et al. [8] propose REFIT, a
framework to remove watermarks through fine-tuning. They show that making a
model forget part of the task it was initially trained on, can effectively
remove watermarks. They do that by devising a learning rate schedule, fine-
tuning with additional data, and using elastic weight consolidation [26]. We
demonstrate the robustness of TATTOOED against the removal techniques proposed
by Chen et al. [8] in Section VI-B. Wang et al. [46] demonstrate that many
watermarking schemes that embed watermarks into model parameters, change the
model weight distribution, thus making the watermarks detectable.
Additionally, they propose an attack to disrupt watermarks embedded with the
methods of Uchida et al. [43], detecting the watermark by analyzing the model
parameters distribution. We show that TATTOOED does not alter the distribution
of the model parameters in Section VI-F, thus making the attack proposed by
Wang et al. [46] ineffective. Shafieinejad et al. [38] present a technique to
remove watermarks in the white-box and black-box settings by exploiting the
fact that backdoor-based watermarks use additional data points as trigger for
watermarking. These points are outliers and applying methods to avoid over-
fitting is useful to remove these kinds of watermarks. This technique is
ineffective against TATTOOED since the TATTOOED watermark does not introduce a
backdoor in the model. Xu et al. [49] propose an attack that can forge the
backdoor-based watermark by finding the trigger inputs and then claiming
ownership of the model. TATTOOED does not use any trigger inputs, thus making
this type of attack ineffective. Moreover, due to TATTOOED foundations on
CDMA, only the proprietary of the spreading codes (i.e., the key to generate
them) can retrieve the watermark and claim legitimate ownership.

##  VIII Conclusions

In this paper we introduced TATTOOED, a novel white-box neural network
watermarking technique based on CDMA spread-spectrum channel-coding. Our
extensive evaluation showed that TATTOOED watermark incurs no penalty on the
model performance, and it can be applied to any model architecture and task
without modifications.

We demonstrated that TATTOOED watermark remains unaffected by state-of-the-art
watermark removal techniques based on fine-tuning and model parameter pruning
thus improving the state-of-the-art for white-box watermarking of neural
networks. Moreover, TATTOOED is significantly more efficient to watermark and
verify the watermark presence in a DNN compared to previous watermarking
techniques. The combination of robustness, practicality, and efficiency make
TATTOOED a strategy of choice for DNN IP protection.

## References

  * [1] Y. Adi, C. Baum, M. Cisse, B. Pinkas, and J. Keshet, “Turning your weakness into a strength: Watermarking deep neural networks by backdooring,” in _27th USENIX Security Symposium (USENIX Security 18)_. Baltimore, MD: USENIX Association, 2018. [Online]. Available: https://www.usenix.org/conference/usenixsecurity18/presentation/adi
  * [2] T. Bansal, D. Belanger, and A. McCallum, “Ask the GRU: Multi-task learning for deep text recommendations,” in _proceedings of the 10th ACM Conference on Recommender Systems_ , 2016, pp. 107–114.
  * [3] J. Behrmann, W. Grathwohl, R. T. Chen, D. Duvenaud, and J.-H. Jacobsen, “Invertible residual networks,” in _International Conference on Machine Learning_. ICML, 2019, pp. 573–582.
  * [4] F. Boenisch, “A survey on model watermarking neural networks,” _arXiv preprint arXiv:2009.12153_ , 2020.
  * [5] L. Breiman, “Random forests,” _Machine Learning_ , vol. 45, no. 1, pp. 5–32, 2001.
  * [6] H. Chen, B. D. Rouhani, C. Fu, J. Zhao, and F. Koushanfar, “Deepmarks: A secure fingerprinting framework for digital rights management of deep learning models,” in _Proceedings of the 2019 on International Conference on Multimedia Retrieval_ , ser. ICMR ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 105–113. [Online]. Available: https://doi.org/10.1145/3323873.3325042
  * [7] H. Chen, B. D. Rouhani, and F. Koushanfar, “Blackmarks: Blackbox multibit watermarking for deep neural networks,” _ArXiv_ , vol. abs/1904.00344, 2019\.
  * [8] X. Chen, W. Wang, C. Bender, Y. Ding, R. Jia, B. Li, and D. Song, “Refit: A unified watermark removal framework for deep learning systems with limited data,” in _Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security_ , ser. ASIA CCS ’21. New York, NY, USA: Association for Computing Machinery, 2021, p. 321–335. [Online]. Available: https://doi.org/10.1145/3433210.3453079
  * [9] A. Continella, A. Guagnelli, G. Zingaro, G. De Pasquale, A. Barenghi, S. Zanero, and F. Maggi, “Shieldfs: A self-healing, ransomware-aware filesystem,” in _ACSAC_ , 2016.
  * [10] I. Cox, J. Kilian, T. Leighton, and T. Shamoon, “Secure spread spectrum watermarking for images, audio and video,” in _Proceedings of 3rd IEEE International Conference on Image Processing_ , vol. 3, 1996, pp. 243–246 vol.3.
  * [11] B. Darvish Rouhani, H. Chen, and F. Koushanfar, “Deepsigns: An end-to-end watermarking framework for ownership protection of deep neural networks,” in _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems_ , ser. ASPLOS ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 485–497. [Online]. Available: https://doi.org/10.1145/3297858.3304051
  * [12] F. De Gaspari, D. Hitaj, G. Pagnotta, L. De Carli, and L. V. Mancini, “Encod: Distinguishing compressed and encrypted file fragments,” in _Network and System Security_ , M. Kutyłowski, J. Zhang, and C. Chen, Eds., 2020, pp. 42–62.
  * [13] ——, “The naked sun: Malicious cooperation between benign-looking processes,” in _International Conference on Applied Cryptography and Network Security_. Springer, 2020, pp. 254–274.
  * [14] J. Devlin, M. Chang, K. Lee, and K. Toutanova, “BERT: pre-training of deep bidirectional transformers for language understanding,” in _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019_ , 2019, pp. 4171–4186. [Online]. Available: https://doi.org/10.18653/v1/n19-1423
  * [15] L. Fan, K. W. Ng, and C. S. Chan, “Rethinking deep neural network ownership verification: Embedding passports to defeat ambiguity attacks,” in _Advances in Neural Information Processing Systems_ , H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, Eds., vol. 32. Curran Associates, Inc., 2019. [Online]. Available: https://proceedings.neurips.cc/paper/2019/file/75455e062929d32a333868084286bb68-Paper.pdf
  * [16] R. Gallager, “Low-density parity-check codes,” _IRE Transactions on Information Theory_ , vol. 8, no. 1, pp. 21–28, 1962.
  * [17] I. Goodfellow, Y. Bengio, and A. Courville, _Deep Learning_. MIT Press, 2016, http://www.deeplearningbook.org.
  * [18] A. Graves, A. Mohamed, and G. Hinton, “Speech recognition with deep recurrent neural networks,” in _2013 IEEE International Conference on Acoustics, Speech and Signal Processing_ , May 2013, pp. 6645–6649.
  * [19] T. Gu, B. Dolan-Gavitt, and S. Garg, “Badnets: Identifying vulnerabilities in the machine learning model supply chain,” 08 2017.
  * [20] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 770–778, 2016.
  * [21] J. Hernandez, M. Amado, and F. Perez-Gonzalez, “Dct-domain watermarking techniques for still images: detector performance analysis and a new structure,” _IEEE Transactions on Image Processing_ , vol. 9, no. 1, pp. 55–68, 2000.
  * [22] D. Hitaj, B. Hitaj, and L. V. Mancini, “Evasion attacks against watermarking techniques found in mlaas systems,” in _2019 Sixth International Conference on Software Defined Systems (SDS)_ , 2019, pp. 55–63.
  * [23] D. Hitaj, G. Pagnotta, B. Hitaj, F. Perez-Cruz, and L. V. Mancini, “Fedcomm: Federated learning as a medium for covert communication,” _arXiv preprint arXiv:2201.08786_ , 2022. [Online]. Available: https://arxiv.org/pdf/2201.08786.pdf
  * [24] H. Jia, C. A. Choquette-Choo, and N. Papernot, “Entangled watermarks as a defense against model extraction,” in _USENIX Security Symposium_ , 2021\.
  * [25] T. Karras, S. Laine, and T. Aila, “A style-based generator architecture for generative adversarial networks,” in _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019, pp. 4396–4405.
  * [26] J. Kirkpatrick, R. Pascanu, N. C. Rabinowitz, J. Veness, G. Desjardins, A. A. Rusu, K. Milan, J. Quan, T. Ramalho, A. Grabska-Barwinska, D. Hassabis, C. Clopath, D. Kumaran, and R. Hadsell, “Overcoming catastrophic forgetting in neural networks,” _Proceedings of the National Academy of Sciences_ , vol. 114, pp. 3521 – 3526, 2017.
  * [27] A. Krizhevsky, “Learning multiple layers of features from tiny images,” 2009\.
  * [28] Y. LeCun and C. Cortes, “MNIST handwritten digit database,” http://yann.lecun.com/exdb/mnist/, 2010.
  * [29] Y. Li, X. Lyu, N. Koren, L. Lyu, B. Li, and X. Ma, “Neural attention distillation: Erasing backdoor triggers from deep neural networks,” in _International Conference on Learning Representations_ , 2021. [Online]. Available: https://openreview.net/forum?id=9l0K4OM-oXE
  * [30] W. Marx, “How valencia crushed covid with ai,” https://www.wired.co.uk/article/valencia-ai-covid-data, 2021.
  * [31] S. Merity, C. Xiong, J. Bradbury, and R. Socher, “Pointer sentinel mixture models,” _CoRR_ , vol. abs/1609.07843, 2016. [Online]. Available: http://arxiv.org/abs/1609.07843
  * [32] E. L. Merrer, P. Perez, and G. Trédan, “Adversarial frontier stitching for remote neural network watermarking,” _CoRR_ , vol. abs/1711.01894, 2017.
  * [33] Y. Nagai, Y. Uchida, S. Sakazawa, and S. Satoh, “Digital watermarking for deep neural networks,” _International Journal of Multimedia Information Retrieval_ , vol. 7, pp. 3–16, 2018.
  * [34] R. Namba and J. Sakuma, “Robust watermarking of neural network with exponential weighting,” in _Proceedings of the 2019 ACM Asia Conference on Computer and Communications Security_ , ser. Asia CCS ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 228–240. [Online]. Available: https://doi.org/10.1145/3321705.3329808
  * [35] K. J. Piczak, “ESC: Dataset for Environmental Sound Classification,” in _Proceedings of the 23rd Annual ACM Conference on Multimedia_. ACM Press, pp. 1015–1018. [Online]. Available: http://dl.acm.org/citation.cfm?doid=2733373.2806390
  * [36] T. Richardson and R. Urbanke, _Modern Coding Theory_. Cambridge University Press, 2008.
  * [37] B. Scholkopf and A. J. Smola, _Learning with kernels: support vector machines, regularization, optimization, and beyond_. MIT press, 2001.
  * [38] M. Shafieinejad, N. Lukas, J. Wang, X. Li, and F. Kerschbaum, “On the robustness of backdoor-based watermarking in deep neural networks,” in _Proceedings of the 2021 ACM Workshop on Information Hiding and Multimedia Security_. New York, NY, USA: Association for Computing Machinery, 2021, p. 177–188. [Online]. Available: https://doi.org/10.1145/3437880.3460401
  * [39] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” 2014.
  * [40] C. Song, T. Ristenpart, and V. Shmatikov, “Machine learning models that remember too much,” in _Proceedings of the 2017 ACM SIGSAC Conference on computer and communications security_ , 2017, pp. 587–601.
  * [41] S. Szyller, B. G. Atli, S. Marchal, and N. Asokan, _DAWN: Dynamic Adversarial Watermarking of Neural Networks_. New York, NY, USA: Association for Computing Machinery, 2021, p. 4417–4425. [Online]. Available: https://doi.org/10.1145/3474085.3475591
  * [42] D. Torrieri, _Principles of Spread-Spectrum Communication Systems, 4th Edition_. Springer, Cham, 2018.
  * [43] Y. Uchida, Y. Nagai, S. Sakazawa, and S. Satoh, “Embedding watermarks into deep neural networks,” in _Proceedings of the 2017 ACM on International Conference on Multimedia Retrieval_ , ser. ICMR ’17. New York, NY, USA: Association for Computing Machinery, 2017, p. 269–277. [Online]. Available: https://doi.org/10.1145/3078971.3078974
  * [44] B. Wang, Y. Yao, S. Shan, H. Li, B. Viswanath, H. Zheng, and B. Y. Zhao, “Neural cleanse: Identifying and mitigating backdoor attacks in neural networks,” in _2019 IEEE Symposium on Security and Privacy (SP)_ , 2019, pp. 707–723.
  * [45] J. Wang, H. Wu, X. Zhang, and Y. Yao, “Watermarking in deep neural networks via error back-propagation,” _Electronic Imaging_ , vol. 2020, pp. 22–1, 01 2020.
  * [46] T. Wang and F. Kerschbaum, “Attacks on digital watermarks for deep neural networks,” in _ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2019, pp. 2622–2626.
  * [47] ——, “Riga: Covert and robust white-box watermarking of deep neural networks,” in _Proceedings of the Web Conference 2021_ , ser. WWW ’21. New York, NY, USA: Association for Computing Machinery, 2021, p. 993–1004. [Online]. Available: https://doi.org/10.1145/3442381.3450000
  * [48] J. Wu, C. Leng, Y. Wang, Q. Hu, and J. Cheng, “Quantized convolutional neural networks for mobile devices,” in _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_. Los Alamitos, CA, USA: IEEE Computer Society, jun 2016, pp. 4820–4828. [Online]. Available: https://doi.ieeecomputersociety.org/10.1109/CVPR.2016.521
  * [49] X. Xu, Y. Li, and C. Yuan, “A novel method for identifying the deep neural network model with the serial number,” _ArXiv_ , vol. abs/1911.08053, 2019\.
  * [50] Z. Yang, H. Dang, and E.-C. Chang, “Effectiveness of distillation attack and countermeasure on neural network watermarking,” _ArXiv_ , vol. abs/1906.06046, 2019.
  * [51] J. Zhang, Z. Gu, J. Jang, H. Wu, M. P. Stoecklin, H. Huang, and I. Molloy, “Protecting intellectual property of deep neural networks with watermarking,” in _Proceedings of the 2018 on Asia Conference on Computer and Communications Security_ , ser. ASIACCS ’18. New York, NY, USA: Association for Computing Machinery, 2018, p. 159–172. [Online]. Available: https://doi.org/10.1145/3196494.3196550


Clustering and Labelling Auction Fraud Data

Ahmad Alzahrani and Samira Sadaoui
CS 2018-08
DOI: 10.6084/m9.figshare.6993308

Copyright © 2018, A. Alzahrani, S. Sadaoui

Department of Computer Science

University of Regina

Regina, SK, CANADA

S4S 0A2

###### Abstract

Although shill bidding is a common auction fraud, it is however very tough to
detect. Due to the unavailability and lack of training data, in this study, we
build a high-quality labeled shill bidding dataset based on recently collected
auctions from eBay. Labeling shill biding instances with multidimensional
features is a critical phase for the fraud classification task. For this
purpose, we introduce a new approach to systematically label the fraud data
with the help of the hierarchical clustering CURE that returns remarkable
results as illustrated in the experiments.

##  I Introduction

The last three decades witnessed a significant increase in exchanging goods
and services over the Web. According to the World Trade Organization, the
worldwide merchandise during the period 1995-2015 was over 18 billion
111https://www.wto.org/english/res_e/statis_e/its2015_e/its2015_e.pdf. Online
auctions are a very profitable e-commerce application. In 2017, eBay claimed
that the net revenue reached 9.7 billion US dollars, and the number of active
users hit 170 million 222https://www.statista.com. Regardless of their
popularity, e-auctions remain very vulnerable to cyber-crimes. The high
anonymity of users, low fees of auction services and flexibility of bidding
make auctions a great incubator for fraudulent activities. The Internet Crime
Complain Center (IC3) announced that auction fraud is one of the top cyber-
crimes [1]. As an example, the complaints about auction fraud in only three
states, California, Florida and New York, reached 7,448 in 2016 [1].
Fraudsters can commit three types of fraud, which are pre-auction fraud, such
as auctioning of black market merchandise, in-auction fraud that occurs during
the bidding time, such as Shill Bidding (SB), and post-auction fraud, such as
fees stacking. Our primary focus is on SB whose goal is to increase the
profits of sellers. SB does not leave any concrete evidence unlike the two
other fraud. Indeed, buyers are not even aware that they have been
overcharged.

Identifying relevant SB strategies, determining robust SB metrics,
preprocessing commercial auction data, and finally evaluation the SB metrics
based on the extracted data make the study of SB fraud very challenging. In
addition, labeling SB instances with multidimensional features is a critical
phase for the classification models. In the literature, labeling training data
is usually done manually by the domain experts, which is quite a laborious
task and is prone to errors too. Due to the unavailability and lack of labeled
SB training datasets, the main contribution of this paper is to produce high-
quality labeled SB data based on commercial auction transactions that we have
extracted lately and preprocessed [2]. As illustrated in Figure 1, we
introduce a new approach to systematically label SB data with the help of data
clustering. This approach consists of splitting first the SB dataset into
several subsets according to the different bidding durations.

Since hierarchical clustering is significantly preferable over partitioning
clustering and provides a higher quality of clusters, we applied the
Clustering Using Representatives (CURE) technique to produce the best
differentiation between normal and suspicious bidders. CURE [3] has been
proved over the years to be a very efficient clustering method for large-scale
training datasets in terms of the cluster quality and outlier elimination.
Hierarchical clustering has been practiced successfully in numerous fraud
studies [4, 5]. The resulting labeled SB dataset can be employed by the state-
of-the-art classification methods. Furthermore, the accuracy of new predictive
models can also be tested using our SB training dataset.

Figure 1: The Labeling Process of the SB Training Dataset

##  II Shill Bidding Overview

SB is a well-known auction fraud, and yet it is the most difficult to detect
since it behaves similarly to normal bidding [6, 4]. It aim is to increase the
price or desirability of the auctioned item. In other words, the objective of
a shill bidder is not to win the auction but to raise the revenue of the
seller. SB leads buyers to overpay for the items, especially for high priced
items. Thus, e-auctions may lose their credibility [6]. In Table I, we
highlight the most relevant SB patterns [7]. Each pattern, representing a
classification feature, provides a unique aspect of the bidding behaviour,
which is very important for building robust fraud classifiers.

Table I: SB Patterns and their Characteristics Name |  Definition |  Category |  Source
---|---|---|---
Bidder Tendency (BT) |  Participates exclusively in auctions of few sellers rather than a diversified lot |  Bidder |  User history
Bidding Ratio (BR) |  Participates more frequently to raise the auction price |  Bid |  Bidding period
Successive Outbidding (SO) |  Successively outbids himself even though he is the current winner |  Bid |  Bidding period
Last Bidding (LB) |  Becomes inactive at the last stage to avoid winning |  Bid |  Last bidding stage
Early Bidding (EB) |  Tends to bid pretty early in the auction to get users attention |  Bid |  Early bidding stage
Winning Ratio (WR) |  Competes in many auctions but hardly wins any auctions |  Bidder |  User history
Auction Bids (AB) |  Tends to have a much higher number of bids than the average of bids in auction dataset |  Auction |  Auction history
Auction Starting Price (ASP) |  Offers a small starting price to attract genuine bidders |  Auction |  Auction history

##  III Production of Shill Bidding Data from Online Auctions

###  III-A Auction Data Extraction and Preprocessing

To obtain a reliable SB training dataset, it must be built from actual auction
data. Nevertheless, producing high quality auction data is itself a burdensome
operation due to the difficulty of collecting data from auction sites on one
hand, and the challenging task of preprocessing the raw data on the other
hand. The latter consumes a significant time and effort, around 60% to 80% of
the entire workload [8]. In our previous study [2] , we employed the
professional scraper Octopars 333https://www.octoparse.com to collect a large
number of auctions for one of the most popular products on eBay. The extracted
dataset contains all the information related to auctions, bids and bidders. We
crawled completed auctions of the iPhone 7 for three months (March to June
2017). We chose iPhone 7 because it may have attracted malicious moneymakers
due to the following facts:

  * •

Its auctions attracted a high number of bidders and bids.

  * •

It has a good price range with the average of $610.17 (US currency). Indeed,
there is a direct relationship between SB fraud and the auction price [9].

  * •

The bidding duration varies between 1 (20.57%), 3 (23.2%), 5 (16.23%), 7
(38.3%) and 10 (1.7%) days. In long duration, a dishonest bidder may easily
mimic usual bidding behaviour [9]. However, as claimed in [10], fraudulent
sellers may receive positive rating in short duration. Thus, we considered
both durations.

Table II presents the statistics after preprocessing the scraped auction data.
This operation was very time consuming as it required several manual
operations [2]: 1) removing redundant and inconsistent records, and also
records with missing bidder IDs; 2) merging several attributes into a single
one; 3) converting the format of several attributes into a proper one; 4)
assigning auction IDs. For instance, Date and Time attributes in each auction
are converted into seconds; e.g. 1 day and 10 day durations are converted into
86,400 and 864,000 seconds respectively.

Table II: Preprocessed Auctions of iPhone 7 No. of Auctions |  807
---|---
No. of Records |  15145
No. of Bidder IDs |  1054
No. of Seller IDs |  647
Avg. Winning Price |  $ 578.64
Avg. Bidding Duration |  7
No. of Attributes |  12

The metrics of SB patterns are presented in [7, 2]. Each metric is scaled to
the range of [0, 1]; a high value indicates suspicious bidding behaviour. We
computed each metric against each bidder in each of the 807 auctions [2]. As a
result, we obtained a SB training dataset with a total of 6321 instances. Each
instance denotes the conduct of a bidder in a certain auction. An instance is
a vector of 10 elements: Auction ID, Bidder ID and the eight SB features.

##  IV Hierarchical Clustering of Shill Bidding Data

Since SB data are not labeled, data clustering, an unsupervised learning
method, can be utilized to facilitate the labeling task. Clustering is the
process of isolating instances into K groups based on their similarities. The
clustering techniques fall into one of the following categories: 1)
Partitioning-based, such as K-medoids and K-means; 2) Hierarchical-based, such
as BIRCH, GRIDCLUST and CURE; 3) Density-based, such as DBSCAN and DBCLASD; 4)
Grid-based, such as STING and CLIQUE. In our work, we select agglomerative
(bottom-top) Hierarchical Clustering (HC) where instances are arranged in the
form of a tree structure using a proximity matrix.

###  IV-A CURE Overview

Among the hierarchical clustering methods, we choose CURE because it is very
performant in handling large-scale multi-dimensional datasets, determines non-
spherical shapes of clusters, and efficiently eliminates outliers [3]. Random
sampling and partitioning techniques are utilized to handle the large-scale
problem. Each selected instance is first considered as an individual cluster,
and the clusters with the closest distance/similarity are integrated into a
final cluster [3]. Two novel strategies have been introduced in CURE:

  * •

Representative Points (RPs), which are selected data points that define the
cluster boundary. Instead of using a centroid, clusters are identified by a
fixed number of RPs that are well scattered. Clusters with the closest RPs are
merged into one cluster. The multiplicity of RPs allow CURE to obtain
arbitrary clustering shapes.

  * •

Constant shrinking factor ($\alpha$), which is utilized to shrink the distance
of RPs towards the centroid of the cluster. This factor reduces noise and
outliers.

The worst case time complexity of CURE is estimated to $O(N^{2}\ log\ N)$,
which is high when $N$ is large ($N$ is the number of instances) [11]. Since
SB data clustering is an offline operation, so the running time is not an
issue. The only disadvantage of CURE is that the two parameters RP and
$\alpha$ have to be set up by users. To run the experiments, we utilize the
Anaconda-Navigator environment for running Python 3, and we integrate GitHub
service to incorporate the CURE program developed by Freddy Stein and Zach
Levonian 444https://github.com/levoniaz/python-cure-
implementation/blob/master/cure.py.

###  IV-B SB Data Preparation

Since the bidding duration is used as a denominator in EB and LB patterns, the
large gap between different durations greatly affects the computation results.
The pattern value for 10 days is far smaller than for 1 day. So, before
applying CURE, we first partition the SB dataset into five subsets according
to the five durations (1, 3, 5, 7 and 10 days) as presented in Table III. We
compute the Mean and STandard Deviation (STD) of each subset, which will be
individually passed into CURE for clustering along with the best number of
clusters. Here a cluster contains instances/bidders with similar bidding
behaviour.

Table III: SB Dataset Partitioning According to Bidding Duration Partition |  1 Day |  3 Days |  5 Days |  7 Days |  10 Days
---|---|---|---|---|---
Mean of each pattern per partition
BT |  0.1434 |  0.1394 |  0.1419 |  0.1455 |  0.1162
BR |  0.1287 |  0.1328 |  0.1235 |  0.1273 |  0.1021
SO |  0.0996 |  0.1047 |  0.0872 |  0.1149 |  0.0620
LB |  0.4624 |  0.4511 |  0.4676 |  0.4678 |  0.4746
EB |  0.4314 |  0.4192 |  0.4318 |  0.4348 |  0.4575
WR |  0.3812 |  0.3718 |  0.3810 |  0.3533 |  0.3496
AB |  0.2120 |  0.1936 |  0.2403 |  0.2567 |  0.2926
ASP |  0.5007 |  0.4301 |  0.4478 |  0.4801 |  0.7123
Avg. Means |  0.2949 |  0.2802 |  0.2901 |  0.2975 |  0.3208
STD of each pattern per partition
BT |  0.1973 |  0.1884 |  0.1984 |  0.2019 |  0.1811
BR |  0.1246 |  0.1330 |  0.1243 |  0.1377 |  0.1165
SO |  0.2764 |  0.2811 |  0.2583 |  0.2917 |  0.2215
LB |  0.3773 |  0.3753 |  0.3917 |  0.3783 |  0.3931
EB |  0.3775 |  0.3742 |  0.3921 |  0.3802 |  0.3968
WR |  0.4356 |  0.4373 |  0.4402 |  0.4345 |  0.4398
AB |  0.2323 |  0.2426 |  0.2646 |  0.2658 |  0.2575
ASP |  0.4931 |  0.4831 |  0.4863 |  0.4908 |  0.4510
Avg. STDs |  0.3142 |  0.3143 |  0.3194 |  0.3226 |  0.3071

###  IV-C Optimal Number of Clusters

It is always difficult to decide about the optimal number of clusters.
Besides, normal and shill bidder behaviour is somehow similar. Thus,
determining the best number of clusters is an essential step to achieve a
better interpretation for classifying similar SB instances [12]. There are
several methods to address this problem, such as Elbow, Dendrogram, the Rule
of Thumb and Silhouette. In our study, we employ the Silhouette method where
each group is represented as a silhouette based on the separation between
instances and the cluster’s tightness [13]. The construction of a silhouette
requires the clustering technique to generate the partitions and also to
collect all approximates between instances [13]. K-mean clustering algorithm
has been successfully utilized for this task due to its simplicity and
effectiveness [12]. Therefore, we apply K-mean to estimate the number of
clusters for each of the five SB subsets. Next, we examine the silhouette
scores for 19 clusters, and choose the best number based on the best
silhouette score. In Figure 2, we give an example for the 7 day bidding
duration. Instances are partitioned into eight clusters since the highest
silhouette score (0.4669) is obtained on that number. In Table IV, we expose
the best number of clusters for each of the five SB subsets.

Figure 2: Optimal number of clusters for 7 day bidding duration. Silhouette score is examined 19 times. We show the top three Silhouette scores. Table IV: The best number of clusters for each SB subset Subset |  Number of Clusters
---|---
1 Day |  7
3 Days |  7
5 Days |  5
7 Days |  8
10 Days |  2
Total |  29

###  IV-D Cluster Generation

CURE has three parameters that need to be setup: representative points,
shrinking factor and optimal number of clusters. Based on the results of
silhouette, we obtain the optimal number of clusters for each of the five SB
subsets. RPs and $\alpha$ are defined by selecting the setting that provides
the best instance distribution among the specified clusters. Thus, CURE is
applied with different RPs and $\alpha$ parameters starting from the default
values on the eight clusters (see Table V).

Table V: CURE Clustering for 7 day Bidding Duration RP |  $\alpha$ |  C#1 |  C#2 |  C#3 |  C#4 |  C#5 |  C#6 |  C#7 |  C#8
---|---|---|---|---|---|---|---|---|---
5 |  0.1 |  136 |  1438 |  1 |  2 |  657 |  190 |  2 |  1
5 |  0.05 |  657 |  328 |  2 |  1408 |  1 |  28 |  2 |  1
5 |  0.01 |  1438 |  640 |  1 |  1 |  17 |  1 |  1 |  328
5 |  0.001 |  21 |  166 |  2 |  1 |  2 |  25 |  2209 |  1
10 |  0.1 |  2 |  1 |  657 |  1410 |  22 |  8 |  137 |  190
10 |  0.05 |  2 |  133 |  2 |  1 |  2 |  31 |  2066 |  190
10 |  0.01 |  1 |  1 |  1 |  1 |  135 |  31 |  2067 |  190
10 |  0.001 |  189 |  654 |  1410 |  3 |  137 |  31 |  1 |  2
Table VI: SB Instances and CURE Classification AuctionID |  900 |  900 |  2370 |  432 |  1370
---|---|---|---|---|---
BidderID |  z***z |  k***a |  g***r |  0***0 |  o***-
BT |  0.75 |  0.4705 |  0.8333 |  0.5 |  0.04615
BR |  0.3461 |  0.3076 |  0.2 |  0.3333 |  0.0857
SO |  1 |  0 |  1 |  0 |  0.5
LB |  0.5667 |  0.1909 |  0.0350 |  0.2199 |  0.2966
EB |  0.5409 |  0.1909 |  0.0239 |  0.0043 |  0.2060
WR |  0.75 |  0.4 |  1 |  0.5 |  0
AB |  0 |  0 |  0.3333 |  0 |  0.0526
ASP |  0 |  0 |  0.9935 |  0 |  0
Label |  1 |  0 |  1 |  0 |  0

##  V Labeling Shill Bidding Data

Algorithm 1 : Labeling Bidders in a Cluster

1:Mean and STD of the corresponding subset

2:Compute $MeanOfCluster$

3:if ($MeanOfCluster\geq$ ($Mean+\frac{STD}{2}$)) then

4: for x=1 to $NumberOBiddersCluster$ do

5: $LabelOfBidder_{x}$ = 1 (Suspicious)

6: end for

7:else

8: for x=1 to $NumberOfBiddersCluster$ do

9: $LabelOfBidder_{x}$ = 0 (Normal)

10: end for

11:end if

In algorithm 1, we show the steps to label the bidders of a cluster. A cluster
belongs to a certain subset. We consider the value of $Mean+\frac{1}{2}STD$ of
the subset since it produces the best decision line that separates between
normal and suspicious instances as depicted in Figure 3. The decision line is
defined by the average of the means and STDs of the values of the SB patterns
in that subset. So, if the mean of the cluster is greater than the decision
line, then instances are labeled as suspicious (1) in that cluster; otherwise,
they are labeled normal (0). We also give an example in Table VI where the
bidders belong to the 7 Day subset. As we can observe in this table, the shill
bidding instances are similar to the normal bidding instances, and our
labeling approach has successfully classified each instance.

Table VII provides all the best results of the clustering and labeling of our
SB dataset. There are 5646 instances categorized as normal and 675 instances
as suspicious. The total number of produced clusters is 29.

Figure 3: Labeling decision line of a cluster of a subset Table VII: Final Results of Clustering and Labeling Partitions |  1 Day |  3 Days |  5 Days |  7 Days |  10 Days |  Total
---|---|---|---|---|---|---
Auctions |  166 |  187 |  131 |  309 |  14 |  807
Instances |  1289 |  1408 |  1060 |  2427 |  137 |  6321
Clusters |  7 |  7 |  5 |  8 |  2 |  29
RP |  5 |  5 |  5 |  10 |  5 |  NA
$\alpha$ |  0.05 |  0.01 |  0.05 |  0.001 |  0.1 |  NA
Normal |  1135 |  1303 |  975 |  2098 |  135 |  5646
Suspicious |  154 |  105 |  85 |  329 |  2 |  675

##  VI Conclusion and Future Work

There are limited SB classification studies due to the difficulty of
identifying useful SB strategies in one hand, and the unavailability of
labeled training SB data on the other hand. Producing and labeling SB training
data are both critical tasks for implementing SB classifiers. Our aim is to
effectively label SB data based on hierarchical clustering. CURE has shown a
remarkable capability for partitioning the behaviour of bidders. After data
clustering, we automatically label each cluster with our own approach. Our
future work mainly concentrates on the following work:

  * •

The generated SB dataset is highly imbalanced, which will negatively impact
the performance of classifiers as shown in [14]. The decision boundary of the
fraud classifiers will be biased towards the normal class, which means
suspicious bidders will poorly be detected. Handling the class imbalance
problem is a continuous area of study [15]. In our research, we will
investigate this problem and test different types of techniques, such as over-
sampling, under-sampling and cost-sensitive learning, to verify the most
suitable technique for our SB dataset.

  * •

Ensemble learning has produced reliable classification performance for
numerous practical applications. The objectives defined by ensemble learning
are lowering the model’s error ratio, avoiding the overfitting problem, and
reducing the bias and variance errors. The most common ensemble methods are
Boosting and Bootstrap Aggregation (Bagging). Thus, we will employ the
ensemble learning to implement a robust SB detection model, and investigate
the most fitting ensemble methods for the SB dataset.

## Acknowledgments

The first author would like to thank Umm Al-Qura University and the Saudi
Arabian Cultural Bureau in Canada for the generous financial support.

## References

  * [1] I. C. C. Center, “2015 internet crime report,” in _2015 IC3 Report_. IC3, 2016.
  * [2] A. Alzahrani and S. Sadaoui, “Scraping and preprocessing commercial auction data for fraud classification,” _arXiv preprint arXiv:1806.00656_ , 2018\.
  * [3] S. Guha, R. Rastogi, and K. Shim, “Cure: an efficient clustering algorithm for large databases,” in _ACM Sigmod Record_ , vol. 27, no. 2. ACM, 1998, pp. 73–84.
  * [4] B. J. Ford, H. Xu, and I. Valova, “A real-time self-adaptive classifier for identifying suspicious bidders in online auctions,” _The Computer Journal_ , vol. 56, no. 5, pp. 646–663, 2012.
  * [5] S. Ganguly and S. Sadaoui, “Online detection of shill bidding fraud based on machine learning techniques,” in _International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems_. Springer, 2018, pp. 303–314.
  * [6] F. Dong, S. M. Shatz, and H. Xu, “Combating online in-auction fraud: Clues, techniques and challenges,” _Computer Science Review_ , vol. 3, no. 4, pp. 245–258, 2009.
  * [7] S. Sadaoui and X. Wang, “A dynamic stage-based fraud monitoring framework of multiple live auctions,” _Applied Intelligence_ , vol. 46, no. 1, pp. 197–213, 2017.
  * [8] P. Ravisankar, V. Ravi, G. R. Rao, and I. Bose, “Detection of financial statement fraud and feature selection using data mining techniques,” _Decision Support Systems_ , vol. 50, no. 2, pp. 491–500, 2011.
  * [9] F. Dong, S. M. Shatz, and H. Xu, “Combating online in-auction fraud: Clues, techniques and challenges,” _Computer Science Review_ , vol. 3, no. 4, pp. 245–258, 2009.
  * [10] J.-S. Chang and W.-H. Chang, “Analysis of fraudulent behavior strategies in online auctions for detecting latent fraudsters,” _Electronic Commerce Research and Applications_ , vol. 13, no. 2, pp. 79–97, 2014.
  * [11] D. Xu and Y. Tian, “A comprehensive survey of clustering algorithms,” _Annals of Data Science_ , vol. 2, no. 2, pp. 165–193, 2015.
  * [12] H. Yu, Z. Liu, and G. Wang, “An automatic method to determine the number of clusters using decision-theoretic rough set,” _International Journal of Approximate Reasoning_ , vol. 55, no. 1, pp. 101–115, 2014.
  * [13] P. J. Rousseeuw, “Silhouettes: a graphical aid to the interpretation and validation of cluster analysis,” _Journal of computational and applied mathematics_ , vol. 20, pp. 53–65, 1987.
  * [14] S. Ganguly and S. Sadaoui, “Classification of imbalanced auction fraud data,” in _Canadian Conference on Artificial Intelligence_. Springer, 2017, pp. 84–89.
  * [15] S. Zhang, S. Sadaoui, and M. Mouhoub, “An empirical analysis of imbalanced data classification,” _Computer and Information Science_ , vol. 8, no. 1, pp. 151–162, 2015.