ZUbers against ZLyfts Apocalypse: An Analysis Frameworkfor DoS Attacks on Mobility-as-a-Service Systems
Chenyang Yuan ∗Jérôme Thai *Alexandre M. Bayen
Department of Electrical Engineering and Computer Sciences
University of California, Berkeley, CA{chenyang.yuan, jerome.thai, bayen}@berkeley.edu
ABSTRACTThe vulnerability of Mobility-as-a-Service (MaaS) systems to Denial-of-Service (DoS) attacks is studied. We
use a queuing-theoretical framework to model the redispatch process used by operators to maintain a highservice availability, as well as potential cyber-attacks
on this process. It encompasses a customer arrival rate
model at different sections of an urban area to pick up
vehicles to travel within the network. Expanding this rebalance model, we analyze DoS cyber-attacks of MaaS
systems by controlling a fraction of the cars maliciously
through fake reservations (so called Zombies) placed in
the system (similar to the computer science field wherea Zombie is a computer that a remote attacker has accessed for malicious purpose). The attacker can thenuse the block-coordinate descent algorithm proposed in
the present work to derive optimal strategies to minimize the efficiency of the MaaS system, thereby allowing us to quantify the economic loss of such systems
under attack. The technique is shown to work well andenables us to arbitrarily deplete taxi availabilities basedon the attacker’s choice and the radius of attacks, which
is demonstrated by drawing a “Cal” logo in Manhattan. Finally, a cost-benefit analysis from 75 million taxi
trips shows diminishing returns for the attacker and thatcountermeasures raising the attack cost to more than
$15 protect MaaS systems in NYC from Zombies.

1.

INTRODUCTION

In recent years, the rapid expansion of Mobility-asa-Service (MaaS) systems such as ride-sharing services∗

These two authors contributed equally.

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
Copyright 200X ACM X-XXXXX-XX-X/XX/XX ...$5.00.

and (electric) car rental programs triggered research on
the optimal management of such systems: optimal dispatch [9], optimal fleet size [5], general design [18], andoptimal re-balancing algorithms [21] to achieve the current level of performance of MaaS systems. The necessary central coordination of the dispatch of vehicles canbe seen as re-balancing the network and it can be done
manually as commonly done by taxi companies with human dispatchers, by apps such as taxi hailing apps, orby incentivization from the two-sided markets formedby ride-sharing companies such as Uber or Lyft.
However, the cyber-physical nature of MaaS systems
makes them vulnerable to physical attacks from malicious drivers, cyber attacks on the hailing apps, andeconomic attacks by controlling the two-sided markets.
These DoS attacks can re-route a fraction of vehicles
to reduce the time usage of the network and decrease
the profits for the MaaS company. Hence, the security of this type of cyber-physical systems has gained alot of attention recently [2]. While there have been research on the security of general networks [14, 22], withapplications to power systems [17, 20], communication
systems [1, 19], and freeway control [15], this work isamongst the first to study their security against cyberattacks on MaaS systems, and understand the extent of
attacks that can be performed on them.
Expanding an established framework on MaaS systems, attacks can be seen as malicious agents controlling the vehicles of the MaaS system, which we will referto as Zombie passengers. When they are serviced byreal cars, e.g. Uber or Lyft, these cars become Zombified, i.e. a ZUber or a ZLyft (similar attacks involving one company calling and canceling vehicles of theother have happened in the past [16]).The term Zombie is used following computer science terminology for
a computer that has been compromised remotely by ahacker to launch DoS attacks. Our main contributionsin this article include: (i) a framework for the study ofcyber-security in MaaS systems encompassing different
features, e.g. attack budget and radius, (ii) designing a
block-coordinate descent algorithm to optimize attacks,

Type

rate

routing

contribution

customerbalancer
Zombie

φi
ψi
νi

αij
βij
κij

MAS model [5]re-balancing [21]cyber-security

Table 1: Summary of Models
Different types of passenger with their arrival rates,
routing probabilities, and the authors who introduced
them.
(iii) a case study in NYC showing the extent of damage we can do with our attacks using a model generated
from 75 million real taxi trips. This framework will ultimately be usable to compute the optimal attack pricepoint of an attacker, hence helping cab companies to adjust their cancellation fees to protect themselves against
such attacks.

2.

A QUEUING-THEORETICAL MODEL

We consider a MaaS system in an urban area divided
into N small sections (typically spanning 2 or 3 city
blocks) indexed by i ∈ S. We assume that M vehicles
provide service to customers between pairs of sections(i, j) ∈ S ×S. Next we describe previous models for customer travel and balancing mechanisms on the network.
Finally, we introduce our model for Zombies. Table 1
summarizes these three models.

2.1

Model Description

Customer model: Customers arrive at each section
i following a time-invariant Poisson process with rate
φi > 0. Upon arrival at a section i, a customer chooses
toP go to section j 6= i with probability αij ≥ 0, wherej∈S αij = 1 and αii = 0 for all i ∈ S. Furthermore, if
a vehicle is not available at a section upon arrival of acustomer, the customer leaves without service (i.e. customers do not queue). The model also assumes that
there is sufficient capacity for vehicle to queue for passengers, as is often the case of pickup locations or taxi
stations. The travel times for different passengers traveling from section i to section j constitute an independently and identically distributed (i.i.d.) sequence of
exponentially distributed random variables with mean
Tij > 0. This model was used in [5] to describe a vehicle
rental company as a queuing network.
Re-balancing process: In any MaaS systems, there
is a need for re-balancing to account for uneven demand.
A re-balancing vehicle is one traveling to a destination
without customers to fulfill the demand at its destination. The process has been studied extensively [9,11, 21] and we use the framework of [21] to model itwith balancers driving these re-balancing vehicles. This

paradigm is analogous to the MaaS company “spoofing” its own drivers for re-balancing purposes. In [21],each section i generates balancers according to a Poissonprocess with rate ψi ≥ 0 and routes thesePbalancers tosection j 6= i with probability βij , where j∈S βij = 1
and βii = 0 for all i ∈ S. The re-balancing process is
assumed to be independent from the customer arrival
process. The model also supposes that the balancer islost if there is no car at the section upon its generation.
Cyber-security: We extend the re-balancing workof [21] for the purpose of cyber-security analysis. We
assume the attacker can generate malicious agents or
Zombies at each section i following a Poisson processwith rate νi ≥ 0 and routePthem to section j 6= i withprobability κij ≥ 0, where j∈S κij = 1 and κii = 0 for
all i ∈ S. We assume that the re-balancing policy does
not detect the attacks and its parameters ψi and βij
only depend on the customers’ demand φi and αij . We
also define the radius r of an attack, which is the furthest (Manhattan or `1 ) distance that a Zombie can berouted through. This captures the fact that the attacker
has a weaker control over the network than customers.
For example, if the attacker targets a ride-sharing company by making a call and then canceling, only nearby
vehicles will be dispatched and affected. Hence we define E the set of pairs (i, j) ∈ S × S such that routing
is allowed from i to j. In other words, denoting 1A the
indicator function of event A, we have the constraints
1{(i,j)∈E}/ κij = 0 ∀ i, j

2.2

(1)

Comments on the Model

Although travel times are in general not exponentiallydistributed, their distribution does not affect the predictive accuracy of similar queuing networks [7]. The customers’ routing probabilities αij reasonably constitutean irreducible Markov chain for dense environments,
and we do not consider congestion, even though it negatively affects the efficiency of the network and the effectof re-balancing.
Note that the“passenger loss”assumption in the model
where passengers not willing to wait (they leave thesection immediately when there are no taxis available) is
accurate in numerous US markets. This framework is agood setting for analyzing the benefits and vulnerabilityof MaaS systems: (i) with high service availability (themedian wait time for an Uber in major U.S. cities in2014 was under 4 min [12]), and (ii) competing against
other MaaS or alternate transportation systems (particularly in dense cities where the waiting time is critical).
The passenger loss model is particularly relevant in an
adversarial setting in which attacks aim at reducing service availability to incur passenger loss and encourage
passengers to use a rival system, similar to the reported
DoS attacks between Uber and Lyft [16]. From an an-alytical perspective, the passenger loss model considerably simplifies our model because customer arrivals at asection is equivalent to a virtual service to the vehicles
currently queuing (and available) at the section.
The re-balancing and attacks are respectively modeled
as balancers and Zombies following the same process
as customers (with passenger loss), but independently
and with different arrival rates and routing probabilities,
thus allowing to combine the customer demand, the rebalancing process, and the attacks into a single queuing
network. In our case, the loss of balancers and Zombies describe processes that encourage a re-allocation ofvehicles to sections but does not enforce it.
Another critical assumption is that there is no attackerdefender game (see [3]) since the re-balancing only aims
at high service availability given customers’ demand,and does not try to defend from possible attacks. Aninteresting extension would be the analysis of a onestage game in which the balancers moves first with theknowledge of the Zombies’ best response.

3.

NETWORK ANALYSIS

Following [5] and [21], the model described above canbe cast into a closed Jackson network, which we now
present with a cyber-attack extension.

3.1

Jackson Network ModelIn the present work, we combine the customer, balancer, and Zombie processes. From the superposition of
independent Poisson processes, the total arrival processof all three types of passengers is Poisson with rate
λi = φi + ψi + νi(2)where φi , ψi , and νi respectively represent the arrival
rates of customers, balancers, and Zombies. A generalized passenger that arrives will either be classified
as one of the three classes with respective probabilities φi /λi , ψi /λi , and νi /λi . The routing probability
rij := P(i → j) of a generalized passenger arriving atsection i to select a destination j is then given byXrij =P(i → j | class) P(class)
(3)
class

With αij , βij , and κij being the routing probabilities
associated to each class, we have (with λi given by (2)):
rij = αij

ψi
νi
φi
+ βij
+ κij
λi
λi
λi

(4)

Sections are modeled as single-server (SS) nodes (or“section” nodes) and the route between two sections as
infinite-server (IS) nodes (or “route” nodes). When ageneralized passenger arrives at a non-empty section, avehicle departs from that node to move to a route nodethat connect the origin to the destination selected by

Figure 1: Illustration on a three section network.
On the left, a passenger arrives at section 1 andpicks a car to go to section 2. The equivalentJackson network is shown on the right side.
that passenger. After spending an exponentially distributed amount of time at the route node (the traveltime), the vehicle moves to the destination section node(see Figure 1).
From a queuing perspective, if vehicles are present at
section i, they are processed with service rate λi givenby (2), and are routed to the IS (route) node between
sections i and j with probability rij given by (4). Thenvehicles at an IS node between sections i and j are processed in parallel (i.e. assuming infinite capacity roads
with no congestion effects) with service rate 1/Tij eachand move to SS node i with probability 1. Hence, theMAS system is modeled as a closed Jackson networkwith respect to the vehicles with vehicle service rate
µn (xn ) at a generalized node n given by(λi
if n = section iµn (xn ) =(5)
xn /Tij if n = route i → jwhere xn ∈ {0, 1, · · · , M } is the number of vehicles at
node n (and M the number of vehicles in the network).
Note that µn only depends on xn on a route node. The
routing probability pnn0 from node n to node n0 is0rij if n = section i, n = route i → j
pnn0 = 1
if n = route i → j, n0 = section j (6)0otherwise

3.2

Asymptotic Behavior and Fairness

A quantity of interest is the availability, which is defined as the percentage of customers who find a vehicle
available at a section upon arrival. Mathematically, it is

S
M
Tij
φi , αij
ψi , βij
νi , κij
Ai (M )ai
1A

If the MaaS company gets a constant amount per ride,the attacker wants to maximize customer loss, i.e. minimize the customers picking a vehicle:
Xmin
φi Ai (M )(9)

Set of SS (section) nodes, |S| = N
Fleet size of the MaaS system
Mean travel time from i ∈ S to j ∈ S
Customer arrival rate and routing matrix
Balancer arrival rate and routing matrix
Zombie arrival rate and routing prob.
Prob. of i ∈ S of having ≥ 1 vehicle
asymptotic availability, γi /maxj∈S γjindicator function of condition A

i∈S

If the MaaS system gets an amount that is proportional
to the length of the ride, a more harmful objective isXminφi αij Tij Ai (M )
(10)
i,j∈S

Table 2: Summary of notations
given by the following steady-state probability (see [8]):Ai (M ) := P(Xi ≥ 1) =γi G(M − 1)
G(M )

(7)

where the random variable Xi represent the queue length
at section i ∈ S. Note that the quantity G(M ) aboveis the normalization factor associated to the equilibrium
state distribution of the queue lengths {Xi }i∈S provided
by the Gordon-Newell theorem [6]. The computation ofG(M) is very expensivewith complexity that grows as|N | + M − 1, where |N | is the cardinality of N (i.e.,|N |the number of nodes in the network), so that |N | = N 2 .
Hence, we want to obtain performance metrics without
computing explicitly the quantity G(M ), e.g. by studying the asymptotic behavior of the network when the
fleet size M goes to infinity. The following result from[13] gives the asymptotic availability at a SS node i:γiai := lim Ai (M ) =(8)M →∞maxj∈S γjwhere maxj∈S γj is the highest relative utilization. Hence,
when M approaches infinity, sections with the highest
relative utilization can have availability arbitrarily close
to 1, while other sections have availability strictly lessthan 1, since in this case γi < maxj∈S γj ).
To cancel this effect, Zhang and Pavone [21] designed
a re-balancing policy with balancer arrival rates ψi androuting βij that maintain fairness in the network, i.e.
γi = γj for all i, j ∈ S. When M is goes to infinity, thismeans that the availability of all sections goes to 1 since
γi = maxj∈S γj for all i ∈ S. In addition to imposing
fairness, they minimize the numberof re-balancing veP
hicles given by the quantity i,j∈S Tij βij ψi .

hence the total time usage for the customers is minimized. Both objectives have general formXminwi Ai (M )
(11)
i∈S

where wi > 0 are some user-defined arbitrary weights.
To avoid computing G(M ) due to the complexity, theavailabilities Ai (M ) are normalized with maxj∈S γj andconsequently study the availability Ai (M ) when the fleet
size M goes to ∞ (see (8))
X
X
γi
= min
wi ai
(12)
min
wi
maxj∈S γji∈Si∈S

Finally, there must be one i ∈ S such that ai = 1, hence
the objective is equivalent to finding the index k suchthat ak is set to 1 and minimizing over the remaining
quantities {ai }i6=k




X
wi ai
(13)
min wk · 1 + mink∈S {ai }i6=k
i6=kHence, we can solve |S| = N programs and select theone with the minimum objective value.

4.2

Attack Budget

The most important constraints are the traffic equations of the Jackson network. Using Lemmas 4.1 and
4.2 in [21], they can be written in terms of SS (section)
nodes and asymptotic utilization aiX(φi +ψi +νi )ai =(αji φj +βji ψj +κji νj )aj , ∀ i (14)j∈S

Let k ∈ S such that ak = 1, then the constraint isX
φk + ψk + νk =(αjk φj + βjk ψj + κjk νj )aj (15)j∈S

4.

OPTIMAL ATTACK PROBLEM

The contributions of the present article encompass theobjectives of an attacker into an optimization framework, which we solve very efficiently.

4.1

Maximizing Passenger Loss

Note that the constraint (15) is redundant since summing the constraints (14) for i 6= k (with ak = 1)
gives (15). Furthermore, the attacker injects Zombies
with arrival rates νi and routing matrix κij to achieve(13). With no restriction on the attack rates, setting
νi = ν > 0 for all i 6= k and routing all the Zombies tosection k with probability 1 gives, using (15)X
aj ≤ (φk + ψk + νk )/ν → 0 when ν → +∞j6=kThen the positive utilizations ai go to 0 for all i 6= k andthe problem is reduced to mink∈S wk . A more realistic
problem is setting a limited budget b for the attacks
Xνi ≤ b
(16)
i∈S

4.3

Formulation

We suppose the customers’ and balancers’ demands
are given, and define their combined rate and routing
probabilities as
ϕi := φi + ψi(17)δij := (αij φi + βij ψi )/(φi + ψi )(18)

and so the combined routing probabilities rij of the customers, balancers, and Zombies given in (4) can be expressed as follows
rij =δji ϕj + κji νjϕi + νi∀ i, j ∈ S(19)Given k ∈ S such that ak = 1, the Optimal Attack Problem (OAP) consists in manipulating the Zombie arrival
rates νi and routing κij probabilities such that:
X
pX 2
min
wi ai +
ν(20)
κij ,νi ,ai
2 i i
i6=k

X δji ϕj + κji νjaj ∀ i ∈ S \ {k} (21)ϕi + νij∈SX
κij ≥ 0,
κij = 1, 1{(i,j)∈E}/ κij = 0 (22)s.t. ai =jνi ≥ 0,X

νi ≤ b

(23)

i

Note
that we have included a `2 -regularization termp P2
νi i in our objective. It compensates for the budget2
constraint (23) which is known to encourage sparsity [4]in the entries νi . Sparsity allocates most of the budget b to a few sections i, resulting in very high attack
rates, which is unrealistic in practice because of limitations inherent to the physical nature of the MaaS, e.g.
bounded fleet size, limited capacity of streets. Hence,the `2 -regularization captures these physical limitations.
We have also included the ai in the decision variables
since they vary. In fact, the ai are function of κij , νiand can be written directly as ai (κ, ν).

Name

Fix

Vary

Attack Routing Pb.
Min. Attack Pb.
Attack Rate Pb.

νi
ai
κij

ai , κijκij , νiνi , aiTable 3: Summary of three-step algorithm
Proof. By assumption, the probabilities αij constitute an irreducible Markov chain. By equation (4), theprobabilities rij lead to an irreducible Markov chain as
well. The {ai }i vector satisfying equations (21) is proportional to the steady state distribution for the transition probabilities {rij }ij and by the Perron-Frobenius
theorem, it is positive [10]. Finally, the constraint ak =1 completely fixes the vector {ai }i .

4.4

ai > 0 for all i ∈ S(24)

ai is uniquely defined for all i ∈ S(25)Block-coordinate Descent

The above optimization program is non-convex andis difficult to solve numerically. Specifically, the vector{ai }i∈S is a function of κij , νi from Lemma 1, hence thegradient of the objective is given byXwi ({∂νi al }i , ∂κij al i,j ) + p({νi }i , {0}i,j ) (26)l6=kwhere each the partial derivative of ai satisfies a set of
N − 1 linear equations obtained by differentiating thebalance constraints (21). Hence, computing the gradient prohibitively requires to solve N 2 linear programsof dimension N − 1 by differentiating the constraints(21). The total complexity for computing the gradient is (N 2 − N )2 ≥ (N − 1)4 . Our of our main contributions is the design of a tractable block-coordinate
descent algorithm to solve the above problem, where
each sub-problem is summarized in Table 3. We pose
the Minimum Attack Problem (MAP) and the Attack
Routing Problem (ARoP) and show that they can be
re-formulated as a quadratic and a linear program respectively with N 2 non-negative variables and N constraints. Using an efficient solver, CPLEX, we solve the
MAP and ARoP efficiently. The Attack Rate Problem(ARaP) has N variables which are {νi }i∈S and can besolved efficiently using a projected gradient descent algorithm. The gradient computation requires solving N
linear programs of dimension N − 1, hence an O(N 3 )complexity that is tractable. We also note that the
ARoP, MAP, and ARaP can be interpreted as specificattack scenarios in their own right.

5.

Lemma 1. For any attack strategies νi and κij :MinimizeP
Pi w2i ai
Pi νi
p P
2
i νi
i wi ai + 2

A TAXONOMY OF ATTACKSIn this section, our contribution is proposing a taxonomy of attack scenarios described by the ARoP, MAP,
and ARaP (in addition to the OAP). In each scenario,

the attacker is given a fixed allocation of either the availabilities ai , the attack rates νi , or the attack routing
κij , and he wants to allocate the two other types of “recources” optimally to harm the system. We also describe
how each one of these programs fits into the proposed
block-coordinate descent algorithm.

5.1

Attack Routing Problem (ARoP)

In this scenario, the attacker can only inject attacks
with fixed rates. For example, the attacker has placed
devices at different sections i ∈ S that remotely spoof
the hailing apps of nearby vehicles, to send them tospecific locations. Hence, given νi , the attacker wants
to optimize the routing to achieve objective (13). Thisis the Attack Routing Problem (ARoP), which can be
re-formulated as a Linear Program from this lemma
Theorem 1. Let us consider the following linear program (LARoP)X
minwi yij
(27)
yij

ij

X
X
s.t.
(λi yij − νj yji ) =δji ϕj yjl
j6=i

yij ≥ 0,∀ i 6= kykj = 1(29)?
Let yij
be an optimal solution to LARoP. Then, an optimal solution of the ARoP is
X
?
ai =
yij
(30)
j6=i

(31)

Proof. We can obtain LARoP from the OAP byfixing νi and making the change of variables yij := κij ai
to equations (20) – P(22).
We decrease the i6=k wi ai part of the objective of
the OAP with respect to ai , κij by solving the above
program efficiently with CPLEX, as part of our blockcoordinate descent algorithm.

5.2∀j ∈ S(32)

where D is a diagonal matrix with entries {ϕi + νi }i6=k ,M = {φj δji + νj κji }i6=k,j6=k , and vj ∈ RN −1 for j ∈ S
are vectors with entries {aj (κji − 1{i=j} )}i6=k where 1A
is the indicator function of event A.
Solving the above N systems of N −1 linear equations
gives the Jacobian of {ai }i6=k . Hence we can solve the
ARaP with the projected gradient descent algorithm,
where g is the gradient of the objective:{νi }i∈S :=Π ({νi }i∈S − t g)Xg :=(∂ai /∂νj )j∈S + p(νj )j∈S

(33)
(34)

i6=k

where t > 0 is the step size and Π is the projection
ontoPthe `1 -ball of radius b, i.e. {x ∈ RS≥0 :
x
≤
b}.
i
i∈S
We use the O(N log N ) implementation
describedin[4].
√
We use a step size decreasing in 1/ n where n is thenumber of iterations and complement it with a simple
line search to have a lower objective at each iteration.

5.3

j6=k

?
κij = yij/ai

(D − M ) xj = vj

(28)

j>l

X

j ∈ S that satisfy

Attack Rate Problem (ARaP)In this scenario, the attacker hacks the apps of thevehicles to display “ghost” demands at specific sections
i. With fixed routing κij , the attack rates νi are chosen to achieve objective (20). The Attack Rate Problem(ARaP) consists in optimizing the OAP with respect tothe rates νi for all i and the asymptotic availabilities
ai for i 6= k, while
P the routing of attacks κij are fixed.
Since the sum i6=k wi ai is a function of the νi , we compute the Jacobian matrix of the vector {ai }i6=k , which
is given by the following:
Lemma 2. The Jacobian matrix (∂ai /∂νj )i6=k,j∈S ofdimension (N − 1) × N has columns xj ∈ RN −1 for

Minimum Attack Problem (MAP)

We consider a scenario in which the attacker wants
to achieve target availabilities ai at each station in the
networkP 2 with the minimum quadratic cost of attacks
1i νi . Given a target of fixed positive availabilities
2
ai for each section, the attacker instead minimizes thecost of such attacks. The Minimum Attack Problem(MAP) can be formulated as follows
1X 2
min
νi
(35)
κij ,νi 2
i
X δji ϕj + κji νjs.t. ai =aj ∀ i ∈ S \ {k} (36)ϕi + νij∈SX
κij ≥ 0,
κij = 1, 1{(i,j)∈E}(37)/ κij = 0jνi ≥ 0∀i ∈ S(38)

The constraints can be formulated as flow constraints
Theorem 2. Let us defineXsi := ai ϕi −aj δji ϕj∀i ∈ S(39)

j6=i

and consider the following Quadratic Program

2
X
X 1

min
xij 
xij
2a2i
j
i
X
s.t.
(xji − xij ) = si∀i ∈ S

(40)
(41)

j6=i

xij ≥ 01{(i,j)∈E}/ xij = 0

∀ i, j ∈ S(42)This is always feasible. Let x?ij be an optimal solution
to it. Then, an optimal solution to the MAP is:Xνi =x?ij /ai
(43)
j6=i

(
κij =

x?ij /(νi ai )P
1/ j 1{(i,j)∈E}

if νi > 0otherwise(44)

Proof. We apply the following change of variables
xij := νi κij ai∀ i, j(45)

which converts the MAP into P
the above program with{si }i∈S given by (39) and νi = j6=i xij /ai as a result of
the change of variable. Note that xij can be interpreted
as the rate of attack from station i to j. This problem isfeasible because the capacity on each edge is unbounded
and the source flows sum to 0:
X
X
X
si =
ai ϕi −aj δji ϕi = 0
(46)
i

i

i,j6=i

Therefore, we can find the minimal-cost attacks that
achieve any arbitrary availabilities.
Within the proposed block-coordinate descent framework, we add the budget constraint (23) to the MAP
using the solution of the previous step as initial solution, and solve it efficiently using CPLEX. Note thatthe objective of the above program can be generalized
to any convex function, and a linear objective results ina min-cost-flow problem (MCFP). This reduction to a
MCFP was shown in [21] for the purpose of re-balancing
vehicles with an objective minimizing the number of rebalancing tripsXminψi Tij βij(47)
ψi , βij

i,jwhere ψi , βij are the balancers arrival rates and routing
probabilities respectively. In our case, the MAP stepof our algorithm redistributes the highest attack rates
among sections, thus avoiding numerical corner cases
associated to the sparsity promoting constraint (23).

6.

APPLICATION TO NYC TAXI SYSTEM

We illustrate the results on a data set comprising 1.1
billion trips gathered since Yellow Taxis’ digital trip
record began, from January 2009 to June 2015. We
infer the parameters for the queueing theoretic model
described in (5) and (6) from these trips. This data
is provided by the New York City Taxi and Limousine
Commission and includes pickup and drop-off locations,trip time, and fare for each trip.
We divide midtown and downtown Manhattan into
531 square sections using a grid that is aligned with theroad layout of Manhattan, each section serving a region
1-2-block wide. Only grid squares with a significant

arrival rate are considered. This results in a Jackson
network with more than 282,000 nodes when road nodes
between each pair of sections are included. Then weuse all 75 million trips originating during the weekday
evening peak period from 5-7pm to infer the parameters
for the queueing model φi and Tij via the sample mean,and αij via Laplacian smoothing. In the process, wechecked that φi closely follows a Poisson distribution,
validating our assumption about customer arrivals. The
customer arrival rate is about 10,600 per hour and there
are about 2,500 taxis in the network in this time period.

6.1

Experiment 1: Controlling Availabilities

In this experiment, given any arbitrary set of availabilities ai , we find the minimal cost of attacks needed tocontrol the network such that the resulting availabilities
match the provided ones. To illustrate this we show that
we can create arbitrary availability patterns in the city,in particular the “Cal” logo, see Figure 2a. An optimal
control is obtained by solving the MAP (i.e. the second
step in our block-coordinate descent algorithm
P to solve
the OAP), but with a linear objective min i νi , resulting in a linear program. We proceed with the simulation
by first balancing the network (assuming that real MaaS
have high service availability) using the methodology of[21], i.e. solving the MAP with the availabilities uniformly equal to 1 and with a linear objective of theform (47). This yields a total rate of 2,200 re-balancing
vehicles per hour. We then compute the attack strategy
on the balanced network. When the attacking radius isunlimited, injecting 800 Zombies per hour achieves theavailability pattern encoded in the “Cal” logo.
Next, we decrease the radius of attacks by limiting therouting from a section i to values between 1 and 15 interms of Manhattan distance (or `1 with a section block
as a unit of length), and find the minimum attacks rate
needed to create the “Cal” logo, as illustrated by Figures
2. Figures 2b-c show the optimal attack strategies interms of the rates and routing directions, and Figure 2d
the minimal attack rates as a decreasing function of theradius, see Figure 2 for more details.

6.2

Experiment 2: Minimizing Availabilities

In this experiment, we solve the OAP on the Jackson network model learned from the NYC taxi trips
data. To avoid numerical difficulties related to the verylarge disparity in customer arrival rates at the different sections (the squares close to Grand Central station having customer arrival rates of 200 vehicles perhour while the sections along East river have one customer arrival every four hours on average between 5 and7pm), we cluster adjacent blocks together and aggregate
the arrival rates such that the minimum arrival rate at
a section is 30 customers per hour, resulting in a re-Figure 2: Effect of Radius of Attacks(a): Target availability pattern following a pixelated version of the “Cal” logo. (b) and (c): Best attack policy toachieve the target with maximum `1 -radius of 0.3km (1 block) and 2km (7 blocks) respectively: each arrow shows
the direction of the κij -weighted barycenter of the destination sections j from an origin i, and the color of eachsquare encodes the attack rate. (d): Total attack rate per hour needed to achieve the specified availabilities as afunction of radius. We can see that if we limit the radius of attacks to one block, as in (b), vehicles are routed
through many intermediate stations, whereas in (c), increasing the radius allows the attacker to remove cars fromregions with low availabilities (yellow in (a)) and send them directly to the borders of Manhattan. Hence, limiting
the attack radius to small values greatly hinders the attacks’ effectiveness, and increasing the radius past 1-2 km
does result in diminishing returns.
duction to 331 blocks. We then balance the network(due to the dispatching of vehicles in response to uneven demand) and apply the proposed block-coordinate
descent algorithm for solving the OAP with an objective(10) minimizing the customer time usage in the network.
The different steps are summarized in Algorithm 1.
Algorithm 1 Algorithm for solving the AOP.
1: choose arbitrary section k ∈ S.
2: initialize νi and κij
3: while stopping criteria not satisfied:
4:
update ai , κij via ARoP with νi fixed.
5:
update νi , κij via MAP with ai fixed.
6:
update ai , νi via ARaP with κij fixed.
7: return ai , νi , κij

We do not set a limit on the radius of attacks and apply the descent method for values of the budget b of at-tack rate in {100, 500, 1000, 1500, 2000, 2500, 3000, 5000,
7000, 10000} with the parameter p controlling the weightof the `2 -regularization equal to 0.1 for b ≤ 1000 and
0.01 otherwise. The total customer and balancer arrival
rates remains unchanged on the reduced network, with
10,600 and 2,200 vehicles per hour respectively, hence
the budget of attacks accounts for values from 0.8% to
44% of the total rate (all three types of passengers).
Initializing with uniform Zombies arrival rate throughout the network and uniform distributions for the routing probabilities, Algorithm 1 gives an attack strategy
that consistently send waves of Zombies to several spots
around the center of Manhattan, see Figure 3a and b. In
equilibrium, these target regions have high availabilities
while the rest of Manhattan has very low availabilities.
We can also see that the attacks are concentrated on one

Figure 3: Optimal Attack Rates and Routing(a) and (b): The attack rates and routing probabilities for a total budget of 2000 Zombies per hour are showed in thesame style as in Figure 2, with an unlimited radius and 3km (9 squares) radius respectively. (c): Passenger/financial
loss as a function of attacks from 10 simulations of the Jackson network (each one associated to a given budget anda strategy computed from the OAP). The vertical scale on the left shows the rate of passenger loss and the oneon the right the financial loss assuming that a passenger spends $10.75 on an average. The red line denotes theprice of attack (assuming $5/unit) against the budget. If 100% of the loss is gained by the attacker (from stealing
customers), then the red region is financially beneficial for the attacker. The red line shows that an attack costing$5/unit (its slope) incurs a maximum loss of $22,500/hour for the MaaS system. (d): Maximum financial loss for the
MaaS system as a function of the cost of one unit of attack, obtained from (c). A cost of attack above $15 protects
the system.
spot if the radius can be high, while the attacks concentrate on several different spots around Manhattan for a
low radius.

6.3

Experiment 3: Network Simulation

Solving for the attack rates using the OAP gives very
low objective values, with a loss of customer time usage
from 60% to 100%. This surprising efficiency is in fact
the asymptotic behavior of the system under attacks,
where most of the vehicles are blocked in the center region because the balancer process does not re-dispatch
the vehicles in other parts of the network in reaction
to the attacks. To account for the transient state sincecoordinated attacks can be seen as a malicious shockpropagating throughout the network, we run a simulation of the Jackson network used for our model to study
the effectiveness of our attack strategy, with 2500 taxis(average number of taxis in the area at the time of theday used for our parameter inference). We start froma closed network in equilibrium and introduce attacks.
For each queue in the simulation, customers, balancers

and Zombies arrive with our specified rates, and arelost when there are no vehicles in the queue. We thenrecord the number of customers lost for one hour andsubtract from this the base rate of loss when the network is balanced. This difference is the passenger lostfrom our attacks. Figure 3c and 3d show the results of
our analysis. Assuming that the cost of conducting an
attack is $5 (the cost of canceling an Uber ride) andthe gain of the attacker is $10.75 (the average cost ofa ride in the area estimated from our data-set), Figure
3c shows that it is not economical to attack with morethan 5000 Zombies per hour. From this, we can deducethat a cost of attack greater than $15 protects the MaaS
sytem against attacks.

7.

CONCLUSION

In this paper, we propose and implement a framework
to analyze DoS attacks on MaaS systems. We proposea tractable block-coordinate descent algorithm to compute attack strategies which are applied to the network
in Manhattan.

This framework can also be extended to more general
settings, such as helping MaaS companies control their
networks if they can predict demand, to intentionallyunbalance their network in anticipation of high demandin certain areas. In addition to this, MaaS companies
can use this model to defend themselves against such attacks, such as setting an appropriate price for cancelingrides.
This also opens up exciting avenues of future work.
We have largely ignored congestion effects on the network, one extension is to include these effects and design attacks that create congestion in critical parts ofthe city. We also assumed that the MaaS company does
not respond to the attacks, and it would be interesting
to model this as a attacker-defender game.

Acknowledgments
The authors would like to thank Cathy Wu and Ramtin
Pedarsani for insightful discussions on the problem.

8.

REFERENCES[1] S. Bohacek, J. P. Hespanha, J. Lee, C. Lim, and
K. Obraczka. Enhancing security via stochastic
routing. In Proc. of the 11th IEEE Int. Conf. on
Comput. Communications and Networks, May
2002.
[2] A. A. Cardenas, S. Amin, and S. Sastry. Securecontrol: Towards survivable cyber-physicalsystems. International Conference on Distributed
Computing Systems, 2008.
[3] L. A. Cox. Game Theory and Risk Analysis. Risk
Analysis, 29, 2009.
[4] J. Duchi, S. Gould, and D. Koller. Projected
subgradient methods for learning sparse gaussians.
Proceedings of the 24th Conference on Uncertainty
in Artificial Intelligence, 2008.
[5] D. K. George and C. H. Xia. Fleet-sizing andservice availability for a vehicle rental system via
closed queueing networks. European Journal ofOperational Research, 211(1):198–207, 2011.
[6] W. J. Gordon and G. F. Newell. Closed Queuing
Systems with Exponential Servers. Operations
Research, 15, 1967.
[7] R. C. Larson and A. R. Odoni. Urban operations
research. 1981.
[8] S. S. Lavenberg. Computer performance modelinghandbook. Elsevier, 1983.
[9] Z. Liao. Real-time taxi dispatching using Global
Positioning Systems. ACM, 46:81–83, 2003.
[10] C. D. Meyer. Matrix Analysis and Applied Linear
Algebra. Society for Industrial and Applied
Mathematics, 2000.

[11] F. Miao, S. Lin, S. Munir, J. A. Stankovic,
H. Huang, D. Zhang, T. He, and G. J. Pappas.
Taxi dispatch with real-time sensing data inmetropolitan areas ı̈£¡ a receding horizon control
approach. International Conference on
Cyber-Physical Systems, pages 100–109, 2015.
[12] P. Mosendz and H. Sender. EXCLUSIVE: Here’s
How Long It Takes to Get an Uber in U.S. Cities.
Newsweek, December 4 2014.
[13] R. R. Muntz and J. W. Wong. Asymptotic
properties of closed queueing network models. 8th
Annual Princeton Conference on Information
Sciences and Systems, pages 348–352, 1974.
[14] T. R. Nudell and A. Chakrabortty. Ensuring
Localizability of Node Attacks in Consensus
Networks via Feedback Graph Design. American
Control Conference, 2014.
[15] J. Reilly, S. Martin, M. Payer, and A. Bayen. On
Cybersecurity of Freeway Control Systems:
Analysis of Coordinated Ramp Metering Attacks.
Transportation Research, Part B, 2014.
[16] S. Rodriguez. Lyft vs. Uber: The battle between
the ridesharing rivals intensifies. Los Angeles
Times, September 26 2015.
[17] K. C. Sou, H. Sandberg, and K. H. Johansson.
Detection and Identification of Data Attacks inPower System. 2012 American Control
Conference, 2012.
[18] K. Spieser, K. Treleaven, R. Zhang, E. Frazzoli,
D. Morton, and M. Pavone. Toward a Systematic
Approach to the Design and Evaluation ofAutomated Mobility-on-Demand Systems. in
Gereon Meyer, Sven Beiker (editors). Road
Vehicle Automation, (Lecture Notes in Mobility),
Springer, 2014.
[19] A. Teixeira, D. Perez, H. Sandberg, and K. H.
Johansson. Attack Models and Scenarios for
Networked Control Systems. High Confidence
Networked Systems, 2012.
[20] J. Weimer, S. Kar, and K. H. Johansson.
Distributed Detection and Isolation of Topology
Attacks in Power Networks. HiCoNS, 2012.
[21] R. Zhang and M. Pavone. Control of robotic
mobility-on-demand systems: aqueueing-theoretical perspective. International
Journal of Robotics Research, 2015.
[22] B. Zhu, A. Joseph, and S. Sastry. Taxonomy ofCyber Attacks on SCADA Systems. Proceedings of
CPSCom 2011: The 4th IEEE International
Conference on Cyber, Physical and Social
Computing, 2011.