arXiv:1708.03366v2 [cs.LG] 15 Aug 2017

Resilient Linear Classification: An Approach to Deal with
Attacks on Training Data
Sangdon Park

James Weimer

Insup Lee

Department of Computer &
Information Science
University of Pennsylvania
sangdonp@cis.upenn.edu

Department of Computer &
Information Science
University of Pennsylvania
weimerj@cis.upenn.edu

Department of Computer &
Information Science
University of Pennsylvania
lee@cis.upenn.edu

ABSTRACT
Data-driven techniques are used in cyber-physical systems (CPS) for
controlling autonomous vehicles, handling demand responses for
energy management, and modeling human physiology for medical
devices. These data-driven techniques extract models from training
data, where their performance is often analyzed with respect to
random errors in the training data. However, if the training data is
maliciously altered by attackers, the effect of these attacks on the
learning algorithms underpinning data-driven CPS have yet to be
considered. In this paper, we analyze the resilience of classification
algorithms to training data attacks. Specifically, a generic metric
is proposed that is tailored to measure resilience of classification
algorithms with respect to worst-case tampering of the training
data. Using the metric, we show that traditional linear classification
algorithms are resilient under restricted conditions. To overcome
these limitations, we propose a linear classification algorithm with
a majority constraint and prove that it is strictly more resilient than
the traditional algorithms. Evaluations on both synthetic data and a
real-world retrospective arrhythmia medical case-study show that
the traditional algorithms are vulnerable to tampered training data,
whereas the proposed algorithm is more resilient (as measured by
worst-case tampering).

CCS CONCEPTS
•Computing methodologies →Supervised learning by classification; Batch learning; •Computer systems organization
→Embedded and cyber-physical systems; •Security and privacy →Domain-specific security and privacy architectures;

KEYWORDS
cyber-physical systems, linear classification, training data attacks
ACM Reference format:
Sangdon Park, James Weimer, and Insup Lee. 2017. Resilient Linear Classification: An Approach to Deal with Attacks on Training Data. In Proceedings
of The 8th ACM/IEEE International Conference on Cyber-Physical Systems,
Pittsburgh, PA USA, April 2017 (ICCPS), 16 pages.
DOI: http://dx.doi.org/10.1145/3055004.3055006

1

INTRODUCTION

The penetration of data-driven techniques (e.g., machine learning)
to monitor and control a broad range of cyber-physical systems has
sharply increased. Autonomous cars rely on visual object detectors
ICCPS, Pittsburgh, PA USA
2017. 978-x-xxxx-xxxx-x/YY/MM. . . $$15.00
DOI: http://dx.doi.org/10.1145/3055004.3055006

learned from image data for recognizing objects[12, 25, 30]. Building demand response can be effectively handled by data-driven
modeling and prediction of the electric usage of buildings [33].
Smart insulin pumps can adapt to type 1 diabetic patients using
data-driven modeling of user-specific eating and pump-using behavior [13]. While data-driven CPS offer remarkable capabilities
for enhanced performance, they also introduce unprecedented security vulnerabilities with the risk of malicious attacks having
catastrophic consequences. Specifically, the training data used for
learning (be it online or offline), is vulnerable to malicious tampering that can result in data-driven CPS reacting incorrectly to
safety-critical events.
The training data for data-driven CPS can be tampered in several
ways, depending on the application. In modern automobiles, multiple vulnerabilities have been demonstrated where hackers obtain
full control of automobiles by eavesdropping a Controller Area Network (CAN) and injecting CAN messages [11, 29], which provides
possibilities to inject malicious data being used for online learning
algorithms [12, 25]. Furthermore, automobiles and robots, which
rely on sensor inputs from global positioning system (GPS), inertial
measurement unit (IMU) or wheel speed sensors, can be susceptible
on spoofing attacks [26, 42, 44]. This means attackers can tamper
training data collected from sensors. Hacking incidents on medical devices and hospitals [1–3] suggest attackers can tamper both
device-level and data center-level training data. Moreover, attackers
with knowledge of the underlying machine learning techniques –
e.g., support vector machines (SVMs), principal component analysis, logistic regression, artificial neural network, and (ensemble)
decision trees – can strategically alter the training data to minimize
the accuracy of the algorithms [6, 7, 23, 27, 34, 45], to maliciously
affect the performance of data-driven CPS [12, 13, 25, 33, 39, 41, 47].
Capabilities provided by traditional cyber defenses (e.g., communication channel encryption and authentication), fault tolerant
techniques (e.g., data sanitization [16], robust loss functions [50, 52],
and robust learning [14, 20]), and adversarial learning [9, 17, 19]
are necessary to secure data-driven CPS, but they are not sufficient.
Specifically, the cyber defenses are insufficient for defending against
cyber-physical attacks (e.g., GPS spoofing [26]) where a sensing
environment can be maliciously altered such that correctly functioning sensors and systems can act erroneously. These challenges are
compounded in dynamic applications (e.g., autonomous driving and
closed-loop physiological control) where accurate physical models,
commonly required for fault tolerant systems, are challenging to
obtain. Moreover, adversarial learning literature (e.g., [9, 17, 19])
usually assumes a known attacker behavior and/or goal – which

ICCPS, April 2017, Pittsburgh, PA USA
is likely unknown in complex CPS applications. Due to the shortcomings of traditional approaches for securing the training data of
data-driven CPS, it is necessary to consider techniques for resilient
machine learning that can defend against cyber-physical attacks
and make minimal assumptions on environments and attackers.
Towards the ultimate goal of attack-resilient machine learning,
we propose a resilience metric for the analysis and design of learning algorithms under cyber-physical attacks. The metric aims to
quantify the resilience of learning algorithms for analysis, which in
turn contributes to designing resilient learning algorithms. Specifically, this work considers binary linear classification algorithms in
the presence of maliciously tampered training data. Binary linear
classification represents a basic building block for more complex
classification approaches, such as neural network, decision trees,
and boosting; thus, developing attack resilient linear classifiers can
lead to more advance resilient machine learning algorithms. To
analyze binary classifiers in the presence of training data attacks,
we introduce a generic measure of resilience for classification in
terms of worst-case errors.
Based on the resilience metric, traditional linear classification
algorithms are evaluated. First, we prove the maximal resilience of
any linear classification algorithm, which provides an upper bound
of a resilience condition that can be achievable. Then, we prove
that convex loss linear classification algorithms, such as SVMs, and
0-1 loss linear classification algorithm can not achieve maximal
resilience. Based on these results, we introduce a majority 0-1 loss
linear classification algorithm that is strictly more resilient than
the traditional approaches and achieves the maximal resilience
condition.
Finally, we evaluate the different classification algorithms, in the
presence of attacks, on a synthetic dataset and a medical case-study,
introduced in [24], to design a detector for arrhythmia (i.e., irregular
heart beat). The evaluation on synthetic data illustrates conditions
when the different algorithms are (and are not) resilient, while the
arrhythmia dataset serves to illustrate resilient binary classification
in a real-world data-driven medical CPS (described in Section 7).
In summary, the contributions of this work include: (i) introducing, to our knowledge, the first assessment metric for analyzing binary classifier resilience; (ii) providing an analysis of the
resilience of traditional binary classification techniques illustrating their shortcomings; (iii) describing a resilient classification
approach that provides maximal resilience; (iv) evaluating in a
retrospective real-world arrhythmia classification case-study.
The following section describes the work most closely related to
the resilient classification problem considered herein. In Section 3,
we define attacker capabilities and a resilience metric. In Section 4,
the resilient classification problem is formally defined while an
analysis of traditional linear classification algorithms is provided in
Section 5. In Section 6, a new resilient linear classification algorithm
is proposed which achieves maximal resilience for the attacker’s
capabilities considered. Section 7 illustrates the theoretical results
using case studies on synthetic and medical data. The final section
provides conclusions with discussion about countermeasures and
future work.

Sangdon Park, James Weimer, and Insup Lee

2

RELATED WORK

This section presents the related works for CPS security (Section 2.1)
and traditional error/attack models in the machine learning literature (Section 2.2).

2.1

CPS security

Though the security of learning systems for data-driven CPS has
been an afterthought, the security of CPS has seen much effort in
the past decade. A mathematical framework considering attacks on
CPS is proposed in [10, 40]. The necessary and sufficient conditions
on CPS with a failure detector such that a stealthy attacker can
destabilize the system are provided in [35]. State estimation for
an electric power system is analyzed in [46] assuming attackers
know a partial model of the true system. Resilient state estimators
for CPS that tolerate a bounded number of sensors and/or actuators attacks are considered in [18, 38]. In mobility-as-a-Service
systems (e.g., ride-sharing services), it has been demonstrated that
a fraction of cars are maliciously called by fake reservation for
denial-of-service [51]. Surgical tele-operated robotic systems can
be affected by denial-of-service attacks on communication channels
[8]. Energy management systems, especially when connected to
building networks, are vulnerable to cyber attacks that impact on
the systems operation. This vulnerability can be attenuated by applying resilient policy when attacks are detected [39]. While there
has been much recent work on CPS security, these approaches are
(in general) not directly applicable to data-driven CPS.

2.2

Learning with Errors

In this subsection, we review the literature on learning in the presence of training data errors most closely related to our work, where
a more complete survey of the entire literature can be found in
[22, 36]. The error models can be categorized as either label errors
or feature errors in Table 1, according to their classical definitions
[22, 36]. Under each error model, the performance of a learning algorithm is analyzed against whether it achieves a desired classifier.
label errors

class-independent (CICE)
class-dependent (CDCE)

[4]
[36]

feature errors

uniform random (URAE)
product random (PRAE)
malicious errors (ME)

[43]
[22]
[28]

Table 1: Taxonomy of training data errors in the literature.
When labels in training data are corrupted, the training data
is said to have label errors, which can be divided into two subtypes: class-independent classification errors (CICE) [4] and classdependent classification errors (CDCE) [36]. The class-independent
classification error model assumes the error probability of positive
and negative labels are same while the class-dependent classification error model allows the different error probability for positive
and negative labels.
When features in the training data are corrupted, the training
data is said to have feature errors, which can be divided into three
subtypes: uniform random attribute errors [43], product random
attribute errors [22], and malicious errors [28]. Both the uniform
random attribute error (URAE) and the product random attribute
error (PRAE) models assume errors on features (i.e., columns of the
feature matrix), where URAE assumes the same error probability for

Resilient Linear Classification

ICCPS, April 2017, Pittsburgh, PA USA

all features and PRAE allows for variable error probabilities. From
a CPS perspective, attacks on individual features require that each
column of the feature matrix corresponds to a single attack surface
(e.g., a single sensor) – which restricts the use of multiple sensors in
a single feature, as common in data-driven CPS [12, 25]. Different
from URAE and PRAE, the malicious error (ME) model assumes
arbitrary attacks on feature vectors (i.e., rows of the feature matrix).
However, the ME model assumes the probabilities of attacking
the feature vectors corresponding to positive and negative labels
are the same – a condition which may not be satisfied by savvy
attackers. In contrast to this, our error (or attack) model assumes
the probabilities can be different.

3

SETUP FOR RESILIENT BINARY
CLASSIFICATION

This section introduces essential definitions that are the bases for
describing resilient binary classification problem. In the following
subsections, we present a traditional binary linear classification
problem (Section 3.1), define our attacker assumptions (Section 3.2),
and introduce a resilience metric (Section 3.3).
Notationally, we write R, R+
0 , N0 and [a, b] to denote the set
of real numbers, non-negative real numbers, non-negative integers, and integers from a to b, respectively. We write 1 as the
ones vector of an appropriate size and | · | to denote the cardinality (i.e., number of elements) of a finite set. The sign function is written as sign : R → {+1, −1} and 1{·} corresponds to
the indicator function that maps true and false to 1 and 0. Additionally, we write `01 to denote a 0-1 loss function, such that
`01 (yi , h(x i )) = 1 {yi , sign(h(x i ))}. Lastly, k · k1 and k · k∞ denotes the 1-norm and the ∞-norm, respectively. See Table 2 for the
glossary of mathematical notations in this paper.

3.1

symbol

description

D̂
D̂
D̂ +
D̂ −
Θ
α
D̂ α
D̂α
D̂ α+
D̂ α−
N
N
F
H
L
S
`
`c
`01
P
P F, S
P H, `
P L, S
P L, `c
P L, `01
P M, `01
дP
G
AP

actual training data
class of training data
positive training data
negative training data
set of attacker capability parameters
attacker capability parameter where α ∈ Θ
tapered training data
class of tampered training data
positive tampered training data
negative tampered training data
number of training data pairs (i.e., |D̂| )
pair of |D̂ + | and |D̂ − |
set of classifiers
subset of classifiers (i.e., H ⊆ F )
set of linear classifiers
set of loss functions
loss function in S
convex loss function in S
0-1 loss function in S
classification algorithm
class of classification algorithms
classification algorithm
class of linear classification algorithms
convex loss linear classification algorithm
0-1 loss linear classification algorithm
majority 0-1 loss linear classification algorithm
resilience bound of a classification algorithm P
set of resilience bounds
resilience attack condition of a classification algorithm P where A P ⊆ Θ
perfectly attackable condition of a classification
algorithm P where BP ⊆ Θ

Traditional Binary Classification

We begin by considering the traditional problem of binary classification in the absence of attacks (or errors). Namely, we consider
N ∈ D̂, where N is the
un-attacked training data D̂ = {(x i , yi )}i=1
number of training data pairs, D̂ = {D ⊂ X × Y | |D| = N } is a
class of training data with N pairs, X ⊆ Rp corresponds to a set
of feature vectors (or attributes), Y = {−1, +1} denotes the set of
labels (or classes), and each element of x i is called a feature. In a traditional (binary) classification problem, such as [49], given training
data, a designer specifies a set of (real-valued) classifiers H ⊆ R X ,
and a loss function ` : Y×R → R+
0 , to learn a (real-valued) classifier
ĥ ∈ H , according to
P H, ` (D̂) : ĥ = arg min kW · R̂ ` (h|D̂)k1 ,
h ∈H

(1)

where W ∈ R2×2 is the diagonal matrix with the positive risk
weight w + and the negative risk weight w − on the diagonal, and zeros elsewhere. R̂ ` (h| D̂) ∈ R2 denotes the bi-dimensional vector of
empirical risks corresponding to the positive and negative training

>
data. Specifically, we write R̂ ` (h| D̂) = R̂ ` (h|D̂ + ) R̂ ` (h| D̂ − ) ,
Í | D̂ |
where R̂ ` (h|D̂) = 1
i=1 `(yi , h(x i )) is the normalized empirical
| D̂ |

risk evaluated over the training data and D̂ + and D̂ − corresponds
to the mutually exclusive sets of positive and negative training data
pairs, respectively, such that D̂ = D̂ + ∪ D̂ − . We note that we use

BP

Table 2: The glossary of mathematical notations.

Equation (1) for distinguishing empirical risks over positive and negative training data, but it is equivalent to the standard notation [49]
if w + = | D̂ + | and w − = |D̂ − |, and we assume the standard notion in
this paper. Also, we call ĥ a classifier (i.e., ĥ ∈ Y X ) or a real-valued
classifier (i.e., ĥ 0 ∈ R X ), interchangeably, assuming the composition
of a sign function and a real-valued classifier (i.e., sign ◦ĥ 0 ∈ Y X )
is a classifier. Moreover, we say N is the number of training data
pairs or N = (| D̂ + |, | D̂ − |), interchangeably.
In this paper, we consider a set of classification algorithms P F, S ,
where F is a set of classifiers and S is the set of monotonically nonincreasing functions that are lower-bounded by a 0-1 loss function.
Specifically, the loss function `(y, h(x)) is represented as `(y, h(x))
= ϕ(t), where t = yh(x), ϕ is lower-bounded by 1 {t ≤ 0}, ϕ(0) = 1,
ϕ is a monotonically non-increasing function, and limt →∞ ϕ(t) = c
for some scalar c < 1. We note that these assumptions generalize a
convex loss [5] to cover a non-convex loss.
Each algorithm in P F, S is a map from a class of training data
D̂ to a subset of F that uses a loss function in S (i.e., P F, S ⊇

ICCPS, April 2017, Pittsburgh, PA USA

Sangdon Park, James Weimer, and Insup Lee

{P F, ` |F ⊆ F , ` ∈ S}). Thus, empirical risk minimization (Equation (1)) for any hypothesis space H ⊆ F and a loss function ` ∈ S
is also a classification algorithm considered here (i.e., P H, ` ∈ P F, S ).

3.2

Attacker Capabilities

In this work, we introduce a new class of an attack based on the
number of training data elements the attacker can manipulate,
referenced to as a bounded feature attack (BFA). Specifically, in
this class of an attack, we assume the attacker has the following
three capabilities; (i) The attacker knows the classification algorithm to be attacked, (ii) the attacker has unbounded computing
power, (iii) the attacker knows all the training data (both before
and after tampering), and (iv) the attacker can tamper the training
data. However, the ability to tamper the training data is limited
such that the tampered training data D̂ α differs from the original
training data D̂ by a finite number of elements. We parameterize
the tampered training data using an attacker capability parameter
α = (α + , α − ) ∈ Θ = [0, | D̂ + |] × [0, |D̂ − |] such that at most α + and
α − number of positive and negative feature vectors are maliciously
manipulated, respectively. Formally, the α-bounded feature attack
is defined as follows:
Definition 1 (bounded feature attack). Given P H, ` , D̂, and α, then
D̂ α is a bounded feature attack (BFA) if D̂ α ∈ D̂ satisfies the following two conditions:
(i) |D̂ α+ \D̂ + | ≤ α + , (ii) |D̂ α− \D̂ − | ≤ α − .

(2)

Additionally, let D̂α be the set of all such D̂ α (i.e., D̂ α ∈ D̂α ⊆ D̂).
We emphasize that Definition 1 only specifies what an attacker can
do and which information can be used – but does not indicate how
the attacker changes the data. This definition is consistent with the
attacker capability definition used in the CPS security literature
(e.g., [18, 38]). Moreover, α is unknown in general, so algorithms
considered in this paper do not assume anything on α.
The BFA represents a practical model of attacker capabilities. For
example, assume several devices collect medical data and store it
in the hospitals central data center. An attacker can exploit known
vulnerabilities of the enterprise system of the data center to gain
read access on all data (i.e., knows all data), but can only alter data
from specific devices having a certain vulnerabilities (i.e., attacks
some of the data). Here, we assume obtaining write access is more
difficult than obtaining read access.
In comparison to other attack models discussed in Section 2,
we emphasize that the proposed attacker capabilities are quite
general; we only limit the number of tampered feature vectors.
By definition, the BFA includes the ME; moreover, the BFA can
represent attacks on (maliciously) manipulating labels in training
data. This is achieved by manipulating a positive feature vector
into one of the negative feature vectors, which effectively switches
the label from positive to negative and suggests the BFA includes
the CICE and CDCE models.

3.3

Resilience Metric

To evaluate a classification algorithm in the presence of a BFA, we
aim to quantify the effect of a BFA on the learned classifier’s worstcase error metric over all training data and all possible attacks. In
traditional detection and classification theory, the true-positive and

true-negative rates (or the corresponding false-positive and falsenegative rates) are commonly used to evaluate the performance of
a classifier. We introduce a generic metric that utilizes the falsepositive and false-negative rates such that it measures the worstcase weighted p-norm of the two error rates over all training data
and all feasible attacks, defined as follows:
Definition 2 (resilience metric). Given N and α, the resilience of
P H, ` is quantified as the worst-case weighted p-norm of error rates
over all D̂ ∈ D̂ and D̂ α ∈ D̂α , stated as
VW ,p (P H, ` |N , α) = max W · R̂ `01 (P H, ` (D̂ α )|D̂)
D̂, D̂ α

p

.

(3)

This resilience metric measures the performance of a classification
algorithm (i.e., VW ,p (·)) in the presence of the worst-cast attack
given the attacker capability parameter α.
In this work, we select w + = w − = 1 and p = ∞. So, VW ,p (·)
ranges from zero to one and equals one if P H, ` outputs any classifier such that an attack could result in mis-classification of all
the positive or negative feature vectors in the un-attacked training
data D̂. For notational simplicity, we denote VW ,p (·) as V (·). Our
selection of w + = w − = 1 means each label is equally important to
model the unknown attacker’s preference for each label. The choice
of p = ∞ is motivated by the worst-case classification approach
that minimizes the maximum of class-conditional error rates [31].
We note that other norm measures could have been chosen rather
than the ∞-norm. For instance, selecting p = 1 results in evaluating
the 1-norm of the false-positive and false-negative rates, where
V (·) ≥ 1 implies that the classifier is at least as bad as a weighted
coin-flip (i.e., a trivial classifier) [48]. Additionally, selecting p = 2
specifies V (·) to be the Euclidean distance to the classifier error of
zero. In general, the selection of p in Equation (3) can vary based
upon the security concerns.
Applying the resilience metric in Equation (3), a binary classification algorithm P H, ` can be evaluated for given N and α. Furthermore, the resilience metric can be upper bounded by a function in
N and α, i.e., д(N , α) : (N0 × N0 × N0 ) → [0, 1] where G is the set
of all such д. Then, the upper bound characterizes the property of
an algorithm over various attack parameters. In this case, the classification algorithm is called a д(N , α)-resilient algorithm. Formally,
we define the resilience property of a classification algorithm in
the context of this work as follows.
Definition 3 (д(N , α)-resilience). A classification algorithm P is
д(N , α)-resilient to a BFA if
V (P |N , α) ≤ д(N , α),

(4)

where д ∈ G denotes the worst-case resilience bound.
This worst-case resilience bound plays a key role in defining resilient binary classification problem, which is defined in the following section.

4

PROBLEM FORMULATION

This section formulates the problem of analyzing (and ultimately
designing) resilient binary classification algorithms with respect
to training data attacks. Specifically, given the number of positive
and negative training data N , a set of classifiers F , a set of loss
functions S, and a class of algorithms P F, S , the goal of this paper

Resilient Linear Classification

ICCPS, April 2017, Pittsburgh, PA USA

is finding a classification algorithm P and a resilience bound д that
minimize the error of the resilience bound such that P is д(N , α)resilient to a BFA. Here, to measure the error of the resilience bound
we use the number of α that makes the resilience bound maximum
Í
(i.e., α ∈Θ 1{д(N , α) = 1}), but any other error measure can be
used. In short, a resilient binary classification problem is defined
as follows:
Problem (BFA resilient binary classification problem). Given N , F , S, and P F, S , a BFA resilient binary classification problem
is to find a classification algorithm P ∈ P F, S and a resilience bound
д ∈ G according to

1{д(N , α) = 1}

(5)

s.t. V (P |N , α) ≤ д(N , α), ∀α ∈ Θ.

(6)

(P, д) = arg min
P,д

Õ
α ∈Θ

We note several implications of the above problem. First, a feasible
classification algorithm of this problem guarantees the worst-case
performance characterized by д since the constraint of the problem
enforces that the worst-case error (i.e., V (·)) is bounded by д for all
possible attacks (i.e., ∀α). Next, the problem can consider the capabilities of classification algorithms by encoding prior knowledge
on the class of classification algorithms P F, S . Specifically, P F, S
can be the class of classification algorithms that uses empirical
risk minimization over F with convex loss functions. The resilient
classification problem then finds a classification algorithm in the
restricted class of P F, S . We note that when choosing the restricted
class of classification algorithms in this paper, we do not consider
the attacker capability parameter α, implying we focus on finding
an algorithm without assumptions on α. Then, the ultimate goal
of the resilient binary classification problem is making д(·) ≤ ϵ
for some N and for all α given conditions on P F, S , where ϵ is a
sufficiently small scalar. Finally, we note that the resilience binary
classification problem is related to the problem of minimizing generalization error of a classifier considered in traditional classification
(See Section A).
We note that in this paper a BFA resilient binary classification
problem is simply called a resilient binary classification problem
assuming a BFA as an attack model. дP denotes the optimal д of
the resilient binary classification problem to explicitly represent
the dependency on P. Also, an algorithm A is more resilient than an
Í
Í
algorithm B if α ∈Θ 1{дA (N , α) = 1} ≤ α ∈Θ 1{дB (N , α) = 1},
and A, B, дA , and дB satisfy the constraint in the problem (Equation (6)). In the following section, we utilize the definition of the
resilient binary classification problem to analyze traditional linear
classification algorithms for resilience under a BFA.

5

RESILIENCE OF TRADITIONAL
LINEAR CLASSIFICATION

Traditional classification algorithms (e.g. SVMs or 0-1 loss linear
classification) rarely consider a learning environment that is partially controlled by attackers. Here, we focus on linear classification
algorithms (i.e., F = L, where L is the set of linear functions),
which is a basic building block for more complex classification
algorithms. In this section, we analyze whether traditional linear
classification algorithms are resilient. First, linear classification

algorithms with various convex loss functions are analyzed (Section 5.1). Next, a linear classification algorithm with a 0-1 loss
function is analyzed (Section 5.2).
In the following, we strictly consider un-attacked training data
D̂ for which a perfect classifier exists – i.e., for some h ∈ H , kW ·
R̂ ` (h|D̂)k1 = 0 – such that only errors are introduced by attacks.
We note that, in practice, the empirical risk over training data is
rarely equal to zero due to errors from noise and an assumption on
H . However, by treating errors as attacks, the theoretical results in
the following sections can be interpreted as assuming worst-case
errors – e.g., attacks.
The resilient binary classification problem finds a classification
algorithm P and a resilience bound дP , but the resilience bound
may be trivial for some α, i.e., д(N , α) = 1. Thus, it is worthwhile
to find a resilience attack condition, A P ⊆ Θ, such that д(N , α) is
non-trivial for all α ∈ A P . In this case, we say that P is resilient
w.r.t. A P .
Definition 4 (resilient w.r.t. A P ). Given N , P, дP , and A P , a
classification algorithm P is resilient w.r.t A P if the algorithm is
д(N , α)-resilient to a BFA and д(N , α) < 1 for all α ∈ A P .
Here, we emphasize that finding an attack condition on α that
makes a classification algorithm 1-resilient to a BFA (i.e., finding
some set BP such that BP ⊆ A Pc ) is equally important to finding
the resilience attack condition A P since α ∈ BP can be a “breaking
point” of the algorithm P. We refer to BP as the perfectly attackable
condition of P. Thus, we introduce a new notion, perfectly attackable
w.r.t BP , which is formally described as follows:
Definition 5 (perfectly attackable w.r.t. BP ). Given N , P, and BP ,
a classification algorithm P is perfectly attackable w.r.t BP if the
algorithm is 1-resilient to a BFA for all α ∈ BP .
Next, we introduce a maximal resilience attack condition Ā ⊆ Θ. It is
a resilience attack condition of some linear classification algorithm
or a combination of algorithms where the size of the condition is
maximal. Formally,
Definition 6 (maximally resilient condition). Ā is a maximal resilient condition if Ā = ∪P ∈QL, S A P , where Q L, S = {P L, ` |` ∈
S} ∪ P M, `01 ⊆ P L, S and P M, `01 is defined in Section 6.
We note that if the resilience attack condition A P of a classification
algorithm P is same as Ā, we say that P is maximally resilient. To
find the maximal resilience attack condition Ā, we consider some
superset of it (i.e., B̄ c such that Ā ⊆ B̄ c ), which is a theoretical
upper bound of the maximal resilience attack condition. We argue
that there exists some classification algorithm that achieves the
attack condition B̄ c . This then implies B̄ c is the maximal resilience
attack condition (See Theorem 2).
One example of B̄ can be some subset of ∩` ∈S BP L, ` due to
Ā = ∪` ∈S A P L, ` ⊆ ∪` ∈S BPc
⊆ B̄ c . The following theorems
L, `

formally state B̄ and a condition when B̄ c is the maximal resilience
attack condition.
Theorem 1. Given | D̂ + | and |D̂ − |, let B̄ be


1
1
α α + ≥ | D̂ + | or α − ≥ |D̂ − | .
2
2
For all ` ∈ S, P L, ` is perfectly attackable w.r.t. B̄.

(7)

ICCPS, April 2017, Pittsburgh, PA USA

Sangdon Park, James Weimer, and Insup Lee

1

1

1

α−
0.5
| D̂ − |

α−
0.5
| D̂ − |

α−
0.5
| D̂ − |

[39] can be vulnerable if an attacker can tamper at least one feature
vector. We note that convex-loss linear classification algorithms
are not maximally resilient since BPc
⊂ B̄ c .
L, `c

5.2
0

0.5

α+
| D̂ + |

(a) Convex loss

1

0

|D̂ − | 0.5
+
|D̂ + | α

1

0

| D̂ + |

(b) 0-1 loss

0.5

α+
|D̂ + |

1

(c) Majority 0-1 loss

Figure 1: Perfectly attackable conditions on α for each linear
classification algorithm (colored in red). Assume |D̂ + | = 75,
and |D̂ − | = 25.
proof sketch. For all N , α ∈ B̄, and ` ∈ S, we find some D̂ and
D̂ α where V (P L, ` (D̂ α )|N , α) = 1. See Section B.2.1 for details. 
Theorem 2. If there exists P ∈ Q L, S such that A P = B̄ c , then
B̄ c is the maximal resilience attack condition.
proof sketch. We use the following two set relations to prove
Ā = B̄ c : (1) Ā ⊆ B̄ c = A P and (2) A P ⊆ Ā. See Section B.2.2 for
details.

The intuitive interpretation of B̄ is that if the number of tampered
positive or negative feature vectors is greater than or equal to
the half of |D̂ + | or |D̂ − |, respectively, then any linear classification
algorithm trained with this training data can be perfectly attackable
w.r.t. B̄. We note that in Section 6 we show B̄ is actually the
maximal resilience attack condition. Thus, we assume this from
now on. In the following subsections, we show that two classical
approaches do not achieve the maximal resilience: (i) convex loss
linear classification; and (ii) 0-1 loss linear classification.

5.1

Convex Loss Linear Classification

In this section, the class of convex-loss linear classification algorithms is considered, where it is the collection of P L, `c ∈ P L, S ,
where `c is any convex relaxation of a 0-1 loss function, such as a
hinge loss function. SVMs and a maximum likelihood learning of logistic regression belong to this class. We prove that any algorithm in
this class is perfectly attackable w.r.t. some attack condition where
an attacker can tamper at least one feature vector. Let BP L, `c be the
attack condition for the convex-loss linear classification algorithms
being perfectly attackable, and then the attack condition is formally
stated as follows:
Proposition 1. Let BP L, `c be the set of α that satisfies one of the
following two conditions:
(i) α + > 0, (ii) α − > 0.

(8)

Then, P L, `c is perfectly attackable w.r.t BP L, `c and resilient w.r.t.
BPc
.

0-1 Loss Linear Classification

A 0-1 loss linear classification algorithm is defined as P L, `01 ∈
P L, S , where `01 (·) is a 0-1 loss function. We prove that the 0-1 loss
linear classification algorithm is perfectly attackable w.r.t. some attack condition where the number of tampered positive or negative
feature vectors is greater than or equal to the half of |D̂ + | or | D̂ − |,
respectively, or the sum of the number of tampered positive feature
vectors and the number of tampered negative feature vectors is
greater than or equal to | D̂ − | or | D̂ + |. Let BP L, `01 be the attack
condition for the 0-1 loss linear classification algorithm being perfectly attackable, and then the attack condition is formally stated
as follows:
Proposition 2. Given |D̂ + | and | D̂ − |, let BP L, `01 be the set of α
that satisfies one of the following four conditions:
1
1
(i) α + ≥ |D̂ + |,
(ii) α − ≥ |D̂ − |,
2
2
(iii) α + + α − ≥ |D̂ − |,
(iv) α + + α − ≥ |D̂ + |.
(9)
Then, P L, `01 is perfectly attackable w.r.t. BP L, `01 .
proof sketch. For all N and α ∈ BP L, `01 we find some D̂ and
D̂ α where V (P L, `01 (D̂ α )|N , α) = 1. See Section B.2.4 for details.

This proposition implies the 0-1 loss linear classification is strictly
more resilient than convex one (See Figure 1b for comparison).
Thus, different to the convex case, tampering single feature vector
is not critical for the 0-1 loss linear classification. This means
any CPS using convex linear classification algorithms [12, 39, 41]
can be converted into the 0-1 linear classification algorithm to
defend against the single feature vector tampering; however, neither
approach can provide maximal resilience due to BPc
⊂ B̄ c .
L, `01

6

RESILIENT LINEAR CLASSIFICATION

In this section, we propose a maximally resilient linear classification algorithm. A majority 0-1 loss linear classification is defined
as P M, `01 ∈ P L, S , where M denotes a majority constraint that
restricts a feasible set of classifiers by only allowing a classifier
that correctly classifies at least half of positive and negative feature
vectors, according to


1
1
M = h ∈ L R̂ `01 (h|D̂ α+ ) < and R̂ `01 (h| D̂ α− ) < .
(10)
2
2

L, `c

proof sketch. The idea of “perfectly attackable” proof is that
for all N and α ∈ BP L, `c we find some D̂ and D̂ α where V (P L, `c (D̂ α )
|N , α) = 1. The “resilient” proof is trivial. See Section B.2.3 for
details.


In the following subsections, the resilience proof and the worst-case
resilience bound of the majority 0-1 classification are provided.

This implies even though an attacker has weak ability to tamper
training data, it can make the algorithm misclassify all positive or all
negative feature vectors of un-attacked training data by tampering
only one positive or negative feature vector (See Figure 1a for
the visualization of the perfectly attackable condition on α). For
example, data-driven CPS that use SVMs to train intrusion detectors

The majority 0-1 loss linear classification is perfectly attackable w.r.t.
some attack condition where an attacker can manipulate greater
than or equal to the half of |D̂ + | or | D̂ − |. Let BPM, `01 be the attack
condition for the majority 0-1-loss linear classification algorithms
being perfectly attackable, and then the attack condition is formally
stated as follows:

6.1

Resilience of Majority 0-1 Loss Linear
Classification

Resilient Linear Classification

ICCPS, April 2017, Pittsburgh, PA USA

Theorem 3. Given | D̂ + | and |D̂ − |, let BPM, `01 be

Alarm



1
1
α α + ≥ | D̂ + | or α − ≥ |D̂ − | .
2
2

(11)

Then, P M, `01 is perfectly attackable w.r.t. BPM, `01 and resilient w.r.t.
BPc
.
M, `01

proof sketch. The ideal of “perfectly attackable” proof is that
for all N and α ∈ BPM, `01 we find some D̂ and D̂ α where V (P M, `01
(D̂ α )|N , α) = 1. For the “resilient” proof, we exploit the property
of the majority constraint. See Section B.2.5 for details.

This result shows that the majority 0-1 loss linear classification
algorithm is more resilient than traditional linear classification
algorithms, which is also illustrated in Figure 1c. Furthermore,
it achieves the maximal resilience condition (Theorem 1) due to
BPM, `01 = B̄, showing this algorithm achieves the maximal resilience attack condition.

6.2

Robustness of Resilient Classification

If a classification algorithm is resilient, it is worth analyzing the
degree of resilience. If α ∈ A PM, `01 , where A PM, `01 = BPc
,
M, `01

then the worst-case resilience bound д of the majority 0-1 loss
classification algorithm is nearly proportional to the tampering
ability of an attacker, which is formally stated as follows:
Theorem 4. Given |D̂ + |, | D̂ − |, and α ∈ A PM, `01 , the resilience
bound д of P M, `01 can be computed as follows:


| D̂ + |−1
min 2α + + α − , α + + 2
д(N , α) = max
,
|D̂ + |


| D̂ − |−1 !
min α + + 2α − , α − + 2
.
(12)
|D̂ − |
proof sketch. To prove V (·) is bounded by д(·) for all N and
α ∈ A PM, `01 , we exploit the optimality condition of an optimal

classifier P M, `01 (D̂ α ) and the property of the majority constraint.
To prove that the bound is tight for all N and α ∈ A PM, `01 , we find
some D̂ and D̂ α where V (·) = д(·). See Section B.2.6 for details.



This theorem shows that if α ∈ A PM, `01 , the resilience bound is nontrivial. Also, it shows that even if the attacker capability parameter
α is restricted (i.e., α ∈ A PM, `01 ) to ensure that the algorithm is
resilient w.r.t. A PM, `01 , the tampered portion of training data still
affects on the accuracy of the algorithm. Finally, we note that the
resilience bound д is tight.

7

CASE STUDY

In this section, we validate the proven resilience of algorithms
experimentally. Qualitative results on synthetic data are presented
in Figure 3 and results on a real-world retrospective arrhythmia
data are shown in Table 3.

Heart

Pacemaker

Arrhythmia
detector

Figure 2: Pacemaker with an Arrhythmia detector.
The majority 0-1 loss linear classification algorithm is formulated
in the following mixed integer linear program (MILP).
min 1>z + λkhk2

h,e,z

s.t. ∀i, ei ≥ 1 − yi h >x i , −δz ≤ e ≤ δz
1 +
1 −
>
1>
+ z ≤ (| D̂ α | − 1), 1− z ≤ (| D̂ α | − 1),
2
2
where (x i , yi ) is an ith training data pair, h ∈ Rp is a real-valued
classifier, e ∈ R | D̂ α | denotes a scaled classification error, z ∈
{0, 1} | D̂ α | is a vector that indicates misclassification of each training data pair, λ is a regularization constant, set to zero, and δ is
a sufficiently large positive constant, where δ = 103 . 1+ and 1−
represent vectors where a jth element is filled with one if y j = +1
and y j = −1, respectively, and zeros elsewhere. We note that the
0-1 loss linear classification algorithm is formulated in the same
way to the above MILP except for the last two constraints (See
Section C), related to the majority constraint, and we adopt a standard SVMs formulation [15] without a regularization term for fair
comparison. Theoretically, the performance of the 0-1 loss linear
classification algorithm is as good as that of the convex loss linear
classification algorithms [5]. If there are no attack and no error,
the 0-1 loss linear classification algorithm is same as the majority
0-1 loss linear classification algorithm since the last two constraints
of MILP are not activated if there are no attacks and no error.
In experiments, we consider two types of attacks: a point attack
and an overlap attack, which are concrete instances of a BFA. The
point attack is an attack that manipulates a single feature vector to
be located far from the training data as illustrated in Figure 3. The
attacked single feature vector is chosen and tampered as follows.
Let α + = 1, and x̄ + and x̄ − be the mean of positive and negative
feature vectors, respectively. Any positive feature vector is chosen
and replaced to a scaled vector σx where the scaled vector is on the
half-line from x̄ + to the direction of x̄ − − x̄ + , and the scale value σ
is a sufficiently large scalar.
The overlap attack is an attack that manipulates positive and/or
negative feature vectors to be overlapped negative and/or positive
feature vectors, respectively, as illustrated in Figure 3. The overlap attack is briefly described as follows: when α = (α + , α − ), α +
and α − number of positive and negative feature vectors are randomly chosen for tampering, respectively. The chosen positive and
negative feature vectors are randomly overlapped to negative and
positive un-attacked feature vectors, respectively. These steps are
repeated until a target classification algorithm achieves a maximum
desired resilience value V (·).
Synthetic data. In Figure 3, the classification results of each
linear classification algorithm, such as SVMs, the 0-1 loss linear
classification, and the majority 0-1 loss linear classification, are

ICCPS, April 2017, Pittsburgh, PA USA

Attack Type

Sangdon Park, James Weimer, and Insup Lee
Approach
0-1

Training Data
SVMs
20
+1
!1

15

15

5

0

0

0

10
x1

15

-5

20

+1
!1

+1
!1

0

0

0

-5
10 0

10 2

x1
+1
!1

(α +,

α −)

(0, 24)

+1
!1

-5
10 0

10 4

+1
!1

15

x2

10

10

0

0

-5

-5

-5

-5

0

5

10
x1

15

20

+1
!1

15

0

20

10 4
x1

0

15

10 2

20

5

10
x1

20

0

10 2

5

5

15

5

5

0

10
x1

+1
!1

x1

10

x2

=

5

15

20

15

10

0

10

x2

Overlap
Attack

+1
!1

-5
10 0

10 4

20

15

-5

20

20

x1

20

15

10
5

10 4

10
x1

15

5

10 2

5

20

5

-5
10 0

0

0

x2

=

-5

20

10

10

(0, 1)

15

x2

α −)

10
x1

15

x2

(α +,

5

20

20
15

0

5

x2

5

10

x2

x2
5

0

+1
!1

15

10

5

-5

Point Attack

15

10

x2

10

(α +, α − ) =
(0, 0)

20
+1
!1

x2

No Attack

0-1 with majority

20
+1
!1

x2

20

5

0

5

10
x1

15

20

0

5

10
x1

15

20

Figure 3: The resilience of each linear classification algorithm under the specified attacks. The blue or red mark represents a
positive or negative feature vector, respectively. The feature vector in the blue or red region is classified as positive or negative,
respectively.
Approach
Attack Type
SVMs

0-1

0-1 with
majority

(α +, α − ) = (0, 0)

0.0

0.0

0.0

Point Attack

1.0

0.0270

0.0270

1.0

1.0

0.5946

No Attack

(α +, α − ) = (0, 1)

Overlap Attack
(α +, α − ) = (16, 21)

Table 3: The resilience metric V (·) of each linear classification algorithm for Arrhythmia detection [24] under the
specified attacks.
1
Empirical
Theoretical
0.8

V (")

0.6

0.4

0.2

0

0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
,+
^ +k
kD

Figure 4: The degree of the resilience of P M, `01 in the resilience metric V (·) with respect to the ability of an attacker.
The blue solid and dashed line represents the theoretical
robustness bound (Equation (12)) and the red cross means
the empirically evaluated feasible resilience. Assume | D̂ + | =
|D̂ − | and α + = α − .

illustrated with different types of an attack. The original training data without attacks is randomly drawn from two Gaussian
distributions, as illustrated in the first column and the first row,
where | D̂ + | = 20 and |D̂ − | = 80. When there is no attack (the first
row in Figure 3), all three algorithms correctly classify training
data. If there is a point attack (the second row in Figure 3), only
SVMs algorithm is affected by the attack, outputting a classifier
that misclassifies all positive feature vectors of un-attacked training
data. When an overlap attack (the third row in Figure 3) is applied,
where α − = 24, both SVMs and the 0-1 loss linear classification
output classifiers that misclassifies all positive feature vectors of
un-attacked training data while the majority 0-1 loss classification
algorithm still correctly classifies the portion of the positive feature
vectors of un-attacked training data, showing that the majority
0-1 loss classification algorithm is more resilient than others.
Moreover, using the synthetic data, the theoretical worst-case
resilience bound (Equation (12)) of the majority 0-1 loss linear
classification is experimentally shown in Figure 4. The blue line
represents the theoretical worst-case resilience bound. Red points
are the resilience V (·) over the corresponding α. Specifically, 100
different D̂ are randomly generated, where D̂ + and D̂ − are drawn
from two Gaussian distributions of positive and negative labels,
respectively. For each D̂ and for each α + , which ranges from 0 to
the total number of positive feature vectors, an attacker moves α +
number of positive feature vectors beyond the negative features in
100 different ways to obtain D̂ α so that positive and negative feature
vectors cannot be linearly separable. By taking the maximum of
V (·) for 100 different D̂ and 100 different D̂ α , the resilience V (·)
is obtained for each α + , which is represented in a red cross. In
Figure 4, the red crosses do not excess the theoretical bound and
the increasing trend follows the bound.

Resilient Linear Classification

ICCPS, April 2017, Pittsburgh, PA USA

Medical data. We evaluated the resilience of traditional linear
classification algorithms and the proposed algorithm using arrhythmia dataset. The arrhythmia, a.k.a irregular heartbeat, is a condition
of the heart in which the heartbeat is irregular. An arrhythmia detector cooperated with logs from pacemaker can reduce stroke and
death rate [21]. To design such a detector, electrocardiogram (ECG)
training data can be collected from logs of the pacemaker (Figure 2)
whether ECG data is normal or abnormal (e.g., atrial fibrillation or
sinus tachycardia). But, if the pacemaker is vulnerable, the training data can be tampered to hinder to detect arrhythmia, possibly
leading to death.
In Table 3, we have compared the resilience V (·) of each algorithm on real medical dataset. Arrhythmia dataset [24], which can
be found at the UCI machine learning repository [32], is used for
evaluating the resilience of each algorithm. The Arrhythmia dataset
is preprocessed as follows. Due to the computational limitation to
solve the MILP, we use 20 percent of training data (i.e., |D̂ + | = 37
and |D̂ − | = 49) and select features from 40th and 99th for training classifiers. We’ve obtained the same results as illustrated with
synthetic data. SVMs algorithm outputs a classifier that misclassifies all positive or negative feature vectors under both a point
attack and an overlap attack. 0-1 loss linear classification does not
affect on a point attack but outputs a classifier that misclassifies
all positive or negative feature vectors when an overlap attack is
applied by tampering 43.2 and 42.8 percent of positive and negative
feature vector, respectively. However, the majority 0-1 loss linear
classification still correctly classifies the portion of positive and
negative feature vectors even though about 43 percent of training
data were tampered. We emphasize that V (·) values in Table 3 are
not prediction results, but they are evaluated over training data,
making V (·) = 0 possible. However, a higher V (·) value implies
higher prediction error.
Comparison with [28]. Kearns and Li’s paper [28] analyzes a
binary classification problem under the malicious error (ME) model,
but our paper analyzes a binary linear classification problem under a BFA, which is a general case of the ME model. Here, we
compare each paper’s result by providing an example. Assume a
binary linear classification problem under the ME model, where
|D̂ + | = |D̂ − | = 50 and α + = α − = 10. Kearns and Li’s paper states
that if a designer wants to have the expected accuracy of 0.9, then
α + = α − < 0.1 ≈ 0.091 regardless of a classification algo+
−
1+0.1
| D̂ |

| D̂ |

rithm. This means at most 0.091 percent of training data can be
tampered to guarantee the expected accuracy. However, this does
+
not state anything on the expected accuracy when α + ≥ 0.091. In
| D̂ |

comparison to this, our paper implies that, in the case of the majority 0-1 linear classification algorithm, д(| D̂|, (α + , α − )) = 0.6. This
means that a designer can expect the accuracy on training data that
is at least 1 − 0.6 = 0.4. This further implies the expected minimum
+
accuracy can be approximately 0.4 when α + = 0.2 ≥ 0.091. We
| D̂ |

note that the connection between the accuracy on training data
(i.e., the performance measure of this paper) and the expected accuracy (i.e., the performance measure of traditional classification) can
be found in Section A.

8

CONCLUSIONS

In particularly, the incorrect decisions on CPS directly affect on a
physical environment, so learning techniques under training data
attacks should be scrutinized. Toward the goal of resilient machine
learning, we propose a resilience metric for the analysis and design
of a resilient classification algorithm under training data attacks.
Traditional algorithms, such as convex loss linear classification algorithms and the 0-1 loss linear classification algorithm, are proved
to be resilient under restricted conditions. However, the proposed
0-1 loss linear classification with a majority constraint is more
resilient than others, and it is the maximally resilient algorithm
among linear classification algorithms. The worst-case resilience
bound of the proposed algorithm is then provided, suggesting how
resilient the algorithm is under training data attacks.
Countermeasures. The resilience analysis on different linear
classification algorithms provides us clues for countermeasures on
training data attacks. Here, we briefly discuss a possible direction
for countermeasures and its challenges. In general, additional algorithms can be considered to eliminate the worst-case situations
in the analysis of each classification algorithm. For example, to
defend against the point attack on SVMs, it might be considered
to add a preprocessing step that saturates large values in training
data. Specifically, if a designer knows the minimum and maximum
range of features, then range can saturate the large values that contribute to the point attack. However, this might not be an effective
countermeasure since the range of features is not known in general
and the point attack can be conducted after the preprocessing step,
not before it.
Here, we emphasize that our analysis, which is purposely focused on a classification algorithm exclusively, helps to devise
countermeasures: combining a classification algorithm with a preprocessing step or using a complex classification algorithm (e.g., hierarchical approach and neural networks). We believe that the
advanced algorithms work better under the training data attack in
general and our analysis on the simple algorithms (e.g., SVMs) can
be a building block for analyzing and devising advanced algorithms.
Future works. As a future work, the following issues are worth
being considered. A more practical mixed integer linear program
can speed up computational time (e.g., [37]) and it would be promising to design and analyze multiple algorithms in tandem (one to
monitor the data, one to learn a classifier). It is also worth incorporating bounded noise error and designing error on H in analysis, and extending to non-linear and multiclass classification problem. Finally, to devise countermeasures, it would be promising to
consider resilient algorithms that estimate attacker capabilities or
model prior knowledge on attackers.

ACKNOWLEDGMENTS
This work was supported in part by NSF CNS-1505799 and the IntelNSF Partnership for Cyber-Physical Systems Security and Privacy,
by ONR N00014-17-1-2012, and by Global Research Laboratory
Program (2013K1A1A2A02078326) through NRF, and the DGIST
Research and Development Program (CPS Global Center) funded by
the Ministry of Science, ICT & Future Planning. This material is also
based in part on research sponsored by DARPA under agreement
number FA8750-12-2-0247. The U.S. Government is authorized
to reproduce and distribute reprints for Governmental purposes

ICCPS, April 2017, Pittsburgh, PA USA
notwithstanding any copyright notation thereon. The views and
conclusions contained herein are those of the authors and should
not be interpreted as necessarily representing the official policies
or endorsements, either expressed or implied, of DARPA or the U.S.
Government.

REFERENCES
[1] 2016. FBI probing after hackers cripple computer systems at major hospital chain.
(Mar. 2016). http://www.cbsnews.com/news/fbi-probing-after-hackers-cripplecomputer-systems-at-major-hospital-chain-medstar-health/
[2] 2016. R7-2016-07: Multiple Vulnerabilities in Animas OneTouch Ping Insulin
Pump. (Oct. 2016).
[3] 2016. U.S. hospitals are getting hit by hackers. (Mar. 2016). http://money.cnn.
com/2016/03/23/technology/hospital-ransomware/
[4] Dana Angluin and Philip Laird. 1988. Learning from noisy examples. Machine
Learning 2, 4 (1988), 343–370.
[5] Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe. 2006. Convexity, classification, and risk bounds. J. Amer. Statist. Assoc. 101, 473 (2006), 138–156.
[6] Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Srndic,
Pavel Laskov, Giorgio Giacinto, and Fabio Roli. 2013. Evasion attacks against
machine learning at test time. In Joint European Conference on Machine Learning
and Knowledge Discovery in Databases. Springer, 387–402.
[7] Battista Biggio, Blaine Nelson, and Pavel Laskov. 2012. Poisoning Attacks against
Support Vector Machines. In Proceedings of the 29th International Conference on
Machine Learning (ICML-12). 1807–1814.
[8] Tamara Bonaci, Junjie Yan, Jeffrey Herron, Tadayoshi Kohno, and Howard Jay
Chizeck. 2015. Experimental analysis of denial-of-service attacks on teleoperated
robotic systems. In Proceedings of the ACM/IEEE Sixth International Conference
on Cyber-Physical Systems. ACM, 11–20.
[9] Michael Brückner and Tobias Scheffer. 2011. Stackelberg games for adversarial prediction problems. In Proceedings of the 17th ACM SIGKDD international
conference on Knowledge discovery and data mining. ACM, 547–555.
[10] Alvaro A Cárdenas, Saurabh Amin, and Shankar Sastry. 2008. Research Challenges for the Security of Control Systems.. In HotSec.
[11] Stephen Checkoway, Damon McCoy, Brian Kantor, Danny Anderson, Hovav
Shacham, Stefan Savage, Karl Koscher, Alexei Czeskis, Franziska Roesner, Tadayoshi Kohno, and others. 2011. Comprehensive Experimental Analyses of
Automotive Attack Surfaces.. In USENIX Security Symposium. San Francisco.
[12] Chenyi Chen, Ari Seff, Alain Kornhauser, and Jianxiong Xiao. 2015. Deepdriving:
Learning affordance for direct perception in autonomous driving. In Proceedings
of the IEEE International Conference on Computer Vision. 2722–2730.
[13] Sanjian Chen, Lu Feng, Michael R Rickels, Amy Peleckis, Oleg Sokolsky, and
Insup Lee. 2015. A Data-Driven Behavior Modeling and Analysis Framework
for Diabetic Patients on Insulin Pumps. In Healthcare Informatics (ICHI), 2015
International Conference on. IEEE, 213–222.
[14] Yudong Chen, Constantine Caramanis, and Shie Mannor. 2013. Robust sparse
regression under adversarial corruption. In Proceedings of the 30th International
Conference on Machine Learning (ICML-13). 774–782.
[15] Corinna Cortes and Vladimir Vapnik. 1995. Support-vector networks. Machine
learning 20, 3 (1995), 273–297.
[16] Gabriela F Cretu, Angelos Stavrou, Michael E Locasto, Salvatore J Stolfo, and
Angelos D Keromytis. 2008. Casting out demons: Sanitizing training data for
anomaly sensors. In IEEE Symposium on Security and Privacy (S&P). IEEE, 81–95.
[17] Nilesh Dalvi, Pedro Domingos, Sumit Sanghai, Deepak Verma, and others. 2004.
Adversarial classification. In Proceedings of the tenth ACM SIGKDD international
conference on Knowledge discovery and data mining. ACM, 99–108.
[18] Hamza Fawzi, Paulo Tabuada, and Suhas Diggavi. 2014. Secure estimation
and control for cyber-physical systems under adversarial attacks. IEEE Trans.
Automat. Control 59, 6 (2014), 1454–1467.
[19] Uriel Feige, Yishay Mansour, and Robert Schapire. 2015. Learning and inference
in the presence of corrupted inputs. In Proceedings of The 28th Conference on
Learning Theory.
[20] Jiashi Feng, Huan Xu, Shie Mannor, and Shuicheng Yan. 2014. Robust logistic regression and classification. In Advances in Neural Information Processing Systems.
253–261.
[21] Taya V Glotzer, Anne S Hellkamp, John Zimmerman, Michael O Sweeney, Raymond Yee, Roger Marinchak, James Cook, Alexander Paraschos, John Love,
Glauco Radoslovich, and others. 2003. Atrial high rate episodes detected by
pacemaker diagnostics predict death and stroke report of the atrial diagnostics
ancillary study of the MOde Selection Trial (MOST). Circulation 107, 12 (2003),
1614–1619.
[22] Sally A. Goldman and Robert H. Sloan. 1995. Can pac learning algorithms tolerate
random attribute noise? Algorithmica 14, 1 (1995), 70–84.
[23] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. 2015. Explaining
and harnessing adversarial examples, In International Conference on Learning
Representations (ICLR). arXiv preprint arXiv:1412.6572 (2015).

Sangdon Park, James Weimer, and Insup Lee
[24] H Altay Guvenir, Burak Acar, Gulsen Demiroz, and Ayhan Cekin. 1997. A
supervised machine learning algorithm for arrhythmia analysis. In Computers in
Cardiology 1997. IEEE, 433–436.
[25] Raia Hadsell, Pierre Sermanet, Jan Ben, Ayse Erkan, Marco Scoffier, Koray
Kavukcuoglu, Urs Muller, and Yann LeCun. 2009. Learning long-range vision for
autonomous off-road driving. Journal of Field Robotics 26, 2 (2009), 120–144.
[26] Todd E Humphreys, Brent M Ledvina, Mark L Psiaki, Brady W OHanlon, and
Paul M Kintner Jr. 2008. Assessing the spoofing threat: Development of a portable
GPS civilian spoofer.
[27] Alex Kantchelian, JD Tygar, and Anthony D Joseph. 2015. Evasion and Hardening
of Tree Ensemble Classifiers. arXiv preprint arXiv:1509.07892 (2015).
[28] Michael Kearns and Ming Li. 1993. Learning in the presence of malicious errors.
SIAM J. Comput. 22, 4 (1993), 807–837.
[29] Karl Koscher, Alexei Czeskis, Franziska Roesner, Shwetak Patel, Tadayoshi
Kohno, Stephen Checkoway, Damon McCoy, Brian Kantor, Danny Anderson,
Hovav Shacham, and others. 2010. Experimental security analysis of a modern
automobile. In IEEE Symposium on Security and Privacy (S&P). IEEE, 447–462.
[30] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2012. Imagenet classification with deep convolutional neural networks. In Advances in neural information
processing systems. 1097–1105.
[31] Gert RG Lanckriet, Laurent El Ghaoui, Chiranjib Bhattacharyya, and Michael I
Jordan. 2002. A robust minimax approach to classification. Journal of Machine
Learning Research 3, Dec (2002), 555–582.
[32] M. Lichman. 2013. UCI Machine Learning Repository. (2013). http://archive.ics.
uci.edu/ml
[33] Achin Jain Madhur Behl and Rahul Mangharam. 2016. Data-Driven Modeling,
Control and Tools for Cyber-Physical Energy Systems. ACM/IEEE 7th International Conference on Cyber-Physical Systems (ICCPS) (apr 2016).
[34] Shike Mei and Xiaojin Zhu. 2015. Using Machine Teaching to Identify Optimal
Training-Set Attacks on Machine Learners.. In AAAI. 2871–2877.
[35] Yilin Mo and Bruno Sinopoli. 2010. False data injection attacks in control systems.
In Preprints of the 1st workshop on Secure Control Systems. 1–6.
[36] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj
Tewari. 2013. Learning with noisy labels. In Advances in neural information
processing systems. 1196–1204.
[37] Tan Nguyen and Scott Sanner. 2013. Algorithms for Direct 0–1 Loss Optimization
in Binary Classification. In Proceedings of the 30th International Conference on
Machine Learning (ICML-13). 1085–1093.
[38] Miroslav Pajic, James Weimer, Nicola Bezzo, Paulo Tabuada, Oleg Sokolsky, Insup
Lee, and George J Pappas. 2014. Robustness of attack-resilient state estimators.
In ICCPS’14: ACM/IEEE 5th International Conference on Cyber-Physical Systems
(with CPS Week 2014). IEEE Computer Society, 163–174.
[39] Kaveh Paridari, Alie El-Din Mady, Silvio La Porta, Rohan Chabukswar, Jacobo
Blanco, André Teixeira, Henrik Sandberg, and Menouer Boubekeur. 2016. CyberPhysical-Security Framework for Building Energy Management System. In 2016
ACM/IEEE 7th International Conference on Cyber-Physical Systems (ICCPS). IEEE,
1–9.
[40] Fabio Pasqualetti, Florian Dörfler, and Francesco Bullo. 2013. Attack detection
and identification in cyber-physical systems. IEEE Trans. Automat. Control 58, 11
(2013), 2715–2729.
[41] Young-Woo Seo, Junsung Kim, and Ragunathan Rajkumar. 2014. Predicting
dynamic computational workload of a self-driving car. In 2014 IEEE International
Conference on Systems, Man, and Cybernetics (SMC). IEEE, 3030–3035.
[42] Yasser Shoukry, Paul Martin, Paulo Tabuada, and Mani Srivastava. 2013. Noninvasive spoofing attacks for anti-lock braking systems. In International Workshop
on Cryptographic Hardware and Embedded Systems. Springer, 55–72.
[43] Robert Sloan. 1988. Types of noise in data for concept learning. In Proceedings of
the first annual workshop on Computational learning theory. Morgan Kaufmann
Publishers Inc., 91–96.
[44] Yunmok Son, Hocheol Shin, Dongkwan Kim, Youngseok Park, Juhwan Noh,
Kibum Choi, Jungwoo Choi, and Yongdae Kim. 2015. Rocking drones with intentional sound noise on gyroscopic sensors. In 24th USENIX Security Symposium
(USENIX Security 15). 881–896.
[45] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru
Erhan, Ian Goodfellow, and Rob Fergus. 2014. Intriguing properties of neural
networks. In International Conference on Learning Representations (ICLR). http:
//arxiv.org/abs/1312.6199
[46] André Teixeira, Saurabh Amin, Henrik Sandberg, Karl H Johansson, and
Shankar S Sastry. 2010. Cyber security analysis of state estimators in electric power systems. In 49th IEEE conference on decision and control (CDC). IEEE,
5991–5998.
[47] Jorge Valenzuela, Jianhui Wang, and Nancy Bissinger. 2013. Real-time intrusion
detection in power system operations. IEEE Transactions on Power Systems 28, 2
(2013), 1052–1062.
[48] Harry L Van Trees. 2004. Detection, estimation, and modulation theory. John
Wiley & Sons.
[49] Vladimir N Vapnik. 1999. An overview of statistical learning theory. IEEE
transactions on neural networks 10, 5 (1999), 988–999.

Resilient Linear Classification

ICCPS, April 2017, Pittsburgh, PA USA

[50] Yichao Wu and Yufeng Liu. 2012. Robust truncated hinge loss support vector
machines. J. Amer. Statist. Assoc. (2012).
[51] Chenyang Yuan, Jérôme Thai, and Alexandre M Bayen. 2016. ZUbers against
ZLyfts Apocalypse: An Analysis Framework for DoS Attacks on Mobility-as-aService Systems. In 2016 ACM/IEEE 7th International Conference on Cyber-Physical
Systems (ICCPS). IEEE, 1–10.
[52] Tong Zhang. 2004. Solving large scale linear prediction problems using stochastic gradient descent algorithms. In Proceedings of the twenty-first international
conference on Machine learning. ACM, 116.

error
R(ĥ α ) − R(h ∗, H ),
where ĥ α is a classifier trained over tampered training data. Similar
to the traditional approach, this error can be decomposed as:
h
i h
i
R(ĥ α ) − R(h ∗, H ) = R(ĥ α ) − R̂(ĥ) + R̂(ĥ) − R(h ∗, H )
|
{z
}
|
{z
}
B

estimation error

APPENDICES
A CONNECTION TO STATISTICAL
LEARNING THEORY
The goal of machine learning should minimize the generalization
error; moreover, we believe the proposed resilience metric and
generalization error are connected. To illustrate this, first, let us
introduce a few standard notations from machine learning comÍ | D̂ |
munity. Let R̂(h) = 1
i=1 `(yi , h(x i )) be the empirical risk of a
| D̂ |

classifier, R(h) = E(x ,y) `(y, h(x)) be the expected risk of a classifier,
R̂(ĥ) = minh ∈H R̂(h) be the empirical risk of a trained classifier,
R(ĥ) be the risk of the trained classifier, R(h ∗, H ) = inf h ∈H R(h) be
the expected risk of the best classifier in H , and R(h ∗ ) = inf h ∈Y X
R(h) be the Bayes risk. Roughly speaking, the goal of learning
problem is minimizing the generalization error
R(ĥ) − R(h ∗ ).
The generalization error usually decomposed into two errors, called
the estimation error and approximation error, as follows:
h
i 

R(ĥ) − R(h ∗ ) = R(ĥ) − R(h ∗, H ) + R(h ∗, H ) − R(h ∗ )
| {z }
|
{z
}
|
{z
}

generalization error

estimation error

approximation error

Minimizing the approximation error is related to finding a “good”
hypothesis space, H . We acknowledge there are many techniques
for identifying a hypothesis space including structural risk minimization, finding a regularization parameter using cross-validation,
model selection, drop-out in deep learning, and manual modeling of
neural network architecture. However, in our paper, we’ve assumed
we have a “good” H , meaning H contains the true classifier f ∗ so
approximation error always equals zero. Furthermore, since we’ve
assumed there is no noise (or uncertainty) so Bayes risk R(h ∗ ) is
also zero – which implies that R(h ∗, H ) = 0.
If we assume empirical risk minimization as a learning algorithm,
the estimation error can be further decomposed as follows:
h
i h
i
R(ĥ) − R(h ∗, H ) = R(ĥ) − R̂(ĥ) + R̂(ĥ) − R(h ∗, H ) .
|
{z
} |
{z
} |
{z
}
estimation error

A

B

In statistical learning theory, it is known that the first term (i.e., A
1 ) and the second term (i.e., B) converge in probability to zero due to
Vapnik-Chervonenkis (VC) theory. Thus, if the number of training
data goes to infinity and if empirical risk minimization is used as a
learning algorithm, the estimation error converges in probability
to zero. Furthermore, this implies that R̂(ĥ) = 0 converges to zero
since (as described above) R(h ∗, H ) = 0 by assumption.
We can consider the resilient learning problem in a similar fashion; the resilient learning problem is minimizing the estimation
1 some

literatures call this term generalization error.

i h
i h
i
= R(ĥ α ) − R̂(ĥ α ) + R̂(ĥ α ) − R̂(ĥ) + R̂(ĥ) − R(h ∗, H )
|
{z
} |
{z
} |
{z
}
h

A0

C

B

As before, the term B converges in probability to zero due to VC
theory and R(h ∗, H ) = 0, which implies R̂(ĥ) = 0. But, we believe
the behaviors of the term A0 and C are uncharacterized and in this
work, we consider the term R̂(ĥ α ). Note that based on the notations
in paper,
R̂(ĥ α ) = k R̂`01 (P H, ` (D̂ α )| D̂, w)k1 ,
>
where w = |D̂ + | | D̂ − |
, suggesting the resilience metric Eq.
(3) is connected to existing statistical learning theory. Note that

>
we’ve used ∞-norm and w = 1 1
instead since our setup
also is used in literatures and we think it describes the behavior of
the empirical risk of a trained classifier better when an attack is
severe (in other words, α is large).


B

PROOFS ON LEMMAS, PROPOSITIONS,
AND THEOREMS

In this section, we describe the proofs of propositions and theorems
stated in the paper, including supporting lemmas. For the notational
simplicity, we use the following shorthands. Let N + = |D̂ + |, N − =
Í | D̂ |
|D̂ − |, and N = (N + , N − ). Let R̄ ` (h|D̂) = i=1 `(yi , h(x i )) such
that R̄ ` (h|D̂) = | D̂| · R̂ ` (h|D̂). When a 0-1 loss function is used,
a set of classifiers has a same empirical risk. We denote, given
D̂, the class
 of classifiers that has a same empirical risk with h
as Lh = hi ∈ L R̂ `01 (h|D̂) = R̂ `01 (hi |D̂) . In this case, only the
representative, h, is considered so that, for example, if there are
three different classes of classifiers, they are simply called three
different classifiers. Figures used in proofs represent training data,
where the point means the overlap of the annotated number of
feature vectors. The positive and negative feature vectors are colorencoded in blue and red, respectively. Set notations in the papers
can be generalized to multiset notations. In the following proof, we
assume all sets defined are multisets to handle duplicated training
data pairs, which can happen if X ⊆ Z.

B.1

Lemmas

Lemma B.1. For all D̂, α, D̂ α , and h, the following is true:
R̂ `01 (h|D̂ α+ ) − R̂ `01 (h| D̂ + ) ≤
R̂ `01 (h|D̂ α− ) − R̂ `01 (h| D̂ − ) ≤

α+
|D̂ + |
α−
|D̂ − |

and
.

Proof. First, for any classifier, h, R̂ `01 (h|D̂ α+ ) can increase compared to R̂ `01 (h|D̂ + ) if an attacker maliciously manipulates training

ICCPS, April 2017, Pittsburgh, PA USA

Sangdon Park, James Weimer, and Insup Lee

data. Also, the amount of the empirical risk increased is at most
α + depending on the choice of the attacker. Formally,
+
| D̂ |

R̂ `01 (h| D̂ α+ ) − R̂ `01 (h|D̂ + ) ≤ s

α+
|D̂ + |

≤

α+
|D̂ + |

,

−
where 0 ≤ s ≤ 1. Likewise, R̂ `01 (h| D̂ α− ) − R̂ `01 (h|D̂ − ) ≤ α − .

| D̂ |

Next, for any classifier, h, R̂ `01 (h|D̂ α+ ) can decrease compared to
R̂ `01 (h|D̂ + ) if an attacker helps h for classification. Also, the amount
+
of the empirical risk decreased is at most α + depending on the

makes R̂ `01 (ĥ α |D̂ + ) = 1 or R̂ `01 (ĥ α |D̂ − ) = 1 for any ` ∈ Φ1 ∪ Φ2 . In
Figure 6b, we denote feature vectors annotated by α + as x and the
point means a set, S, of α + -pairs of (x, +1). Also, the three points
are collinear.
First, assume ` ∈ Φ1 . As illustrated in Figure 6, we consider two
classes of classifiers, Lh1 and Lh2 , where h ∈ Lh1 misclassifies
all feature vectors annotated by α + but correctly classifies others
and h ∈ Lh2 misclassifies all feature vectors annotated by N + − α +
but correctly classifies others. By the definition of ` ∈ Φ1 , the
followings are true:

| D̂ |

choice of the attacker. Formally,
R̂ `01 (h| D̂ + ) − R̂ `01 (h|D̂ α+ ) ≤ s

α+
|D̂ + |

≤

α+
|D̂ + |

| D̂ |



Lemma B.2. Let `c (·) be a convex loss function and h be linear. For
all k, y, and h, there exists x such that `c (y, h(x)) ≥ k.
Proof. Let `c (y, h(x)) = ϕ(t), where t = yh(x), ϕ is convex, and
ϕ(0) = 1, which is a usual setup for convex losses [5].
By the convexity of ϕ and ϕ(0) = 1,
t 
1
(ϕ(t) + ϕ(0)) ≥ ϕ
2
2
t 
− 1.
ϕ(t) ≥ 2ϕ
2



yh(x )
Given k, y, and h, x can be chosen such that 2ϕ t2 −1 = 2ϕ
−
2
1 ≥ k since yh(x) can increase arbitrarily by moving x toward
the direction of the normal vector of h if y = +1 or the opposite direction of the normal vector of h if y = −1. This implies
`c (y, h(x)) = ϕ(t) ≥ k for some x.


Proposition and Theorem Proofs

B.2.1

lim
kh 1 k2 →0

R̄ ` (h 1 |D̂ α )


= dα + + c N + − α + + N − ,

,

−
where 0 ≤ s ≤ 1. Likewise, R̂ `01 (h| D̂ − ) − R̂ `01 (h|D̂ α− ) ≤ α + .

B.2

inf R̄ ` (h| D̂ α ) =

h ∈Lh1

Theorem 1.

Proof. Let ĥ α = P L, ` (D̂ α ) for the notational simplicity of this
proof, and `(y, h(x)) = ϕ(t), where t = yh(x). Assume that ϕ is
lower-bounded by 1 {t ≤ 0}, it is a monotonically non-increasing
function, and limt →∞ ϕ(t) = c for some scalar c < 1. Note that
the assumptions are generalized from the assumptions on convex
losses [5] to cover non-convex ones.
Theorem 1 is formally stated as follows:

1
1
∀`∀N ∀α α + ≥ N + ∨ α − ≥ N + =⇒ ∃D̂∃D̂ α ∃ĥ α ,
2
2

R̂ `01 (ĥ α |D̂ + ) = 1 ∨ R̂ `01 (ĥ α |D̂ − ) = 1 . (13)
Assume α + ≥ 12 N + . we partition the type of loss functions into
two classes. One class is the set of the loss function that has a “flat
tail”. Formally, it is the set of ϕ such that ∀s < t, ϕ(s) = ϕ(t) = d for
some negative t and some scalar d ≥ 1. Call this set Φ1 . The other
class is the set of the loss function that has a “not-flat tail”. Formally,
it is the set of ϕ such that ∃s < t, ϕ(s) > ϕ(t) for any negative t.
Call this set Φ2 . We claim that D̂ and D̂ α illustrated in Figure 6

inf R̄ ` (h| D̂ α ) =

h ∈Lh2

lim
kh 2 k2 →0

R̄ ` (h 2 |D̂ α )



= d N + − α+ + c α+ + N − .
Also, from d > c and α + ≥ 21 N + ,
inf R̄ ` (h|D̂ α ) − inf R̄ ` (h| D̂ α )
h ∈Lh1

h ∈Lh2


= dα + + c N + − α + + N − −


d N + − α+ + c α+ + N −


= d 2α + − N + − c 2α + − N +

= (d − c) 2α + − N +
≥ 0.
This implies inf h ∈Lh R̄ ` (h|D̂ α ) ≥ inf h ∈Lh R̄ ` (h|D̂ α ) ≥ R̄ ` (ĥ α |D̂ α )
1

2

and Lĥ ∩ Lh2 , ∅. Thus, R̂ `01 (ĥ α |D̂ + ) = 1 for some ĥ α and all
α
` ∈ Φ1 .
Next, assume ` ∈ Φ2 . Same as before, as illustrated in Figure 6, we
consider two classes of classifiers, Lh1 and Lh2 . By the definition
of ` ∈ Φ2 , an attacker can choose x such that
Õ
inf
`(y, h(x)) ≥ inf R̄ ` (h|D̂ α ).
h ∈Lh1

h ∈Lh2

(x ,y)∈S

This is because the left term can be arbitrarily large if an attacker
moves x to the right side in Figure 6b. However, the right term
cannot be arbitrarily large since any h ∈ Lh2 correctly classifies x.
Í
Here, let h̄ = arg inf h ∈Lh (x ,y)∈S `(y, h(x)). Thus, the following
1
is true:





inf R̄ ` (h | D̂ α ) = inf

h∈Lh

1

h∈Lh

R̄ ` (h | D̂ α \ S) +



≥ inf R̄ ` (h | D̂ α \ S) +
1

h∈Lh

1

Õ

`(y, h(x ))

(x ,y)∈S

Õ

`(y, h̄(x ))









(x ,y)∈S

≥ inf R̄ ` (h | D̂ α \ S) + inf R̄ ` (h | D̂ α )
h∈Lh

1

h∈Lh

2

≥ inf R̄ ` (h | D̂ α ).
h∈Lh

2

This implies Lĥ ∩ Lh2 , ∅. Thus, R̂ `01 (ĥ α |D̂ + ) = 1 for some ĥ α
α
and all ` ∈ Φ2 . Likewise, if α − ≥ 12 N − , then R̂ `01 (ĥ α |D̂ − ) = 1 for
some ĥ α and all `. Therefore, Equation (13) is true.


Resilient Linear Classification

N+

ICCPS, April 2017, Pittsburgh, PA USA

N+ − α+

N−

α+

N−

h1

(a) D̂

h2

(b) D̂ α

Figure 6: D̂ and D̂ α for the necessary condition proof of Theorem 1 and Proposition 2.

First, assume α + > 0. Consider D̂ and D̂ α illustrated in Figure 5.
An attacker converts D̂ to D̂ α by moving one positive data pair,
(x j , +1), to the right side, such that three points are collinear as in
Figure 5b.
Given D̂ α , there are six classes of classifiers, Lhi , where i ∈ [1, 6]
and hi are classifiers illustrated in Figure 5b. By Lemma B.2, an
attacker can choose x j such that `c (+1, h̄(x j )) ≥ k, where
h̄ = arg inf `c (+1, h(x j )) and
h ∈Lh1

k ≥ max inf R̄ `c (h|D̂ α ).

α−

i ∈[2,6] h ∈Li

N+ − α+

N+

N− − α−

N−

h3

α+

From this, the following is true:
inf R̄ `c (h | D̂ α ) = inf

h∈Lh

h∈Lh

1

h∈Lh

h2

h

h∈Lh

(b) D̂ α

h3
N+ − 1

h4
N−

1

h5

(a) D̂

h2

(b) D̂ α

Figure 5: D̂ and D̂ α for the necessary condition proof of
Proposition 1.
B.2.2

Theorem 2.

Proof. Assume A P = B̄ c . Since B̄ c in Theorem 1 provides a
theoretical upper bound of Ā, Ā ⊆ A P . Also, by the definition
of the maximal resilience attack condition, A P ⊆ Ā. Therefore,
Ā = A P = B̄ c .

B.2.3

h∈Lh

i

Proposition 1.

Proof. Let ĥ α = P L, `c (D̂ α ) for the notational simplicity of this
proof. The proposition is formally stated as follows:

∀α α + > 0 ∨ α − > 0 ⇐⇒ ∃D̂∃D̂ α ∃ĥ α ,

R̂ `01 (ĥ α |D̂ + ) = 1 ∨ R̂ `01 (ĥ α | D̂ − ) = 1 .
(⇐=) We prove that if α + = 0 and α − = 0, then P L, `c is not
perfectly attackable. Since an attacker cannot attack any point,
D̂ α = D̂ and P L, `c (D̂ α ) = P L, `c (D̂). This implies R̂ `01 (P L, `c (D̂)|
D̂ + ) = 0 and R̂ `01 (P L, `c (D̂)| D̂ − ) = 0, which implies P L, `c is not
perfectly attackable.
(=⇒) We prove that if α + > 0 or α − > 0, then P L, `c is perfectly
attackable.

i



6 L
where i ∈ [2, 6]. Thus, Lĥ ∩ ∪i=2
h i , ∅. This implies
α

there exists a classifier that is trained over D̂ α can misclassify all
positive or negative feature vectors in D̂, i.e., R̂ `01 (ĥ α |D̂ + ) = 1 or
R̂ `01 (ĥ α |D̂ − ) = 1 for some ĥ α ∈ Lhi . Therefore, P L, `c is perfectly
attackable.

B.2.4

h1

h∈Lh

1

≥ inf R̄ `c (h | D̂ α ),

h6
N−

1

≥ inf R̄ `c (h | D̂ α \ {(x j , +1)}) + inf R̄ `c (h | D̂ α )

Figure 7: D̂ and D̂ α for the necessary condition proof of
Proposition 2.

N+

R̄ `c (h | D̂ α \ {(x j , +1)}) + `c (+1, h(x j ))

≥ inf R̄ `c (h | D̂ α \ {(x j , +1)}) + `c (+1, h̄(x j ))

h1

(a) D̂


1

Proposition 2.

Proof. Let ĥ α = P L, `01 (D̂ α ). Proposition 2 is formally described as follows:

1
1
∀N ∀α α + ≥ N + ∨ α − ≥ N + ∨
2
2
α+ + α− ≥ N − ∨ α+ + α− ≥ N +

=⇒ ∃D̂∃D̂ α ∃ĥ α , R̂ `01 (ĥ α |D̂ + ) = 1 ∨ R̂ `01 (ĥ α |D̂ − ) = 1 .
(=⇒) Prove that if the conditions, α + ≥ 21 N + , α − ≥ 12 N + ,
α + + α − ≥ N − , or α + + α − ≥ N + , satisfies, then P L, `01 is perfectly
attackable.
First, assume α + ≥ 12 N + . To show P L, `01 is perfectly attackable,
it is enough to find D̂ and D̂ α for all N and α that make P L, `01
perfectly attackable. Consider D̂ and D̂ α described in Figure 6.
By a BFA, D̂ α can be represented as in Figure 6b. Note that the
attacker does not move negative feature vectors even though it
may have the ability to do that. Since α + ≥ 12 N + , R̄(h 1 | D̂ α ) ≥
R̄(h 2 |D̂ α ) ≥ R̄(ĥ α |D̂ α ). This means there exists ĥ α that misclassifies
all positive or negative feature vectors in D̂, i.e., R̂ `01 (ĥ α | D̂ + ) = 1
or R̂ `01 (ĥ α |D̂ − ) = 1 for some ĥ α . Therefore, for all N and α, there
exist D̂ and D̂ α that make P L, `01 perfectly attackable. Likewise, if
α − ≥ 12 N − , for all N and α, there exist D̂ and D̂ α that make P L, `01
perfectly attackable.
Next, assume α + + α − ≥ N − . For all N and α, there exist D̂ and
D̂ α that make P L, `01 perfectly attackable as illustrated in Figure 7.
When P L, `01 is trained over D̂ α , one possible optimal classifier can
be h 3 as represented in Figure 7b among eight different classifiers

ICCPS, April 2017, Pittsburgh, PA USA
except for h 1 and h 2 . Since R̄(h 1 |D̂ α ) = α + + α − ≥ R̄(h 2 | D̂ α ) =
α + ≥ N − − α − , and R̄(h 3 |D̂ α ) = N − − α − , the empirical risk of
h 3 is as small as h 1 and h 2 . Thus, any classifier, h ∈ Lh3 , has
R̂ `01 (h|D̂ + ) = 1 or R̂ `01 (h| D̂ − ) = 1, which implies for all N and
α there exists D̂ and D̂ α that make P L, `01 perfectly attackable.
Likewise, for all N and α, if α + + α − ≥ N + , then P L, `01 is perfectly
attackable for some D̂ and D̂ α .
Therefore, for all the above mentioned four cases, there exist D̂
and D̂ α that make P L, `01 perfectly attackable.

B.2.5

Theorem 3.

Proof. Let ĥ α = P M, `01 (D̂ α ), h ∗ = P M, `01 (D̂), where R̂(h ∗ | D̂) =

0, and A= (α + , α − ) α + < 12 N + and α − < 12 N − Formally, show the
following statement:

1
1
∀N ∀α α + < N + ∧ α − < N − ⇐⇒ ∀D̂∀D̂ α ,
2
2


+
−
(M , ∅) ∧ ∀ĥ α , R̂ `01 (ĥ α |D̂ ) < 1 ∧ R̂ `01 (ĥ α |D̂ ) < 1 .
(=⇒) First, prove that if the conditions, α + < 12 N + and α − <
hold, then P M, `01 is feasible and resilient to α-BFA for all
a ∈ A. To prove M , ∅, it is enough to show M includes at least
one element for all N , α, D̂, and D̂ α . Consider h ∗ . By Lemma B.1
and the conditions,
α+
1
α+
R̂ `01 (h ∗ |D̂ α+ ) ≤ R̂ `01 (h ∗ | D̂ + ) + + ≤ + < .
N
N
2
Likewise, R̂(h ∗ |D̂ α− ) < 21 , suggesting h ∗ ∈ M for all N , α, D̂, and
D̂ α .
Since M , ∅, prove that P M, `01 is resilient. By the definition of
M,
1
1
R̂(ĥ α |D̂ α+ ) < ∧ R̂(ĥ α |D̂ α− ) <
2
2
for all D̂, D̂ α , and ĥ α . Thus,
1 1
α+
R̂ `01 (ĥ α | D̂ + ) ≤ R̂ `01 (ĥ α |D̂ α+ ) + + < + = 1
N
2 2
by Lemma B.1, the majority constraint, and the conditions. Likewise,
R̂(ĥ α |D̂ − ) < 1. Therefore, for all N , α, D̂, and D̂ α , P M, `01 is resilient
to α-BFA if α ∈ A.
(⇐=) Next, prove that if P M, `01 is feasible and resilient, then the
conditions, α + < 12 N + ∧ α − < 12 N − , hold. Equivalently,

1
1
∀N ∀α α + ≥ N + ∨ α − ≥ N − =⇒ ∃D̂∃D̂ α ,
2
2


+
−
(M = ∅) ∨ ∃ĥ α , R̂(ĥ α |D̂ ) = 1 ∨ R̂(ĥ α | D̂ ) = 1 .
1 −
2N ,

To show this, it is enough to find D̂ and D̂ α for all N and α that
make P M, `01 infeasible or perfectly attackable. Assume P M, `01 is
feasible and check whether it is perfectly attackable. The proof
is same as proving P L, `01 is perfectly attackable if α + ≥ 21 N + or
α − ≥ 12 N − in Section B.2.4. The main difference is the feasible
set. Here, M is used instead of L. But, we can use the same proof
to prove P M, `01 is perfectly attackable since h 2 in Figure 6b still
satisfy the majority constraint such that h 2 ∈ M.

Sangdon Park, James Weimer, and Insup Lee
Therefore, there exist D̂ and D̂ α that make P M, `01 perfectly
attackable if α + ≥ 12 N + or α − ≥ 12 N − .

B.2.6

Theorem 4.

Proof. Let ĥ α = P M, `01 (D̂ α ), h ∗ = P M, `01 (D̂), where R̂(h ∗ |D̂) =
0, and R̄(·) = R̄ `01 (·) for the notational simplicity of this proof.
Show that the worst-case resilience of P M, `01 is tightly bounded.
Formally,

1
1
∀N ∀α α + < N + ∧ α − < N − =⇒
2
2
∀D̂∀D̂ α ∀ĥ α , V (P M, `01 |N , α) ≤


N + −1
+
− +
© min 2α + α , α + 2
max ­­
,
N+
«


−
min α + + 2α − , α − + N 2−1 ªª
®® . (14)
®®
N−
¬¬
Note that the proof of Theorem 3 implies if α + < 12 N + and α − <
1 −
2 N , then P M, `01 is feasible.
(bounded) First, we prove that the worst-case resilience of
P M, `01 is bounded. The optimality of ĥ α with Lemma B.1 implies
the following:
R̄(ĥ α |D̂ α+ ) + R̄(ĥ α |D̂ α− ) ≤ R̄(h ∗ |D̂ α+ ) + R̄(h ∗ |D̂ α− ) − k
R̄(ĥ α |D̂ α+ ) ≤ R̄(h ∗ |D̂ α+ ) + R̄(h ∗ |D̂ α− ) − k
− R̄(ĥ α |D̂ α− )
≤ R̄(h ∗ |D̂ α+ ) + R̄(h ∗ |D̂ α− ) − k
= R̄(h ∗ |D̂ α+ ) − R̄(h ∗ |D̂ + )
+ R̄(h ∗ |D̂ α− ) − R̄(h ∗ |D̂ − ) − k
≤ α + + α − − k,
where k is a slack variable to satisfy the majority constraint such
+
that α + + α − − k ≤ N 2−1 .
+
If α + + α − ≤ N 2−1 , k = 0 maximizes R̄(ĥ α |D̂ α+ ). Thus,
R̄(ĥ α | D̂ + ) ≤ R̄(ĥ α |D̂ α+ ) + α +
≤ 2α + + α − .

(15)

N + −1

If α + + α − > 2 , k can be the smallest non-zero scalar such
+
that α + + α − − k ≤ N 2−1 . Thus,
R̄(ĥ α | D̂ + ) ≤ R̄(ĥ α |D̂ α+ ) + α +
≤ α+ +

N+ − 1
.
2

(16)

From the above two cases,


+
min 2α + + α − , α + + N 2−1
R̂(ĥ α |D̂ + ) ≤
.
N+

(17)

Likewise,


−
min α + + 2α − , α − + N 2−1
R̂(ĥ α |D̂ − ) ≤
.
N−
Therefore, for all N , α, D̂, D̂ α , and ĥ α , Equation (14) is true.

(18)

Resilient Linear Classification

ICCPS, April 2017, Pittsburgh, PA USA

C

ĥ α
N + − 2α + − α − + k

N + − 2α + − α − + k
2α + + α − − k

N−

2α + + α − − k

N−

h∗

(b) D̂ and ĥ α

(a) D̂ and h ∗

Figure 8: An example of D̂ for proving on the worst-case
tight resilience bound of Theorem 4.

PROOF ON MIXED-INTEGER LINEAR
PROGRAM FOR 0-1 LINEAR
CLASSIFICATION

In this section, we derive Mixed-Integer Linear Program (MILP)
for 0-1 linear classification algorithm from the standard 0-1 linear
classification problem.
Proof. The 0-1 linear classification problem is minimizing the
misclassification error of a classifier over training data, or equivalently the sum of a 0-1 loss of a classifier over each training data
pairs, according to
Õ

min
1{yi , sign h>x i }.
h

R̄(ĥ α | D̂ α ) = α + + α − − k

α−

−α +

−α −

h,z

α+

Figure 9: An example of D̂ α for proving on the worst-case
tight resilience bound of Theorem 4.
(tight) Next, we prove that the worst-case resilience bound is
tight. To prove the tightness, we show there exist D̂, D̂ α , and ĥ α
by which the equality of Equation (14) holds for all N and α if h is
linear, α + < 12 N + , and α − < 12 N − .
The examples of D̂, h ∗ , and ĥ α are illustrated on Figure 8. Figure 8a shows D̂ and the corresponding optimal classifier h ∗ . Figure 8b shows D̂ and the projected optimal classifier ĥ α trained over
D̂ α . Figure 9 represents D̂ α from which ĥ α is obtained. Note that
the annotated number of positive and negative feature vectors are
the difference from the original numbers in Figure 8; i.e., the blue
dot has N + − 2α + − α − + k number of positive feature vectors as
originally denoted and the red dot has N − − α − number of negative
feature vectors.
If α + + α − ≤ 12 (N + − 1), let k = 0. There are 16 different
linear classifiers that separate five dots in Figure 9. Each classifier
has an empirical risk, R̄(·), among α + + α − , 2α + + α − , 2α + + 2α −
or is infeasible due to the majority constraint. Thus, ĥ α can be
optimal. From this, R̄(ĥ α | D̂ + ) = 2α + + α − that satisfies the equality
in Equation (15). Likewise, we can find D̂, D̂ α , and ĥ α such that
R̄(ĥ α |D̂ − ) = α + + 2α − .
If α + + α − > 12 (N + − 1), let k = α + + α − − 12 (N + − 1). There are
16 different linear classifiers that separate 5 dots in Figure 9. Each
classifier has an empirical risk, R̄(·), among α + + α − − k, α + + α − ,
2α + + α − − k, 2α + + 2α − − k or is infeasible due to the majority
constraint. Thus, ĥ α can be optimal. From this, R̄(ĥ α |D̂ + ) = α + +
1 (N + − 1) that satisfies the equality in Equation (16). Likewise, we
2
can find D̂, D̂ α , and ĥ α such that R̄(ĥ α |D̂ − ) = α − + 12 (N − − 1).
Therefore, for all N and α such that α + < 12 N + and α − < 12 N − ,
there exist D̂, D̂ α , and ĥ α that make the equalities in Equation (17)
and Equation (18) hold.


i

We introduce new binary variable zi ∈  {0, 1} such that zi =
1{yi h>x i ≤ 0}. Since 1{yi , sign h>x i } = 1{yi h>x i ≤ 0}
assuming sign(0) = 0, sign(x) = 1 if x > 0, and sign(x) = −1 if
x < 0, the equivalent problem (by introducing equality constraints)
is as follows:
Õ
min
zi
i

s.t. ∀i, zi = 1{yi h >x i ≤ 0}.
Next, we introduce new variables ei ∈ R to convert the indicator
function into a real-valued function. The equivalent problem is as
follows:
Õ
min
zi
h,e,z

i

s.t. ∀i, ei = 1{yi h >x i ≤ 0}, −zi ≤ ei ≤ zi .
This problem is equivalent to the previous one since the optimal
values zi∗ are identical. Specifically, if there are i such that yi h >x i ≤
0 for some h, then zi∗ = 1 in the previous problem if and only if
ei = 1 and zi∗ = 1 in this problem. Likewise, if there are i such that
yi h >x i > 0 for some h, then zi∗ = 0 in the previous problem if and
only if ei = 0 and zi∗ = 0 in this problem. Thus, zi∗ = z̄i for all i.
To remove the indicator function, we introduce new slack variable c i ∈ R. Also, let |yi h >x i | ≤ δ , assuming δ ∈ R is sufficiently
large. The equivalent problem is as follows:
Õ
min
zi
h,e,z,c

i

s.t. ∀i, ei = c i − yi h >x i ,
− (δ + ϵ)zi ≤ ei ≤ (δ + ϵ)zi , c i > 0,
where ϵ > 0 is a sufficiently small value. To prove the equivalence,
check whether the optimal solution zi∗ of the previous problem and
this problem are same. Let zi∗ and z̄i be the optimal solution of
the previous and this problem, respectively. If there are i such that
yi h >x i ≤ 0 for some h, then ei = 1 and zi∗ = 1 in the previous
problem, and c i = ϵ, ei > ϵ, and z̄i = 1 are optimal solutions in this
problem, resulting zi∗ = z̄i . If there are i such that yi h >x i > 0 for
some h, ei = 1 and zi∗ = 1 in the previous problem, and c i = yi h >x i ,
ei = 0, and z̄i = 0 are optimal solutions in this problem, resulting
zi∗ = z̄i . Thus, zi∗ = z̄i for all i.

ICCPS, April 2017, Pittsburgh, PA USA
To reduce the number of optimization parameters, we consider
the following problem:
Õ
min
zi
h,e,z,c

i

s.t. ∀i, ei ≥ c − yi h >x i ,
− (δ + ϵ)zi ≤ ei ≤ (δ + ϵ)zi , c > 0.
The previous problem and this problem are equivalent since the
optimal solution on zi for both problems are same. Specifically,
let zi∗ and z̄i are the optimal solution of the previous and this
problem, respectively. First, assume zi∗ = 1. This implies ei , 0
and yi h >x i ≤ 0. Since, in this problem, yi h >x i ≤ 0 implies ei > 0,
z̄i = 1. Likewise, z̄i = 1 implies zi∗ = 1. Next, assume zi∗ = 0. This
implies ei = 0 and yi h >x i > 0. In this problem, yi h >x i > 0 implies

Sangdon Park, James Weimer, and Insup Lee
ei = 0 or ei = 1. Thus, z̄i = 0. Likewise, z̄i = 0 implies zi∗ = 0.
Therefore, z̄i = zi∗ .
Finally, if each constraints are divided by c, then we have the
following MILP.
Õ
min
zi
h,e,z,c

i

ei
h>
≥ 1 − yi
xi ,
c
c
ei
δ +ϵ
δ +ϵ
zi ≤
≤
zi ,
−
c
c
c

s.t. ∀i,

and if let ei0 = eci , h 0 = hc , and δ 0 = δ +ϵ
c , the final MILP is obtained.


