smallequation

$\BODY$

(1)

smallalign

$\BODY$

(2)

# Integrity Authentication in Tree Models

Weijie Zhao, Yingjie Lao, Ping Li

Cognitive Computing Lab
Baidu Research
10900 NE 8th St. Bellevue, WA 98004, USA

{zhaoweijie12, laoyingjie<EMAIL_ADDRESS>
###### Abstract

Tree models are very widely used in practice of machine learning and data
mining. In this paper, we study the problem of model integrity authentication
in tree models. In general, the task of model integrity authentication is the
design & implementation of mechanisms for checking/detecting whether the model
deployed for the end-users has been tampered with or compromised, e.g.,
malicious modifications on the model. We propose an authentication framework
that enables the model builders/distributors to embed a signature to the tree
model and authenticate the existence of the signature by only making a small
number of black-box queries to the model. To the best of our knowledge, this
is the first study of signature embedding on tree models. Our proposed method
simply locates a collection of leaves and modifies their prediction values,
which does not require any training/testing data nor any re-training. The
experiments on a large number of public classification datasets confirm that
the proposed signature embedding process has a high success rate while only
introducing a minimal prediction accuracy loss.

##  1 Introduction

Along with the evolution of machine learning, the growing cost of model
building in terms of computational power, data annotation, and human expertise
calls for intellectual property (IP) protection methods to secure the
innovations and creative endeavors in this field. The problem is clearly
aggravated by recent studies demonstrating that machine learning models are
vulnerable to various categories of adversarial attacks (Szegedy et al., 2014;
Papernot et al., 2016; Kurakin et al., 2017; Liu et al., 2018a; Yuan et al.,
2019; Doan et al., 2021a, b) and model stealing via reverse engineering or
model extraction (Hua et al., 2018; Hu et al., 2019; Juuti et al., 2019).
Especially under the machine learning as a service (MLaaS) paradigm where the
supply chain of models may involve multiple parties and vendors, the
proprietary assets of the model IP owner, including data, algorithm, and
computation infrastructure, are vulnerable to breach. On the other hand,
maliciously altered models, e.g., by poisoning or backdoor attacks (Chen et
al., 2017; Muñoz-González et al., 2017; Steinhardt et al., 2017; Shafahi et
al., 2018; Liu et al., 2017, 2018b; Gu et al., 2019; Doan et al., 2021a, b),
will also impair the integrity, reputation, and profit of the model owner.
These attacks have been extensively studied on various machine learning
models, including collaborative filtering (Li et al., 2016), logistic
regression (Muñoz-González et al., 2019), clustering (Biggio et al., 2018),
support vector machine (Biggio et al., 2012), and also deep neural networks
(Yang et al., 2017; Gu et al., 2017; Turner et al., 2019; Saha et al., 2020;
Shafahi et al., 2018). Very recently, such attacks on tree models have also
been investigated (Chen et al., 2019; Andriushchenko and Hein, 2019; Grari et
al., 2020; Zhang et al., 2020), which further demands techniques for
protecting tree models.

To this end, signature embedding and fingerprinting have emerged as promising
directions for protecting the advanced machine learning models (Uchida et al.,
2017; Adi et al., 2018; Zhang et al., 2018; Li et al., 2019b, a; Darvish
Rouhani et al., 2019; Fan et al., 2019; Cao et al., 2021; Le Merrer et al.,
2020; Zhong et al., 2020; Yang et al., 2021; Lao et al., 2022a, b).
Conceptually, these techniques embed a unique signature into a model that will
behave differently from other models. The presence of such signatures should
be easily verifiable in a later stage, which can serve as an ownership or
integrity proof. However, almost all of these prior methods are only targeting
deep neural networks, which is understandable as deep neural networks have
shown superior performance across many fields while requiring large costs to
build.

In this paper, as opposed to focusing on deep neural networks, we take the
first step to investigate signature embedding for (ensemble) tree models
(Brieman et al., 1983). We follow the direction of embedding fragile
watermarks (Lao et al., 2022b) for the purpose of verifying the integrity of
the model, which is different from robust watermarks (Uchida et al., 2017; Adi
et al., 2018; Zhang et al., 2018; Li et al., 2019b, a; Darvish Rouhani et al.,
2019; Fan et al., 2019; Yang et al., 2021; Lao et al., 2022a) that are used to
trace the IP ownership. In particular, we focus on boosted trees in our
experiments, although the ideas and concepts are also applicable to (e.g.,)
bagging (Breiman, 1996).

###  1.1 Boosted Tree Models

In machine learning practice, boosting (Schapire, 1990; Freund, 1995; Freund
and Schapire, 1997; Bartlett et al., 1998; Schapire and Singer, 1999; Friedman
et al., 2000; Friedman, 2001; Li, 2009, 2010; Li and Zhao, 2022) is one of the
most successful learning paradigms. Boosting is typically integrated with
trees (Brieman et al., 1983) to produce powerful tools for classification and
regression; Readers are also referred to some interesting discussions in 2010
https://hunch.net/?p=1467 for comparing deep neural networks with boosted
trees.

As summarized in a recent paper on trees (Fan and Li, 2020), there are two
recent implementation tricks that have made boosted tree models considerably
more practical:

  * •

Li et al. (2007) developed an adaptive binning strategy to effectively
transform any numerical features into (non-negative) integer values. This
binning operation is conducted on a feature-wise fashion hence it is highly
efficient. It is adaptive because, for each feature, it only assigns bins in
the regions where there are data points. Recall that tree model (Brieman et
al., 1983) (recursively) partitions the data points in a feature-wise fashion.
Therefore, this simple trick has significantly simplified the implementation
of trees and at the same time also improved the efficiency. In addition, it
also makes it convenient for parallelizing tree models.

  * •

Li (2010) derived the explicit (and robust) formula for tree-split criterion
using the second-order gain information (i.e., the so-called “Robust
LogitBoost”), which typically improves the accuracy, compared to the
implementation based on the criterion of using only the first-order gain
information (Friedman, 2001). This formula for computing tree-split gain has
resolved the numerical issue in the original LogitBoost (Friedman et al.,
2000; Friedman, 2001; Friedman et al., 2008). This formula has been widely
used in practice and is the standard implementation in all major tree
platforms.

Another major progress is the so-called “adaptive base class boost” (ABC-
Boost) (Li, 2009, 2010) for multi-class classification by re-writing the
derivatives of the classical multi-class logistic regression loss function.
ABC-Boost often improves the accuracy of multi-class classification tasks, in
many cases substantially so.

In this paper, we develop integrity authentication schemes for “Robust
LogitBoost” (Li, 2010) and the code base uses the implementation of “Fast ABC-
Boost” (Li and Zhao, 2022).

###  1.2 Challenges and Goals

Signature embedding or watermarking has been widely studied in the deep
learning community (Uchida et al., 2017; Adi et al., 2018; Zhang et al., 2018;
Li et al., 2019b, a; Darvish Rouhani et al., 2019; Cao et al., 2021; Fan et
al., 2019; Le Merrer et al., 2020; Zhong et al., 2020; Yang et al., 2021; Lao
et al., 2022b, a). Many of these works embed a desired behavior into the
learned function by using backdoor techniques (Adi et al., 2018) or enforcing
a specific representation in a latent space (Darvish Rouhani et al., 2019).
However, similar techniques are not readily available for tree models in order
to facilitate effective signature embedding, e.g., backdoor on tree models
entails little study in the literature. In addition, tree models have
different architectures and applications from deep neural networks, which also
demands careful customization of tree model signature embedding.

In general, it is not straightforward to directly apply the signature
embedding process of deep learning to tree models. We summarize the key
challenges as follows:

  * •

Deep learning methods require gradients. However, tree models are not
differentiable.

  * •

Many deep learning signature embedding algorithms require to retrain the
network. In the context of boosted tree models, each training iteration
constructs a new tree that attempts to correct the misclassifications of
previous trees. Appending more trees not only increases the model size (to
store additional trees) but also damages the inference performance (to
evaluate additional trees).

  * •

Meanwhile, retraining tree models by only replacing a subset of existing trees
is still an open research direction since each tree is generated on the
classification results of the previous trees—eliminating previous trees
invalidates the boosting dependency. As a result, it is impractical to inplace
retrain the tree models.

Therefore, this paper designs a new signature embedding framework for non-
differentiable and non-inplace-retrainable tree models. We target to have a
signature embedding framework to “sign” a trained tree model. After
distributing the model to the host services, we are able to remotely access
the model in a black-box fashion: we can query the model with several secret
inputs (we call them signature keys) and verify its output predictions. We
have three main objectives: (i) The signature embedding procedure should be
able to generate a vast number of distinct signs for different model host
services. (ii) The signature can verify the integrity of the model that has
not been tampered with. Whenever the model host modified the model, the output
predictions of signature keys should be changed, i.e., the signature should be
fragile against malicious modifications. (iii) The signature embedding
algorithm should not degrade the model prediction accuracy.

###  1.3 Summary of Contributions

We summarize our contributions as follows:

  * •

We introduce a novel model authentication framework and signature embedding
algorithm for tree models. As far as we know, this is the first study that
investigates model authentication on tree models.

  * •

We propose a novel searching and selection algorithm to generate signature
keys and manipulate tree models.

  * •

We empirically evaluate the proposed algorithm on various public datasets. The
results confirm the effectiveness and high authentication rate of our methods.

  * •

Since this paper is the first work to investigate signature embedding on tree
models, we design baseline attacks to assess the quality of our technique,
which also provides qualitative and quantitative metrics and comparisons for
future tree model protection methods.

Organization. In the rest of the paper, we introduce our authentication
framework in Section 2 and present the signature embedding process in Section
3. Section 4 reports the experimental evaluation. We present remarks and
conclude this paper in Section 5.

##  2 Authentication Framework

In this section, we first present the threat model for the signature embedding
process. Then we describe the workflow of the signature enrollment and
authentication.

###  2.1 Threat Model

The signature embedding process can be conducted by the model builder or a
trusted party. Without loss of generality, we assume a pre-trained model could
be received from a model builder who builds the model architecture and
corresponding parameters with the training dataset, and a held-out validation
dataset for evaluating the performance. We then apply the proposed methodology
to this tree model to embed a desired signature. Only the legitimate model
owner will have knowledge of the signature and the corresponding signature
keys. In the authentication process, the model owner can verify the presence
of the signature by using the signature keys via the prediction API—the model
owner only needs access to the predicted class during the authentication.
Thus, memorizing the tree weight hashing value or the predicted probability of
some inputs may not be applicable.

For signature embedding on DNNs, transformation attacks such as model
compression, model fine-tuning, and signature overwriting are often used to
evaluate the performance of an embedded signature. Since this paper is the
first work to investigate signature embedding on tree models, we design
similar transformation attacks as a baseline countermeasure to assess the
quality of our proposed technique, which also provides qualitative and
quantitative metrics and comparisons for future tree model protection methods.
Note that the target of this work is a fragile signature, which could verify
if a tree model has been tampered with and serve as a proactive defense
against malicious model modifications, similar to Lao et al. (2022b). In other
words, the objective of this signature is integrity verification as opposed to
IP tracing as in some of prior DNN watermarking and fingerprinting methods
(Darvish Rouhani et al., 2019; Adi et al., 2018; Cao et al., 2021; He et al.,
2019; Yang et al., 2021; Lao et al., 2022a). Thus, we expect the embedded
signatures to disappear after transformation attacks. Please also note that
ambiguity attack is not a concern for fragile signature, as similarly laid out
in Lao et al. (2022b).

###  2.2 Flow of Enrollment and Authentication

We formally express our proposed scheme as two phases:

  * •

Signature embedding $R^{\textit{msg}}\leftarrow\mbox{\bf
Embed}(R,\textit{msg})$ that generates a signed version of regression trees
$R^{\textit{msg}}$, signature key key from the given original regression trees
$R$ with a target signature message msg.

  * •

Signature extraction $\textit{msg}^{\prime}\leftarrow\mbox{\bf
Extract}(R^{\textit{msg}},\textit{key})$ that collects the signature message
$\textit{msg}^{\prime}$ using key from the given regression trees
$R^{\textit{msg}}$. The generated $\textit{msg}^{\prime}$ will then be used
for authentication.

Figure 1: Signature enrollment and authentication workflow.

Figure 1 presents a visual illustration of the signature enrollment and
authentication workflow. Built upon the proposed signature embedding
technique, an authentication process can be established. After successfully
embedding the signatures, the signature key and the correct signature message
are stored on a secure server. We can also choose to register the information
of model ID during the enrollment to enable authentication for multiple
legitimate users. In this case, each version of the model needs to be
generated by applying the proposed technique with a different set of the
signature key and signature message. Then, the model builder will sell,
distribute, or deploy the model. Each customer may receive a different version
of the original tree model (i.e., with a different signature). Later, when an
authentication process is initiated, based on the model ID if it is enrolled,
the server sends the signature key to the model API and collects the
corresponding response. The server determines the authenticity of the unknown
model by checking how this response matches the stored signature message.
Thus, another advantage of this method is its small computational and
communication overhead: only one authentication process, especially when
comparing to those countermeasures that require periodically checking the
accuracy (Muñoz-González et al., 2017; Yang et al., 2017). We focus on the
steps of embedding signatures on tree models in this paper. Modern
authentication techniques and protocols (Majzoobi et al., 2012; Lee et al.,
2014; Alamr et al., 2018) can be implemented on top of the generated
signatures.

##  3 Signature Embedding

In this section, we begin with a brief introduction of boosted tree models as
a preliminary. Then we present the proposed two-stage algorithm to embed
signatures: 1) locating the signature key candidates; 2) selecting independent
signature keys and manipulating the prediction value on the terminal nodes.

###  3.1 Boosted Tree Models: MART and Robust LogitBoost

We denote a training dataset by $\\{y_{i},\mathbf{x}_{i}\\}_{i=1}^{N}$, where
$N$ is the number of training samples, $\mathbf{x}_{i}$ is the $i$-th feature
vector, and $y_{i}\in\\{1,2,...,K\\}$ is the $i$-th class label, where $K\geq
3$ in multi-class classification. We consider the same framework as in
LogitBoost (Friedman et al., 2000) and MART (multiple additive regression
trees) (Friedman, 2001), which can be viewed as generalizations to logistic
regression and assume the class probabilities $p_{i,k}$ to be:

$\displaystyle
p_{i,k}=\mathbf{Pr}\left(y_{i}=k|\mathbf{x}_{i}\right)=\frac{e^{F_{i,k}(\mathbf{x_{i}})}}{\sum_{s=1}^{K}e^{F_{i,s}(\mathbf{x_{i}})}},\hskip
14.45377pti=1,2,...,N,$ (3)

where $F_{i,k}(\mathbf{x}_{i})$ is an additive model of $M$ terms:

$\displaystyle
F^{(M)}(\mathbf{x})=\sum_{m=1}^{M}\rho_{m}h(\mathbf{x};\mathbf{a}_{m}),$ (4)

where $h(\mathbf{x};\mathbf{a}_{m})$ is typically a regression tree, and
$\rho_{m}$ and $\mathbf{a}_{m}$ are parameters learned from the data, by
minimizing the negative log-likelihood loss:

$\displaystyle L=\sum_{i=1}^{N}L_{i},\hskip
28.90755ptL_{i}=-\sum_{k=1}^{K}r_{i,k}\log p_{i,k}$ (5)

where $r_{i,k}=1$ if $y_{i}=k$ and $r_{i,k}=0$ otherwise. The optimization
procedures would need the derivatives of $L$ with respect to the function
values $F_{i,k}$. The classical multi-class logistic regression textbooks give

$\displaystyle\frac{\partial L_{i}}{\partial
F_{i,k}}=-\left(r_{i,k}-p_{i,k}\right),\hskip
36.135pt\frac{\partial^{2}L_{i}}{\partial
F_{i,k}^{2}}=p_{i,k}\left(1-p_{i,k}\right).$ (6)

1: $F_{i,k}=0$, $p_{i,k}=\frac{1}{K}$, $k=1$ to $K$, $i=1$ to $N$

2: for $m=1$ to $M$ do

3: for $k=1$ to $K$ do

4: $\left\\{R_{j,k,m}\right\\}_{j=1}^{J}=J$-terminal node regression tree from
$\\{r_{i,k}-p_{i,k},\ \ \mathbf{x}_{i}\\}_{i=1}^{N}$, with weights
$p_{i,k}(1-p_{i,k})$, using the tree split gain formula Eq. (7).

5: $\beta_{j,k,m}=\frac{K-1}{K}\frac{\sum_{\mathbf{x}_{i}\in
R_{j,k,m}}r_{i,k}-p_{i,k}}{\sum_{\mathbf{x}_{i}\in
R_{j,k,m}}\left(1-p_{i,k}\right)p_{i,k}}$

6: $f_{i,k}=\sum_{j=1}^{J}\beta_{j,k,m}1_{\mathbf{x}_{i}\in R_{j,k,m}}$,
$F_{i,k}=F_{i,k}+\nu f_{i,k}$

7: end for

8: $p_{i,k}=\exp(F_{i,k})/\sum_{s=1}^{K}\exp(F_{i,s})$

9: end for

Algorithm 1 Robust LogitBoost. MART is similar, with the only difference in
Line 4.

Algorithm 1 describes the details for Robust LogitBoost (Li, 2010). It fixes
the previously thought “numerical instability” problem in the original
LogitBoost paper (Friedman et al., 2000), as discussed in Friedman (2001);
Friedman et al. (2008). Robust LogitBoost (Li, 2010) uses the 2nd-order
formula in (7) for computing the gains when deciding the split points.

Given $N$ data points which are assumed to be sorted according to the
corresponding feature values. The tree-splitting procedure is to find the
index $s$, $1\leq s<N$, such that the weighted square error (SE) is reduced
the most if split at $s$. That is, we seek the $s$ to maximize

$\displaystyle Gain(s)=$
$\displaystyle\frac{\left[\sum_{i=1}^{s}\left(r_{i,k}-p_{i,k}\right)\right]^{2}}{\sum_{i=1}^{s}p_{i,k}(1-p_{i,k})}+\frac{\left[\sum_{i=s+1}^{N}\left(r_{i,k}-p_{i,k}\right)\right]^{2}}{\sum_{i=s+1}^{N}p_{i,k}(1-p_{i,k})}-\frac{\left[\sum_{i=1}^{N}\left(r_{i,k}-p_{i,k}\right)\right]^{2}}{\sum_{i=1}^{N}p_{i,k}(1-p_{i,k})}.$
(7)

Because the computations involve $\sum p_{i,k}(1-p_{i,k})$ as a group, this
procedure is actually numerically stable. In the implementation, to avoid
occasional numerical issues, some “damping” could be added to the denominator,
i.e., $\left\\{\epsilon+\sum_{node}p_{i,k}(1-p_{i,k})\right\\}$.

In comparison, MART (Friedman, 2001) only used the first order information to
construct the trees, i.e.,

$\displaystyle MartGain(t)=$
$\displaystyle\frac{1}{s}\left[\sum_{i=1}^{s}\left(r_{i,k}-p_{i,k}\right)\right]^{2}+\frac{1}{N-s}\left[\sum_{i=s+1}^{N}\left(r_{i,k}-p_{i,k}\right)\right]^{2}-\frac{1}{N}\left[\sum_{i=1}^{N}\left(r_{i,k}-p_{i,k}\right)\right]^{2}.$
(8)

To avoid repetition, we do not provide the pseudo code for MART (Friedman,
2001), which is in fact almost identical to Algorithm 1. The only difference
is in Line 4, which for MART becomes

$\left\\{R_{j,k,m}\right\\}_{j=1}^{J}=J$-terminal node regression tree from
$\\{r_{i,k}-p_{i,k},\ \ \mathbf{x}_{i}\\}_{i=1}^{N}$,
using the tree split gain formula Eq. (8).

Inference. After the training, we obtain $K\times M$ regression trees
$f_{i,k}$ ($M$ trees for each class). In the inference, we just follow the
trained regression trees to obtain $f_{i,k}$. For each instance, it ends up at
a terminal node in the tree, and $f_{i,k}$ is the prediction value stored at
the node. We aggregate them to $F_{i,k}$ and apply a softmax over all classes
to compute the multi-class classification probability. Figure 2 depicts an
example: we have 3 classes and build the tree models for 2 iterations. For
each decision tree, the inference procedure follows the tree to a terminal
node. The prediction value for each class is aggregated across iterations and
then softmaxed to generate the probability.

Figure 2: Inference example for 2 iterations and 3 classes. For simplicity, we
assume the learning rate $\nu=1$. (In practice, we typically let $\nu\leq
0.1$.)

###  3.2 Signature Key Candidates Locating

As described in Section 2.2, our proposed authentication framework leverages a
collection of signature keys to check the embedded signature. Here a signature
key is a legit input of the model, e.g., an image for vision datasets. For a
subset of the signature keys, we manipulate the tree prediction value so that
their prediction flips to a new class other than the original one. On the
other hand, the manipulation must be carefully performed to preserve the model
functionality. Intuitively, the new class should be the second most likely
class of an input: We tend to have the key input whose highest class
prediction is close to its second-highest class. With $S$ signature keys, we
can generate $2^{S}$ unique signatures (by either using the original class or
flipping it to a new class).

Signature key locating problem. Recall that each internal node of the decision
trees represents a split condition, i.e., whether feature $x$ is greater than
$y$. For any terminal node (leaf node), we can extract the possible input
space to arrive at this node by intersecting the split conditions of its
ancestors. Thus, even without the training data, we can construct a valid
input space by searching the split conditions. Given $M\times K$ trees, we are
going to find $S$ distinct signature keys, such that the maximum gap for each
signature key is minimized, where the gap denotes the difference between the
largest $F_{i,k}$ and the second largest $F_{i,k^{\prime}}$ (class $k$ is the
original prediction and class $k^{\prime}$ is the class we are going to flip
to after embedding the signature).

This problem is, unfortunately, NP-Hard—we can straightforwardly reduce the
partition problem (Korf, 1998) to the signature key locating problem within
polynomial time. The good news is that we are not required to have the exact
best $S$ signature keys to make the signature embedding procedure work—as long
as the gap is sufficiently small, changing the prediction value on a terminal
node (i.e., flipping the prediction class) will not dramatically affect the
predictions for other test instances.

Algorithm 2 Signature Key Candidates Locating

Input: $M\times K$ decision trees $f_{i,k}$

Output: $S\times\alpha$ signature keys

1. initialize a global heap that stores the found best $S\times\alpha$ signature keys

2. for repeat $\leftarrow$ 1 to $S\times\alpha$ do

3. $\textit{cons}_{d}\leftarrow[0,+\infty)$ $\forall d\in[1..\textit{\\#Features}]$

4. Random-DFS(1,1,cons)

5. end for

Algorithm 3 Random-DFS

Input: current searching iteration $i$,

class $k$ and constraints cons
Output: a heap with updated signature keys

1. if $i>M$ then

2. if $k>K$ then

3. update signature key heap with cons

4. if reach max search step then

5. stop all Random-DFS

6. end if

7. return

8. else

9. return Random-DFS$(1,k+1,\textit{cons})$

10. end if

11. end if

12. for each terminal node $n$ of tree $f_{i,k}$ in random order do

13. if $\textit{cons}\cap\textit{condition}(n)\not=\emptyset$ then

14. Random-DFS$(i+1,k,\textit{cons}\cap\textit{condition}(n))$

15. end if

16. end for

Therefore, we introduce a heuristic random search algorithm to locate the
“sufficiently good” signature key candidates in Algorithm 2. We call them
candidates since they are not guaranteed to be independent—flipping one of
them may affect other keys. We introduce a selection procedure in Section 3.3
to generate the final signature keys from the candidate set. We have a scaling
factor $\alpha$ to generate sufficient candidates for the follow-up selection.
Algorithm 2 maintains a heap that stores the best key signatures (the ones
with the least gaps) found currently. Since tree models commonly quantize data
into natural numbers (Li et al., 2007), we assume all the data are non-
negative integers—all constraints are initialized to $[0,+\infty)$ before each
search. The sub-procedure Algorithm 3 performs a depth-first search (DFS)
while considering all the terminal nodes in a random order (Line 12). When we
reach Line 3, any instance satisfies cons is a possible signature key. We
construct one instance from the constraints, compute its gap, and insert it
into the heap. Whenever we reach Line 3, a search counter increments. The
algorithm keeps refining the searched local potential signature keys and
terminates when the search counter hits a preset max search step e.g., 1,000.

It is important to note that our algorithm does not require any training
data—we only search on the constructed trees.

###  3.3 Signature Key Selection

After obtaining $S\times\alpha$ signature key candidates, we are required to
select $S$ independent signature keys. The definition of the “independence” is
as follows:

######  Definition 3.1.

Given a collection of instances, they are independent if and only if: for each
instance, there exists a terminal node on its highest and second-highest
prediction classes such that the terminal node is not referenced by any other
instances in this collection.

Our signature embedding process will add a perturbation to the prediction
value on terminal nodes of the signature keys (details are presented in
Section 3.4). We can add the perturbation to the “independent” terminal node
on its highest or second-highest prediction class. In this case, the
perturbation will not affect the prediction result of other instances since no
other instance references this terminal node. The independence guarantees that
we can pick any subset of the signature keys as the signature message
independently—the prediction class flip of one chosen signature key does not
affect others.

Figure 3: An example for signature key selection.

Figure 3 depicts an example for the signature key selection. We have 3
signature key candidate instances represented in 3 colors in the example.
Flipping class 3 or class 1 for the green instance may change the prediction
value of other instances. Thus, the collection of red, blue, and green
signature candidates are not independent. However, we can choose a subset of
instances to form a collection of independent signature keys: Here we can
manipulate the prediction value of the $3^{\textit{rd}}$ terminal node on the
(iter 1, class 2) tree to flip the prediction of the red instance and
manipulate the prediction value of the $2^{\textit{nd}}$ terminal node on the
(iter 2, class 1) tree to flip the blue candidate. The flipping of the red and
blue signature candidates does not affect any other instances.

However, maximizing the number of selected independent signature keys in a
collection is an NP-Hard problem—it is equivalent to the maximum independent
set problem (Cook, 1983). Since we just need a “reasonable” number of
independent signature keys to generate a sufficient number of key
combinations, a collection with $10$ to $20$ independent signature keys is
sufficient for practical authentication usage. We do not need to pursue an
optimal but time-consuming independent signature key selection process. Thus,
we propose a greedy algorithm to select the signature keys.

According to the independence definition, we construct a histogram ref_freq
that counts the frequency of all terminal nodes: how many signature key
candidates reference the node. As illustrated in Algorithm 4, we find the
terminal node that only has one referencing signature key candidate and is on
the highest or second-highest prediction class of the candidate instance. Then
we put this candidate into the final set of signature keys. Because the
terminal node is only referenced by this signature key, manipulating the
prediction value of this node does not affect other signature keys’ highest
and second-highest predicted classes.

Algorithm 4 Signature Key Selection

Input: $S\times\alpha$ signature key candidates

Output: $S$ signature keys

1. $\textit{selected}\leftarrow\emptyset$

2. for each terminal nodes $n$ do

3. if ref_freq[n] = 1 then

4. $c\leftarrow$ the signature key candidate referencing $n$

5. if $n\in$ the highest/second-highest prediction of $c$ then

6. if $|\textit{selected}|<S$ and $c$ is not selected then

7. $\textit{selected}\leftarrow\textit{selected}\cup\\{c\\}$

8. end if

9. end if

10. end if

11. end for

12. return selected

###  3.4 Node Prediction Value Manipulation

Now we have obtained $S$ independent signature keys. The signature key
candidate locating algorithm (Algorithm 2) tries to find an instance such that
its aggregated prediction values of the highest possible class ($F_{i,k}$) and
the second-highest class ($F_{i,k^{\prime}}$) are close. In order to flip the
prediction of a signature key without affecting other keys, we can simply add
the difference between $F_{i,k}$ and $F_{i,k^{\prime}}$ to the terminal node
whose ref_freq is $1$ and then add a small perturbation $\epsilon$, e.g.,
$10^{-5}$, onto the prediction value of the node to obtain a desired flipped
prediction. The small perturbation we added flips the order of the aggregated
prediction values of the highest and the second-highest class. In addition,
our independence constraint ensures that the perturbation does not affect the
prediction value for other signature keys. We assume the prediction value of
$F_{i,k}$ and $F_{i,k^{\prime}}$ are significantly greater than the $F$ values
of other classes. The assumption empirically holds for a well-trained
converged model. With this assumption, after we apply a small perturbation on
the prediction value of class $k$ and $k^{\prime}$, it should not make the
prediction values of them smaller than other classes. Therefore, we only
consider the terminal nodes on classes $k$ and $k^{\prime}$. This completes
the proposed signature embedding algorithm.

##  4 Experimental Evaluation

The objective of the experimental evaluation is to investigate the performance
of the proposed algorithm, based on Robust LogitBoost (Friedman et al., 2000;
Li, 2010; Li and Zhao, 2022). Specifically, we target to answer the following
questions:

  * •

How many signature keys can be generated in one pass?

  * •

How does the signature embedding procedure affect the model functionality,
i.e., test accuracy?

  * •

Is there any correlation among the generated signature keys?

  * •

How effective is the embedded signature in detecting malicious modification,
i.e., when the attacker adds/removes decision trees?

Implementation. We use the code base from (Li and Zhao, 2022). The code is
compiled with g++-5.4.0 enabling the “O3” optimization. We execute the
experiments on a single node server with one Intel Xeon Processor Intel(R)
Xeon(R) CPU E5-2660 v4 @ 2.00GHz and 128 GB of memory. The operating system is
Ubuntu 16.04.4 LTS 64-bit.

Datasets. We evaluate our proposed algorithm on $20$ public
datasets111https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/. See Table
1 for the dataset specifications.

Table 1: Dataset specifications. | #Train | #Test | #Class | #Dim
---|---|---|---|---
CIFAR10 | 50,000 | 10,000 | 10 | 3,072
connect4 | 54,045 | 13,512 | 3 | 126
covtype | 464,809 | 116,203 | 7 | 54
glass | 171 | 43 | 6 | 9
letter | 15,000 | 5,000 | 26 | 16
MNIST | 60,000 | 10,000 | 10 | 780
news20 | 15,935 | 3,993 | 20 | 62,061
pendigits | 7,494 | 3,498 | 10 | 16
poker | 25,010 | 1,000,000 | 10 | 10
protein | 17,766 | 6,621 | 3 | 357
satimage | 4,435 | 2,000 | 6 | 36
segment | 1,848 | 462 | 7 | 19
Sensorless | 48,509 | 10,000 | 11 | 48
SVHN | 73,257 | 26,032 | 10 | 3,072
svmguide2 | 312 | 79 | 3 | 20
svmguide4 | 300 | 312 | 6 | 10
usps | 7,291 | 2,007 | 10 | 256
acoustic | 78,823 | 19,705 | 3 | 50
vehicle | 676 | 170 | 4 | 18
vowel | 528 | 462 | 11 | 10

Table 2: The number of selected independent signature keys with $S=40$ candidates. The candidates are generated with $\alpha=8$ and $\textit{max search step}=1,000$ for each Random-DFS. $J$ is the number of terminal nodes for each tree and #Iteration is the number of training iterations (the number of trees for each class). #Iteration | 50 | 100 | 200
---|---|---|---
$J$ | 4 | 8 | 12 | 16 | 20 | 4 | 8 | 12 | 16 | 20 | 4 | 8 | 12 | 16 | 20
CIFAR10 | 21 | 40 | 40 | 40 | 40 | 33 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40
connect4 | 17 | 33 | 40 | 40 | 40 | 19 | 39 | 40 | 40 | 40 | 23 | 40 | 40 | 40 | 40
covtype | 23 | 37 | 39 | 40 | 40 | 30 | 40 | 40 | 40 | 40 | 27 | 40 | 40 | 40 | 39
glass | 23 | 36 | 37 | 35 | 35 | 22 | 33 | 36 | 39 | 39 | 32 | 33 | 28 | 35 | 35
letter | 38 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40
MNIST | 34 | 40 | 40 | 40 | 40 | 37 | 40 | 40 | 40 | 40 | 30 | 40 | 40 | 36 | 31
news20 | 38 | 39 | 40 | 40 | 40 | 40 | 40 | 37 | 40 | 40 | 28 | 40 | 40 | 35 | 30
pendigits | 23 | 35 | 40 | 40 | 40 | 28 | 37 | 39 | 40 | 40 | 36 | 40 | 40 | 33 | 33
poker | 9 | 24 | 21 | 35 | 38 | 14 | 31 | 34 | 40 | 40 | 25 | 38 | 40 | 39 | 38
protein | 15 | 23 | 21 | 38 | 40 | 23 | 24 | 28 | 28 | 40 | 10 | 35 | 40 | 40 | 31
satimage | 34 | 40 | 40 | 40 | 40 | 38 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40
segment | 33 | 35 | 38 | 40 | 38 | 37 | 39 | 40 | 40 | 34 | 31 | 37 | 40 | 40 | 38
Sensorless | 29 | 40 | 40 | 40 | 40 | 34 | 39 | 40 | 39 | 40 | 36 | 28 | 22 | 26 | 20
SVHN | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 28 | 40 | 40 | 40
svmguide2 | 19 | 35 | 39 | 39 | 39 | 26 | 37 | 29 | 40 | 25 | 27 | 38 | 23 | 31 | 14
svmguide4 | 24 | 32 | 37 | 40 | 40 | 26 | 32 | 40 | 40 | 39 | 31 | 37 | 39 | 26 | 30
usps | 37 | 38 | 40 | 40 | 40 | 32 | 36 | 40 | 40 | 40 | 29 | 40 | 34 | 39 | 38
acoustic | 20 | 33 | 39 | 39 | 40 | 29 | 39 | 40 | 40 | 40 | 37 | 40 | 40 | 40 | 40
vehicle | 21 | 40 | 40 | 40 | 40 | 20 | 39 | 40 | 40 | 40 | 25 | 40 | 40 | 40 | 40
vowel | 26 | 38 | 40 | 36 | 32 | 24 | 36 | 36 | 39 | 34 | 28 | 31 | 24 | 26 | 22

Hyperparameters. We use the code base of Robust LogitBoost from Li and Zhao
(2022). The model mainly has 3 hyperparameters: the number of terminal nodes
for each decision tree ($J$), the number of training iterations ($M$), and the
learning rate ($\nu$). The learning rate does not affect the structure of the
decision tree. Since our signature embedding algorithm does not depend on how
well the model is trained, we fix the learning rate as $0.1$ in the following
experiments. We enumerate the remaining two hyperparameters, i.e., $J$ and
#Iterations, to examine the performance of our algorithm.

###  4.1 Number of Independent Signature Keys

In Table 2, our signature key candidate size is $S=40$, and we perform
$S\times\alpha=40\times 8=320$ Random-DFS searching. When $J$ is sufficiently
large, it is easy to find the terminal node with only one referenced signature
key (Algorithm 4). In most cases, all candidates can be selected in the
procedure. When $J$ is small (e.g., $J=4$) and #Iteration is small (it is not
common in practice due to its inferior accuracy), since each candidate has to
select a terminal node from the limited choices, fewer nodes with $1$
referencing frequency can be found. The signature space (the number of unique
signatures) is exponential to the number of selected signature keys, i.e.,
$2^{x}$ where $x$ is the number of selected signature keys. As seen in Table
2, for most configurations, we can have more than $20$ selected independent
signature keys. With $20$ keys, the signature space goes beyond 1 million.
Even with the rare cases when $J$ is small and $50$ iterations, we have at
least $9$ independent signature keys—it yields more than $500$ unique
signatures and sufficient for real-world authentication applications.

Table 3: The effectiveness of searching factor $\alpha$ on balancing the signature key candidate searching time and the number of selected independent signature keys with $J=20$ and $50$ iterations. | Time (seconds) | #Selected keys
---|---|---
$\alpha$ | 1 | 2 | 4 | 8 | 1 | 2 | 4 | 8
CIFAR10 | 0.03 | 0.03 | 0.06 | 0.09 | 20 | 40 | 40 | 40
connect4 | 0.10 | 0.08 | 0.17 | 0.42 | 14 | 10 | 26 | 40
covtype | 0.39 | 0.49 | 1.25 | 2.32 | 22 | 40 | 40 | 40
glass | 1.79 | 3.07 | 5.80 | 10.85 | 18 | 24 | 35 | 35
letter | 2.26 | 5.18 | 10.62 | 21.87 | 23 | 36 | 40 | 40
MNIST | 0.03 | 0.04 | 0.06 | 0.11 | 18 | 24 | 40 | 40
news20 | 0.12 | 0.14 | 0.19 | 0.35 | 21 | 30 | 40 | 40
pendigits | 0.52 | 1.07 | 2.28 | 4.13 | 18 | 24 | 34 | 40
poker | 0.87 | 1.94 | 4.14 | 10.88 | 31 | 37 | 37 | 38
protein | 0.01 | 0.02 | 0.07 | 0.09 | 10 | 20 | 37 | 40
satimage | 0.40 | 0.71 | 1.25 | 2.60 | 20 | 24 | 40 | 40
segment | 1.33 | 2.30 | 4.42 | 8.09 | 10 | 15 | 31 | 38
Sensorless | 0.87 | 1.30 | 1.80 | 3.76 | 14 | 15 | 26 | 40
SVHN | 0.02 | 0.04 | 0.08 | 0.14 | 18 | 26 | 40 | 40
svmguide2 | 0.16 | 0.49 | 0.77 | 2.09 | 10 | 21 | 31 | 39
svmguide4 | 1.73 | 2.91 | 5.47 | 10.45 | 11 | 22 | 39 | 40
usps | 0.11 | 0.21 | 0.21 | 0.39 | 40 | 30 | 38 | 40
acoustic | 0.07 | 0.09 | 0.17 | 0.41 | 17 | 24 | 40 | 40
vehicle | 0.38 | 0.69 | 1.35 | 2.14 | 13 | 23 | 40 | 40
vowel | 1.83 | 4.18 | 6.06 | 13.82 | 9 | 8 | 11 | 32

###  4.2 Searching Factor $\alpha$

The searching factor $\alpha$ balances the signature key candidate searching
time and the number of selected independent signature keys. With a larger
$\alpha$, we achieve more candidates at the cost of searching time. Table 3
shows that the searching time is almost linear to $\alpha$. As expected, the
number of selected independent signature keys increases when we use a larger
$\alpha$ factor. $\alpha=8$ is sufficient for most datasets to generate enough
signature keys. Since our signature key candidate searching only touches on
the decision trees of the trained model, neither training nor testing data are
required in the authentication workflow. As a result, the signature key
candidate searching is very efficient (regardless of the size of the
training/testing data). The execution time for most datasets is around only
one second. For the data with more classes, Gradient Boosting Machine
generates more trees (it works in a one versus all multi-class classification
fashion). Therefore, the letter dataset with $26$ classes takes the most
searching time. Because the searching only takes sub-minute time, users are
free to increase $\alpha$ to obtain more independent signature keys for a
larger signature space.

###  4.3 Model Functionality

Now we have obtained the signature keys. Our target is to embed these
signatures without dramatically changing the model functionality, i.e.,
prediction accuracy. Table 4 presents the number of changed predictions after
we embed all 20 signatures (by manipulating the prediction values on terminal
nodes and flipping all the prediction classes of 20 signature keys). The
prediction change is minimal $(0\%-0.08\%)$ on all datasets in the
experiments. Although our independent signature key selection ensures that one
manipulated prediction value on a terminal node is only referenced by one
signature key, the instance in the test dataset may touch multiple manipulated
terminal nodes. The aggregated small perturbation may flip the prediction for
some “sensitive” test instance (whose highest prediction class is very close
to its second-highest prediction class). As shown in the experiment result,
this aggregated flipping is very uncommon because our perturbation is small—at
most $0.08\%$ prediction values are changed for test datasets. Therefore, we
can conclude that our proposed signature embedding algorithm preserves the
original model functionality.

Table 4: The number of changed predictions on test datasets with $J=20$ and $\alpha=8$ embedded signatures. #Iteration | 50 | 100 | 200
---|---|---|---
CIFAR10 | 0/10,000 | 3/10,000 | 1/10,000
connect4 | 8/13,512 | 8/13,512 | 3/13,512
covtype | 4/116,203 | 1/116,203 | 101/116,203
glass | 0/43 | 0/43 | 0/43
letter | 1/5,000 | 0/5,000 | 0/5,000
MNIST | 0/10,000 | 0/10,000 | 0/10,000
news20 | 0/3,993 | 0/3,993 | 0/3,993
pendigits | 0/3,498 | 0/3,498 | 0/3,498
poker | 9/1,000,000 | 4/1,000,000 | 16/1,000,000
protein | 9/6,621 | 2/6,621 | 3/6,621
satimage | 1/2,000 | 1/2,000 | 1/2,000
segment | 0/462 | 0/462 | 0/462
Sensorless | 0/10,000 | 0/10,000 | 0/10,000
SVHN | 2/26,032 | 1/26,032 | 11/26,032
svmguide2 | 0/79 | 0/79 | 0/79
svmguide4 | 0/312 | 0/312 | 0/312
usps | 0/2,007 | 1/2,007 | 0/2,007
acoustic | 0/19,705 | 6/19,705 | 1/19,705
vehicle | 0/170 | 0/170 | 0/170
vowel | 1/462 | 0/462 | 0/462

###  4.4 Attacking

At this moment, we have tested the signature key generation algorithm and the
embedding procedure—the proposed technique can embed signatures into tree
models without noticeable performance degradation. Here we present two
possible attacks to verify the fragility of the signatures: we desire to
detect unauthorized modification to the model so that the signature should be
destroyed when the model is attacked. Due to the space limit, we only report
the attacking result on $5$ popular datasets (CIFAR10, letter, MNIST,
pendigits, and poker). The attacking results on other datasets show a similar
trend and thus are omitted.

Table 5: The percentage of the signature key outputs change when appending more training iterations on CIFAR10, letter, MNIST, pendigits, and poker with $J=20$. | #Signed iterations | #Appended iterations
---|---|---
| 1 | 5 | 10
CIFAR10 | 50 | 65% | 50% | 50%
100 | 30% | 55% | 50%
200 | 45% | 45% | 45%
letter | 50 | 40% | 55% | 60%
100 | 40% | 65% | 45%
200 | 40% | 40% | 55%
MNIST | 50 | 60% | 55% | 50%
100 | 30% | 50% | 25%
200 | 60% | 35% | 50%
pendigits | 50 | 70% | 50% | 40%
100 | 70% | 50% | 65%
200 | 50% | 35% | 30%
poker | 50 | 45% | 45% | 35%
100 | 60% | 40% | 55%
200 | 40% | 65% | 60%

Attack 1: Adding more training iterations. One possible attack is to continue
training the model by adding more training iterations to the model. This
attack appends more trees to the original model. From Table 5, we observe that
even appending one iteration to the original model can destroy more than
$30\%$ signatures in the original model. Adding even one iteration will “fix”
the flipping introduced in our signature embedding procedure—it changes the
prediction of signature keys to their original predictions. On the other hand,
when we embed the signatures to the model with 50 iterations, more than 50%
flipped predictions are lost in the retraining. We can enforce a subset of
signature keys to be embedded and vary the remaining keys to generate unique
signatures. Therefore, the appending tree modification can be captured in our
authentication framework.

Attack 2: Removing trees. The other attack we consider is removing the trees
in the last several iterations. Because each iteration of the tree model is
constructed based on all its previous trees, removing a tree from the model
invalidates all the trees generated in its following iterations and destroys
the prediction. Hence, we only consider the attack by removing the trees in
the last several iterations. Table 6 reports the signature key prediction
changes. Similar to Attack 1, this attack also destroys most of the flipped
predictions for signature keys (from 35% to 70%). We can conclude that our
signature is also fragile to this attack. Thus, malicious modifications can be
effectively detected.

Authentication. Since our authentication workflow checks if the extracted
signature message equals the original encoded signature, in both attacks we
tested above, more than $30\%$ signature messages are changed. Our
authentication framework is able to successfully detect those attacks for all
tested cases.

Table 6: The percentage of the signature key outputs change when removing the last training iterations on CIFAR10, letter, MNIST, pendigits, and poker with $J=20$. | #Signed iterations | #Removed iterations
---|---|---
| 1 | 5 | 10
CIFAR10 | 50 | 65% | 60% | 65%
100 | 50% | 55% | 55%
200 | 50% | 40% | 40%
letter | 50 | 55% | 55% | 40%
100 | 55% | 55% | 55%
200 | 50% | 55% | 60%
MNIST | 50 | 55% | 55% | 40%
100 | 50% | 60% | 65%
200 | 35% | 50% | 40%
pendigits | 50 | 60% | 40% | 50%
100 | 55% | 55% | 55%
200 | 75% | 70% | 70%
poker | 50 | 45% | 40% | 40%
100 | 50% | 70% | 60%
200 | 75% | 70% | 70%

###  4.5 Discussion

We can answer the questions that drove the experimental evaluation now: In one
pass of our signature key searching algorithm, we can obtain more than $20$
independent signature keys for most datasets on most configurations. When $J$
is small and the number of iterations is limited, we may have fewer
independent signatures for some datasets. However, the generated signature
keys with $\alpha=8$ are sufficient for practical use. The signature key
searching is very efficient—it only takes several seconds for most scenarios.
The signature embedding procedure has minimal impact on model functionality.
For most datasets, only a small number of predictions ($<10$) are changed. In
the percentage view, $0\%-0.08\%$ predictions are changed for all datasets.
For malicious attacking, we consider two possible attacks: the attacker
removes some trees or appends some trees by training more iterations. In both
attack scenarios, our authentication framework can successfully detect those
changes—because the embedded signatures are changed even with adding or
removing one iteration of decision trees.

##  5 Conclusion

In this paper, we introduce a novel model authentication framework and
signature embedding algorithm for tree models. We propose a (largely)
heuristic searching and selection algorithm to generate signature keys and
manipulate tree models. We evaluate the proposed method on 20 public datasets.
Experiments demonstrate that our proposed algorithm can efficiently locate
signature keys in a few seconds. The signature embedding minimally affects the
model functionality—the accuracy change is within $0.08\%$ for all tested
datasets and within $0.03\%$ for most cases. As a fragile signature for model
authentication, the empirical results confirm that adding/removing even a
small number of trees to the model will destroy the embedded signatures. In
summary, the generated signature by our proposed method is an effective tool
for ensuring the integrity of a deployed model that has not been tampered
with.

## References

  * Adi et al. [2018] Yossi Adi, Carsten Baum, Moustapha Cissé, Benny Pinkas, and Joseph Keshet.  Turning your weakness into a strength: Watermarking deep neural networks by backdooring.  In _Proceedings of the 27th USENIX Security Symposium (USENIX Security)_ , pages 1615–1631, Baltimore, MD, 2018.
  * Alamr et al. [2018] Amjad Ali Alamr, Firdous Kausar, Jongsung Kim, and Changho Seo.  A secure ecc-based rfid mutual authentication protocol for internet of things.  _The Journal of Supercomputing_ , 74(9):4281–4294, 2018.
  * Andriushchenko and Hein [2019] Maksym Andriushchenko and Matthias Hein.  Provably robust boosted decision stumps and trees against adversarial attacks.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 12997–13008, Vancouver, Canada, 2019.
  * Bartlett et al. [1998] Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert E. Schapire.  Boosting the margin: a new explanation for the effectiveness of voting methods.  _The Annals of Statistics_ , 26(5):1651–1686, 1998.
  * Biggio et al. [2012] Battista Biggio, Blaine Nelson, and Pavel Laskov.  Poisoning attacks against support vector machines.  In _Proceedings of the 29th International Conference on Machine Learning (ICML)_ , Edinburgh, Scotland, UK, 2012.
  * Biggio et al. [2018] Battista Biggio, Ignazio Pillai, Samuel Rota Bulò, Davide Ariu, Marcello Pelillo, and Fabio Roli.  Is data clustering in adversarial settings secure?  _arXiv preprint arXiv:1811.09982_ , 2018.
  * Breiman [1996] Leo Breiman.  Bagging predictors.  _Mach. Learn._ , 24(2):123–140, 1996.
  * Brieman et al. [1983] Leo Brieman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone.  _Classification and Regression Trees_.  Wadsworth, Belmont, CA, 1983.
  * Cao et al. [2021] Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong.  Ipguard: Protecting intellectual property of deep neural networks via fingerprinting the classification boundary.  In _Proceedings of the ACM Asia Conference on Computer and Communications Security (ASIA CCS)_ , pages 14–25, Virtual Event, Hong Kong, 2021.
  * Chen et al. [2019] Hongge Chen, Huan Zhang, Duane S. Boning, and Cho-Jui Hsieh.  Robust decision trees against adversarial examples.  In _Proceedings of the 36th International Conference on Machine Learning (ICML)_ , pages 1122–1131, Long Beach, CA, 2019.
  * Chen et al. [2017] Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song.  Targeted backdoor attacks on deep learning systems using data poisoning.  _arXiv preprint arXiv:1712.05526_ , 2017.
  * Cook [1983] Stephen A. Cook.  An overview of computational complexity.  _Commun. ACM_ , 26(6):400–408, 1983.
  * Darvish Rouhani et al. [2019] Bita Darvish Rouhani, Huili Chen, and Farinaz Koushanfar.  DeepSigns: an end-to-end watermarking framework for ownership protection of deep neural networks.  In _Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)_ , pages 485–497, Providence, RI, 2019.
  * Doan et al. [2021a] Khoa Doan, Yingjie Lao, and Ping Li.  Backdoor attack with imperceptible input and latent modification.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 18944–18957, virtual, 2021a.
  * Doan et al. [2021b] Khoa Doan, Yingjie Lao, Weijie Zhao, and Ping Li.  LIRA: learnable, imperceptible and robust backdoor attacks.  In _Proceedings of the 2021 IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 11946–11956, Montreal, Canada, 2021b.
  * Fan and Li [2020] Chenglin Fan and Ping Li.  Classification acceleration via merging decision trees.  In _Proceedings of the ACM-IMS Foundations of Data Science Conference (FODS)_ , pages 13–22, Virtual Event, 2020.
  * Fan et al. [2019] Lixin Fan, Kam Woh Ng, and Chee Seng Chan.  Rethinking deep neural network ownership verification: Embedding passports to defeat ambiguity attacks.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 4714–4723, Vancouver, Canada, 2019.
  * Freund [1995] Yoav Freund.  Boosting a weak learning algorithm by majority.  _Inf. Comput._ , 121(2):256–285, 1995.
  * Freund and Schapire [1997] Yoav Freund and Robert E. Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  _J. Comput. Syst. Sci._ , 55(1):119–139, 1997\.
  * Friedman [2001] Jerome H. Friedman.  Greedy function approximation: A gradient boosting machine.  _The Annals of Statistics_ , 29(5):1189–1232, 2001.
  * Friedman et al. [2000] Jerome H. Friedman, Trevor J. Hastie, and Robert Tibshirani.  Additive logistic regression: a statistical view of boosting.  _The Annals of Statistics_ , 28(2):337–407, 2000\.
  * Friedman et al. [2008] Jerome H. Friedman, Trevor J. Hastie, and Robert Tibshirani.  Response to evidence contrary to the statistical view of boosting.  _Journal of Machine Learning Research_ , 9:175–180, 2008\.
  * Grari et al. [2020] Vincent Grari, Boris Ruf, Sylvain Lamprier, and Marcin Detyniecki.  Achieving fairness with decision trees: An adversarial approach.  _Data Science and Engineering_ , 5:99–110, 2020.
  * Gu et al. [2017] Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg.  Badnets: Identifying vulnerabilities in the machine learning model supply chain.  _arXiv preprint arXiv:1708.06733_ , 2017.
  * Gu et al. [2019] Tianyu Gu, Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg.  Badnets: Evaluating backdooring attacks on deep neural networks.  _IEEE Access_ , 7:47230–47244, 2019.
  * He et al. [2019] Zecheng He, Tianwei Zhang, and Ruby Lee.  Sensitive-sample fingerprinting of deep neural networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 4729–4737, Long Beach, CA, 2019.
  * Hu et al. [2019] Xing Hu, Ling Liang, Lei Deng, Shuangchen Li, Xinfeng Xie, Yu Ji, Yufei Ding, Chang Liu, Timothy Sherwood, and Yuan Xie.  Neural network model extraction attacks in edge devices by hearing architectural hints.  _arXiv preprint arXiv:1903.03916_ , 2019.
  * Hua et al. [2018] Weizhe Hua, Zhiru Zhang, and G. Edward Suh.  Reverse engineering convolutional neural networks through side-channel information leaks.  In _Proceedings of the 55th Annual Design Automation Conference (DAC)_ , pages 4:1–4:6, San Francisco, CA, 2018.
  * Juuti et al. [2019] Mika Juuti, Sebastian Szyller, Samuel Marchal, and N. Asokan.  PRADA: protecting against DNN model stealing attacks.  In _Proceedings of the IEEE European Symposium on Security and Privacy (EuroS &P)_, pages 512–527, Stockholm, Sweden, 2019.
  * Korf [1998] Richard E Korf.  A complete anytime algorithm for number partitioning.  _Artificial Intelligence_ , 106(2):181–203, 1998\.
  * Kurakin et al. [2017] Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio.  Adversarial machine learning at scale.  In _Proceedings of the 5th International Conference on Learning Representations (ICLR)_ , Toulon, France, 2017.
  * Lao et al. [2022a] Yingjie Lao, Peng Yang, Weijie Zhao, and Ping Li.  Identification for deep neural network: Simply adjusting few weights!  In _Proceedings of the 38th IEEE International Conference on Data Engineering (ICDE)_ , Virtual Event, 2022a.
  * Lao et al. [2022b] Yingjie Lao, Weijie Zhao, Peng Yang, and Ping Li.  Deepauth: A dnn authentication framework by model-unique and fragile signature embedding.  In _Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI)_ , Virtual, 2022b.
  * Le Merrer et al. [2020] Erwan Le Merrer, Patrick Perez, and Gilles Trédan.  Adversarial frontier stitching for remote neural network watermarking.  _Neural Computing and Applications_ , 32(13):9233–9244, 2020.
  * Lee et al. [2014] Jun-Ya Lee, Wei-Cheng Lin, and Yu-Hung Huang.  A lightweight authentication protocol for internet of things.  In _Proceedings of the 2014 International Symposium on Next-Generation Electronics (ISNE)_ , pages 1–2, 2014.
  * Li et al. [2016] Bo Li, Yining Wang, Aarti Singh, and Yevgeniy Vorobeychik.  Data poisoning attacks on factorization-based collaborative filtering.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 1885–1893, Barcelona, Spain, 2016.
  * Li et al. [2019a] Huiying Li, Emily Willson, Haitao Zheng, and Ben Y Zhao.  Piracy resistant watermarks for deep neural networks.  _arXiv preprint arXiv:1910.01226_ , 2019a.
  * Li [2009] Ping Li.  Abc-boost: Adaptive base class boost for multi-class classification.  In _Proceedings of the 26th Annual International Conference on Machine Learning (ICML)_ , pages 625–632, Montreal, Canada, 2009.
  * Li [2010] Ping Li.  Robust logitboost and adaptive base class (abc) logitboost.  In _Proceedings of the Twenty-Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI)_ , pages 302–311, Catalina Island, CA, 2010.
  * Li and Zhao [2022] Ping Li and Weijie Zhao.  Fast ABC-Boost: A unified framework for selecting the base class in multi-class classification.  _arXiv preprint arXiv:2205.10927_ , 2022.
  * Li et al. [2007] Ping Li, Christopher J. C. Burges, and Qiang Wu.  Mcrank: Learning to rank using multiple classification and gradient boosting.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 897–904, Vancouver, Canada, 2007.
  * Li et al. [2019b] Zheng Li, Chengyu Hu, Yang Zhang, and Shanqing Guo.  How to prove your model belongs to you: a blind-watermark based framework to protect intellectual property of dnn.  In _Proceedings of the 35th Annual Computer Security Applications Conference (ACSAC)_ , pages 126–137, San Juan, PR, 2019b.
  * Liu et al. [2018a] Qiang Liu, Pan Li, Wentao Zhao, Wei Cai, Shui Yu, and Victor CM Leung.  A survey on security threats and defensive techniques of machine learning: a data driven view.  _IEEE Access_ , 6:12103–12117, 2018a.
  * Liu et al. [2018b] Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen-Chuan Lee, Juan Zhai, Weihang Wang, and Xiangyu Zhang.  Trojaning attack on neural networks.  In _Proceedings of the 25th Annual Network and Distributed System Security Symposium (NDSS)_ , San Diego, CA, 2018b.
  * Liu et al. [2017] Yuntao Liu, Yang Xie, and Ankur Srivastava.  Neural trojans.  In _Proceedings of the 2017 IEEE International Conference on Computer Design (ICCD)_ , pages 45–48, Boston, MA, 2017.
  * Majzoobi et al. [2012] Mehrdad Majzoobi, Masoud Rostami, Farinaz Koushanfar, Dan S Wallach, and Srinivas Devadas.  Slender PUF protocol: A lightweight, robust, and secure authentication by substring matching.  In _Proceedings of the 2012 IEEE Symposium on Security and Privacy Workshops_ , pages 33–44, San Francisco, CA, 2012.
  * Muñoz-González et al. [2017] Luis Muñoz-González, Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamee, Emil C. Lupu, and Fabio Roli.  Towards poisoning of deep learning algorithms with back-gradient optimization.  In _Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security (AISec@CCS)_ , pages 27–38, Dallas, TX, 2017.
  * Muñoz-González et al. [2019] Luis Muñoz-González, Bjarne Pfitzner, Matteo Russo, Javier Carnerero-Cano, and Emil C Lupu.  Poisoning attacks with generative adversarial nets.  _arXiv preprint arXiv:1906.07773_ , 2019.
  * Papernot et al. [2016] Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z Berkay Celik, and Ananthram Swami.  The limitations of deep learning in adversarial settings.  In _Proceedings of the 2016 IEEE European Symposium on Security and Privacy (Euro S &P)_, pages 372–387, Saarbrucken, Germany, 2016.
  * Saha et al. [2020] Aniruddha Saha, Akshayvarun Subramanya, and Hamed Pirsiavash.  Hidden trigger backdoor attacks.  In _Proceedings the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI)_ , pages 11957–11965, New York, NY, 2020.
  * Schapire [1990] Robert E. Schapire.  The strength of weak learnability.  _Machine Learning_ , 5(2):197–227, 1990.
  * Schapire and Singer [1999] Robert E. Schapire and Yoram Singer.  Improved boosting algorithms using confidence-rated predictions.  _Machine Learning_ , 37(3):297–336, 1999.
  * Shafahi et al. [2018] Ali Shafahi, W Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein.  Poison frogs! targeted clean-label poisoning attacks on neural networks.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 6103–6113, Montreal, Canada, 2018.
  * Steinhardt et al. [2017] Jacob Steinhardt, Pang Wei Koh, and Percy Liang.  Certified defenses for data poisoning attacks.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 3517–3529, 2017.
  * Szegedy et al. [2014] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  In _Proceedings of the 2nd International Conference on Learning Representations (ICLR)_ , Banff, Canada, 2014.
  * Turner et al. [2019] Alexander Turner, Dimitris Tsipras, and Aleksander Madry.  Label-consistent backdoor attacks.  _arXiv preprint arXiv:1912.02771_ , 2019.
  * Uchida et al. [2017] Yusuke Uchida, Yuki Nagai, Shigeyuki Sakazawa, and Shin’ichi Satoh.  Embedding watermarks into deep neural networks.  In _Proceedings of the 2017 ACM on International Conference on Multimedia Retrieval (ICMR)_ , pages 269–277, Bucharest, Romania, 2017.
  * Yang et al. [2017] Chaofei Yang, Qing Wu, Hai Li, and Yiran Chen.  Generative poisoning attack method against neural networks.  _arXiv preprint arXiv:1703.01340_ , 2017.
  * Yang et al. [2021] Peng Yang, Yingjie Lao, and Ping Li.  Robust watermarking for deep neural networks via bi-level optimization.  In _Proceedings of the 2021 IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 14821–14830, Montreal, Canada, 2021.
  * Yuan et al. [2019] Xiaoyong Yuan, Pan He, Qile Zhu, and Xiaolin Li.  Adversarial examples: Attacks and defenses for deep learning.  _IEEE Transactions on Neural Networks and Learning Systems_ , 30(9):2805–2824, 2019.
  * Zhang et al. [2020] Chong Zhang, Huan Zhang, and Cho-Jui Hsieh.  An efficient adversarial attack for tree ensembles.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , virtual, 2020.
  * Zhang et al. [2018] Jialong Zhang, Zhongshu Gu, Jiyong Jang, Hui Wu, Marc Ph. Stoecklin, Heqing Huang, and Ian M. Molloy.  Protecting intellectual property of deep neural networks with watermarking.  In _Proceedings of the 2018 Asia Conference on Computer and Communications Security (AsiaCCS)_ , pages 159–172, Incheon, Korea, 2018.
  * Zhong et al. [2020] Qi Zhong, Leo Yu Zhang, Jun Zhang, Longxiang Gao, and Yong Xiang.  Protecting IP of deep neural networks with watermarking: A new label helps.  In _Proceedings of the 24th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD), Part II_ , pages 462–474, Singapore, 2020.