1

Resiliency of Mobility-as-a-Service Systems to
Denial-of-Service Attacks
Jérôme Thai1 and Chenyang Yuan1 and Alexandre M. Bayen1,2

Abstract
Mobility-as-a-Service (MaaS) systems such as ride sharing services have expanded very quickly overthe past years. However, the popularity of MaaS systems make them increasingly vulnerable to Denialof-Service (DOS) attacks, in which attackers attempt to disrupt the system to make it unavailable to thecustomers. Such attacks have already occurred: Uber and Lyft claiming to have canceled thousandsof rides between each other [10], [23], and hackers suggesting how to control a fleet of 471,000
internet-connected vehicles [17]. Such attacks have real-world physical consequences. Expanding on
an established queuing-theoretical model for MaaS systems, attacks are modeled as a malicious control
of a fraction of vehicles in the network. We then formulate a stochastic control problem that maximizes
the passenger loss in the network, and solve it as a sequence of linear and quadratic programs. Combinedwith an economic model of supply and demand for attacks, we quantify how raising the cost of
attacks (such as increasing ride cancellation fees, higher level of security of the cyber components, andbetter fraud detection by law enforcement agencies) removes economical incentives for DoS attacks.
Calibrating the model on 1B taxi rides, we dynamically simulate a system under attack and estimate thepassenger loss under different scenarios, such as arbitrarily depleting taxis or maximizing the passenger
loss. Cost of attacks of $15 protects the MaaS system against DoS attacks. The contributions is thus at
the same time in the analytical work which enabled the modeling and analysis of the network, and thepractical conclusions in terms of financial countermeasures to counteract the attacks.

I. I NTRODUCTION
A. Motivation
Mobility-as-a-Service (MaaS) systems such as ride-sharing services and (electric) car rental
programs have expanding very quickly over the past years. The statistics are staggering: Uber
1

Department of Electrical Engineering and Computer Sciences, University of California at Berkeley. {chenyang.yuan,

jerome.thai, bayen}@berkeley.edu
2

Department of Civil and Environmental Engineering, University of California at Berkeley.

2launched in more than 120 cities worldwide [19], facing competition in the U.S. from Lyft which
operates in 60 cities [47] and in China from Didi Kuaidi which raised $1.2B [44]. An analysis of
the New York City Taxi & Limousine Commission (NYC TLC) data from January 2009 throughJune 2015 and Uber data (see https://github.com/toddwschneider/nyc-taxi-data) shows that Uberis taking millions of rides away from taxis in Manhattan [11]. Similarly, car-sharing programs
have been developed in response of the increasing population in cities, such as Zipcar which
has more then 10,000 vehicles in cities across the USA [45], the non-profit City CarShare in
the Bay Area, and Car2Go which offers one-way car sharing in Austin, TX. This revolution in
Personal Urban Mobility [30] is accompanied with the growing population in dense cities: 64%of the developing world and 86% of the developed world is predicted to be urbanized by 2050,
which is approximately equivalent to 3B urbanites by 2050 [1]. Hence, it will be increasingly
challenging for cities to maintain and develop infrastructures that will fullfill the rapid increasein transportation demands. As a result, the increased congestion of the road network will makecar ownership inconceivable and no longer sustainable. Morgan Stanley’s research shows thatcars are driven just 4% of the time [26] while the average cost of car ownership is nearly $9000
a year [38]. For example, car ownership has dropped by 30% from 2001 to 2015 in London[39] and the population will increasingly rely on public transportation (bus usage has doubled
in the same period) and MaaS systems.
Optimal management of MaaS systems: Since urban population will heavily depend on
MaaS systems, research has become very active on their optimal management, e.g. there havebeen works on real-time taxi dispatching [24], [29], optimal fleet sizing of vehicle rental systems[14], optimal re-balancing to supply demand in New York City [51], and the financial benefitsof an autonomous MaaS system in Singapore [41]. Dispatching or re-balancing is the necessary
coordination of the vehicles’ dispatching to fulfill the uneven distribution of origins and destinations of the requested rides. It can be done manually as commonly done by taxi companies
with human dispatchers, by apps such as taxi hailing apps, or by incentivization from the twosided markets formed by ride-sharing companies such as Uber or Lyft. It is also worth notingthat autonomous cars have aguably received a great deal of scientific attention, both Google
and Tesla predicting that autonomous cars will be available to the public by 2020 [25], [12].
Hence we include fleets of autonomous vehicles as part of MaaS systems, and research has also
been focused on the sustainability of autonomous fleets, suggesting that a fleet of 8000 to 9000
optimally-rebalanced autonomous vehicles (70% of the size of the current taxi fleet) can satisfy

3

the taxi demand in Manhattan [51], [50].
Vulnerability to Denial-of-Service attacks: As MaaS systems will provide several millions
rides per day (Uber currently does 1 milion/day [18]), fleets of connected vehicles and theirpassengers will be increasingly vulnerable to Denial-of-Service (DoS) attacks where attackers
are attempting to control and disrupt the re-balancing of vehicles to make them unavailable tocustomers. Such attacks have alreaby been reported: Uber claimed Lyft requested and cancelednearly 13,000 Uber rides and Lyft counted 5,560 canceled rides [23], [10], the goal being tosteal each other customers. Moreover, the vulnerability of self-driving cars to hacking is alreadya major concern for automobile manufacturers developing them. For example, General Motors
created the new role of cybersecurity to make sure that the company’s future autonomous vehicles
remain safe [13]. In fact, Miller and Valasek hacked a Jeep and suggested that it is possible
to wirelessly control a fleet of 471,000 vehicles already on the road by exploiting a flaw intheir Internet-connected computer feature (Uconnect) [17]. Hence, it will be possible for fleetsof autonomous vehicles to be vulnerable to DoS attacks. The present article also provides aframework for the analysis of the impact of DoS attacks on autonomous MaaS systems.
Cyber-security in transportation: The security of cyber-physical systems (along with Internetof Things) have gained a lot of attention recently [5] because the consequences of cyber-attacks
on them are not just financial, they could result in real-world and real-time physical problems.
The vulnerability of transportation systems are real: two Israeli students have successfully hacked
the traffic app Waze causing it to report a nonexistent traffic jam [46], an Argentinian security
researcher hacked traffic lights’ sensors to trick their control systems into thinking that open
roadways are congested and control them indirectly [49]. Reilly et al. suggested different attack
scenarios on Freeways via Coordinated Ramp Metering attacks [35]. In general, there have been
research on the security of abstract networks [34], [52], with applications to power systems [40],[48] and communication systems [3], [42].
B. Contributions and outline
To the best of our knowledge, we provide one of the first analysis frameworks for the financial
impacts of DoS attacks on MaaS systems. Here are our contributions:
Detailed statistical methodology: Even though our model expands an established queueingtheoretical framework for the analysis of the sustainability benefits of MaaS systems, such as in[14], [41], [51], we are among the first to provide a rigorous and detailed methodology for the4learning and construction of our model. Starting from the representation of the taxi demand as a
Poisson point process, we analyze the simplifying assumptions leading to the Jackson networkmodel. Most importantly, this powerful framework provides the mathematical tools to analyze theperformance of networked systems at a macroscopic level. In general, queuing models have been
widely used by the scientific community to model and analyze systems in traffic engineering,
computing, and telecommunication [27] and to optimally design factories, shops, offices andhospitals [16].
How to attack in practice? Our second contribution consists in providing realistic scenariosof attacks on (autonomous) MaaS systems based on case studies of existing systems. Technically,
it is possible to issue DoS attacks against Uber and Lyft with relatively low (material) costs. The
most direct approach consists in simultaneously requesting from the same origin several rides
and take them to go to specific destinations to make the service unavailable at the origin. Anotherapproach consists in issuing coordinated pickup requests (without taking the rides) in order tosteer the vehicles outside of a specific target region. These can be real pickup requests which
would be canceled (with a $5 dollar fee), or emulated ones by purchasing short-lived phone
numbers tied to human verification farms for $85-$500 per 1K [43] and credit card numbers
for 50 cents per unit on black markets [8]. The possible attack of a fleet of connected vehicles
would also be possible as a relatively low (material) price. As documented in [17], it is firstnecessary to acquire the hardware (typically the vehicle to be hacked) since the architecture of avehicle may be specific. Then analyzing weaknesses in the vehicle’s Internet-connected featureenables to gain access to the vehicle’s micro-controller and design a firmware that would replace
the vehicle’s one to send commands to its physical parts. Assuming that all vehicles in the fleet
have the same architecture, the attack would work on any vehicles from the analysis of a single
one, hence the low price of the attacks on a fleet of vehicles.
Modeling of the attacks: Attacks can be seen as malicious agents controlling the vehiclesof the MaaS system, which we will refer to as Zombie passengers. When they are serviced
by real 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 the other have happened in thepast [37]).The term Zombie is used following computer science terminology for a computer thathas been compromised remotely by a hacker to launch DoS attacks. Expanding an establishedframework in which the re-balanced MaaS system is cast into a queuing network where thecity blocks in Manhattan can be seen as server nodes (or stations), and cars as packets moving

5

between stations [51], one of our main contributions is to model the attacks as a stochastic processthat control a fractions of the packets (the cars) for malicious purpose. This malicious stochastic
process is added to two stochastic processes introduced in [14], [51]: packets with customers (thetaxi demand) learned from the taxi data provided by the NYC TLC, and a re-balancing process(the taxis being dispatched) to maintain high service availability in the network. Furthermore, tocapture different types of attacks, we also define the radius r of an attack, which is the furthest(Manhattan or `1 ) distance that a Zombie can be routed through. This captures the fact thatthe 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 bedispatched and affected. In the case of autonomous cars, the malicious behavior is more likely
to be detected if the cars are controlled by the attacker for a long period of time. With unlimited
resources, it would technically be possible to inject a very large flow of Zombies to disrupt thesystem. However, we assume that the total rates of attacks is upper bounded by a budget b andwe also study the financial impact of optimally attacks on the system under different values ofthe budget b.
Large-scale attack strategies: Casting the model of a MaaS system into a Jackson network
guarantees the existence of a set of balance equations and a product-form stationary distribution
for the stations occupancy, from which powerful analytic results have been derived [2]. There
results enable to characterize and compute the performance of large-scale networks such as
the Manhattan one. In particular, we focus on the availabilities of vehicles at each station andformulate a mathematical program for the design of attack strategies that optimally disrupt the
MaaS system at the city scale, e.g. that maximizes the customer loss or minimizes the customer
time usage of the system. This mathematical program is not convex and first-order descentmethods are not tractable (O(N 4 ) complexity where N is the number of stations) due to thebalance equations constraints, hence we propose a block-coordinated descent algorithm in which
each minimization block can be solved efficiently and each block can be seen as a specific attack
scenario.
Financial analysis: The optimization program provides different attack strategies that are thenimplemented on a Jackson network simulation to evaluate dynamically different metrics suchas the increase in passenger loss or decrease in vehicle availabilities one hour after the attacks
have started to be injected into the balanced network. The incurred customer or customer time
usage loss are then mapped to financial losses for the MaaS system under attack and benefits

6

for the attacks. For example, if the attacker is a rival MaaS system that receives a fraction of
the customers that were lost to the other system (from the DoS attacks), then a cost-benefit
analysis analysis shows the extent of damage that can be done with these attack. A case study in
NYC using a queuing model learned from the taxi data provided by the NYC TLC shows thatraising the cost of attacks to $15 is sufficient to deter rival companies from attacking via ridecancellations. Hence our framework will be usable to compute the optimal attack price-point of
an attacker, hence helping cab companies to adjust the cost of attacking to protect them selves.
The cost of attacks is a sum of explicit costs such as cancellation fees or price of the hardware
necessary to inject the zombies, and hidden costs like the time it takes to access to fleet ofvehicles, or the probability of detection times the penalty.
II. L EARNING THE Q UEUEING MODEL
In this section and the next one, we formally introduce the mathematical framework for ouranalysis: 1) a discretization framework can be used to study these systems in practice (and apply
it to NYC), 2) the three stochastic processes describing the customer demand, the re-balancing
process, and the attacks, 3) and the queuing model that connects these three processes together.
A. A Poisson point process
We consider a bounded (geographical) region R ⊂ R2 and a time period [t1 , t2 ] in which asequence of passenger rides xi = (ti , oi , di ) for i ∈ N are requested, where ti is the start timeof the ride, oi ∈ R its origin, and di ∈ R its destination. We model the sequence of ride requests
as a Poisson point process X = (Xt , Xo , Xd ) in the bounded space
Q := [t1 , t2 ] × R × R
with intensity function ρ : Q → [0, ∞) and intensity measure µ(B) :=

(1)
R
B

ρ(ξ) dξ for all

B ⊆ Q. We suppose that for all B ⊆ Q, µ(B) < ∞ since Q is bounded. Hence the Poisson
point process satisfies the following two properties for any B ⊆ Q and n ∈ N [31]:N (B) ∼ Pois(µ(B))(2)[XB | N (B) = n] ∼ Bin(B, n, ρ/µ(B))(3)

where N (B) is the number of points (or ride requests) in B, XB the restriction of the Poissonprocess X to the subset B, Pois(λ) the Poisson distribution with mean λ, and Bin(B, n, f ) the
distribution of n i.i.d. points in B with common density f .

7Vehicles must be dispatched to pickup passengers requesting a rides. The number of vehicles
to be dispatched to a region R1 ⊂ R to supply for the demand in the time window [t, t + ∆t] ⊂[t1 , t2 ] should be larger than the number of rides (ti , oi , di ) with ti ∈ [t, t + ∆t] and oi ∈ R1 ,i.e. larger than N (B), where B = [t, t + ∆t] × R1 × R. Using (3), a ride with origin o and start
time t and destination d ∈ R is chosen with probability density (with x = (t, o, d)):P (Xd = d | o, t) =ρ(x)µ({t} × {o} × R)

(4)

For tractability, we discretize the region R into N tiles Ti indexed by i ∈ S and the timeinterval [t1 , t2 ] into time windows of length ∆t. Blocks are chosen small enough such that all
trips end in a different block, and time intervals should be short so that the passenger demandcan be assumed constant, see Figure II-B for an example of discretization in NYC. Then pickup
requests arrivals within a tile Ti and time window τ := [t, t] follow a time-invariant Poissonprocess with rate µ([t, t] × Ti × R), and the destination tile Tj is chosen with probability
P (Xd ∈ Tj |Xt ∈ τ, Xo ∈ Ti ) =µ(τ × Ti × Tj )µ(τ × Ti × R)

(5)

which is a categorical distribution.
B. Statistically learning the demand
The pickup arrival rate in tile T and within times [t, t] follows a Poisson distribution withmean µ([t, t] × T × R). It is well-known that the sample mean is an unbiased minimum-varianceestimator1 (by achieving the Cramer-Rao lower bound), hence it is an efficient estimator of the
Poisson process [20]. An example of sample mean computed for each tile in part of Manhattan
is provided in Figure 1.
From (5), the destination tiles Tj of a trip starting at tile Ti and in time interval τ follows acategorical distribution with probabilities denoted by pτij . The maximum-a-posteriori (MAP) of
the parameters {pτij }j∈S is the mode of the posterior Dirichlet distributionmτij + nτijττk∈S mik + nik

MAP({pτij }j∈S | data) = P(6)

where nτij is simply the number of trips starting at tile Ti in time interval τ and with destination
Tj , and mτij are prior observations. Since we may not have any observations from the data,2 we
1Note that it is also a sufficient statistics for a Poisson distribution.

2

In Figure 1, all observed trips starting at the edge of the region of study finish outside of it.

8Fig. 1. Average passenger arrival rates in Manhattan from January 2009 to June 2015 on weekdays from 5pm to
7pm, learned from a dataset of 1B taxi trips provided by the NYC TLC. The average pickup rate every 10min during
weekdays is provided in our video: https://www.youtube.com/watch?v=RwGttGlflsA.

choose mτik = 1 for all k so that mτik + nτik > 0. A possible improvement consists in choosing aprior distribution {mik }k∈S proportional to the destination arrival rates.
III. Q UEUEING MODEL
We now drop the superscript τ since we restrict our analysis to a specific time interval (5pm7pm for the NYC case study). We have considered a MaaS system in an urban area divided into
N tiles indexed by i ∈ S. We assume that M vehicles provide service to customers between
pairs of tiles (i, j) ∈ S × S and cast the MaaS system into a Jackson model. Since vehicles are‘processed’ by a server in each tile, we will refer tiles as stations, which convey the fact thatvehicles are queuing to be picked up by customers.

9

Type

rate

routing

contribution

customerφiαij

MAS model [14]balancerψi

βij

re-balancing [51]Zombieνiκijcyber-security

TABLE IS UMMARY OF M ODELS

Different types of passenger with their arrival rates, routing probabilities, and the authors who introduced them.

A. Three types of passengers
We describe the model for vehicles picking up customers and re-balancing themselves in the
network. Finally, we introduce our model for Zombies. Table I summarizes these three models.
Customer model: Customers arrive at each tile i following a time-invariant Poisson processwith rate φi > 0. Upon arrival at a station i, a customer chooses to go to station j 6= i withP
probability αij ≥ 0, where j∈S αij = 1 and αii = 0 for all i ∈ S. Furthermore, if a vehicle
is not available at a station upon arrival of a customer, 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 station i to station j constitute an independently
and identically distributed (i.i.d.) sequence of exponentially distributed random variables withmean Tij > 0. This model was used in [14] 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 foruneven demand. A re-balancing vehicle is one traveling to a destination without customers tofulfill the demand at its destination. The process has been studied extensively [24], [29], [51]and we use the framework of [51] to model it with balancers driving these re-balancing vehicles.
This paradigm is analogous to the MaaS company “spoofing” its own drivers for re-balancing
purposes. In [51], each station i generates balancers according to a Poisson process with ratePψi ≥ 0 and routes these balancers to station 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 is lost if there is no car at the station
upon its generation.

10

Cyber-security: We extend the re-balancing work of [51] for the purpose of cyber-security
analysis. We assume the attacker can generate malicious agents or Zombies at each station ifollowing a Poisson process with rate νi ≥ 0 and route them to station j 6= i with probabilityPκ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 be routed through. 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

(7)

B. Comments on the Model
Although travel times are in general not exponentially distributed, their distribution does
not affect the predictive accuracy of similar queuing networks [21]. The customers’ routing
probabilities αij reasonably constitute an irreducible Markov chain for dense environments, andwe do not consider congestion, even though it negatively affects the efficiency of the networkand the effect of re-balancing.
Note that the “passenger loss” assumption in the model where passengers not willing to wait
(they leave the station immediately when there are no taxis available) is accurate in numerous
US markets. This framework is a good setting for analyzing the benefits and vulnerability of
MaaS systems: (i) with high service availability (the median wait time for an Uber in major
U.S. cities in 2014 was under 4 min [32]), 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 potentially encourage passengers
to use a rival system. From an analytical perspective, the passenger loss model considerably
simplifies our model because customer arrivals at a station is equivalent to a virtual service tothe vehicles currently queuing (and available) at the station.
The re-balancing and attacks are respectively modeled as balancers and Zombies following thesame process as customers (with passenger loss), but independently and with different arrival
rates and routing probabilities, thus allowing to combine the customer demand, the re-balancing

11

process, and the attacks into a single queuing network. In our case, the loss of balancers andZombies describe processes that encourage a re-allocation of vehicles to stations but does notenforce it.
Another critical assumption is that there is no attacker-defender game (see [7]) since the rebalancing only aims at high service availability given customers’ demand, and does not try to
defend from possible attacks. An interesting extension would be the analysis of a one-stage gamein which the balancers moves first with the knowledge of the Zombies’ best response.
C. Jackson network model
Following [14] and [51], the model described above can be cast into a closed Jackson network,
which we now present with a cyber-attack extension. We combine the customer, balancer, andZombie processes. From the superposition of independent Poisson processes, the total arrival
process of all three types of passengers is Poisson with rate
λi = φi + ψi + νi

(8)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 withrespective probabilities φi /λi , ψi /λi , and νi /λi . The routing probability rij := P (i → j) of ageneralized passenger arriving at station i to select a destination j is then given byXrij =P (i → j | class) P (class)

(9)

class

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

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

(10)

Stations are modeled as single-server (SS) nodes (or “station” nodes) and the route between
two stations as infinite-server (IS) nodes (or “route” nodes). When a generalized passenger arrives
at a non-empty station, a vehicle departs from that node to move to a route node that connect theorigin to the destination selected by that passenger. After spending an exponentially distributed
amount of time at the route node (the travel-time), the vehicle moves to the destination station
node (see Figure 2).
From a queuing perspective, if vehicles are present at station i, they are processed with service
rate λi given by (8), and are routed to the IS (route) node between stations i and j with probability

12Fig. 2. Illustration on a three station network. On the left, a passenger arrives at station 1 and picks a car to go tostation 2. The equivalent Jackson network is shown on the right side.

rij given by (10). Then vehicles at an IS node between stations 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, the MaaS system is modeled as a closed
Jackson network with respect to the vehicles with vehicle service rate µn (xn ) at a generalized
node n given byµn (xn ) =



λ i

if n = station ixn /Tij

if n = route i → j(11)where 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



rij



pnn0 = 1





0

if n = station i, n0 = route i → j
if n = route i → j, n0 = station j(12)otherwise

D. 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 station upon arrival. Mathematically, it is given by the following

13

steady-state probability (see [22]):
Ai (M ) := P (Xi ≥ 1) =γi G(M − 1)
G(M )

(13)

where the random variable Xi represent the queue length at station i ∈ S. Note that the quantity
G(M ) above is the normalization factor associated to the equilibrium state distribution of thequeue lengths {Xi }i∈S provided by the Gordon-Newelltheorem [15].
 The computation of G(M )|N | + M − 1
, where |N | is the cardinality|N |of N (i.e., the number of nodes in the network), so that |N | = N 2 . Hence, we want to obtainis very expensive with complexity that grows as 

performance metrics without computing explicitly the quantity G(M ), e.g. by studying theasymptotic behavior of the network when the fleet size M goes to infinity. The following result
from [33] gives the asymptotic availability at a SS node i:ai := lim Ai (M ) =M →∞γimaxj∈S γj(14)where maxj∈S γj is the highest relative utilization. Hence, when M approaches infinity, stations
with the highest relative utilization can have availability arbitrarily close to 1, while other stations
have availability strictly less than 1, since in this case γi < maxj∈S γj ).
To cancel this effect, Zhang and Pavone [51] designed a re-balancing policy with balancer
arrival rates ψi and routing βij that maintain fairness in the network, i.e. γi = γj for all i, j ∈ S.
When M is goes to infinity, this means that the availability of all stations goes to 1 since
γi = maxj∈S γj for all i ∈ S. In addition to imposing fairness, they minimize the number ofP
re-balancing vehicles given by the quantity i,j∈S Tij βij ψi .
IV. P ROBLEM FORMULATIONThe contributions of the present article encompass the objectives of an attacker into an
optimization framework, which we solve very efficiently.
A. Maximizing passenger loss
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 )
i∈S

(15)

14

S

Set of SS (station) nodes, |S| = N

MFleet size of the MaaS system

Tij

Mean travel time from i ∈ S to j ∈ S

φi , αij

Customer arrival rate and routing matrix

ψi , βij

Balancer arrival rate and routing matrix

νi , κij

Zombie arrival rate and routing prob.

Ai (M )

Prob. of i ∈ S of having ≥ 1 vehicle

ai

asymptotic availability, γi /1A

indicator function of condition A
TABLE II
S UMMARY OF NOTATIONS

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

(16)

i,j∈S

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

where wi > 0 are some user-defined arbitrary weights. To avoid computing G(M ) due to thecomplexity, the availabilities Ai (M ) are normalized with and consequently study the availability
Ai (M ) when the fleet size M goes to ∞ (see (14))
X
X
γi
= min
w i aiminwimaxj∈S γj
i∈S
i∈S

(18)

Finally, there must be one i ∈ S such that ai = 1, hence the objective is equivalent to finding
the index k such that ak is set to 1 and minimizing over the remaining quantities {ai }i6=k()
X
min wk · 1 + min
w i ai(19)k∈S{ai }i6=k

i6=kHence, we can solve |S| = N programs and select the one with the minimum objective value.
3

The distance Dij between stations i and j can also be included in the objective since fares as usually a combination of the

two.

15

B. Attack budget
The most important constraints are the traffic equations of the Jackson network. Using Lemmas
4.1 and 4.2 in [51], they can be written in terms of SS (station) nodes and asymptotic utilizationai(φi + ψi + νi )ai =X(αji φj + βji ψj + κji νj )aj , ∀ i

(20)

j∈S

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

(21)

j∈S

Note that the constraint (21) is redundant since summing the constraints (20) for i 6= k (withak = 1) gives (21). Furthermore, the attacker injects Zombies with arrival rates νi and routing
matrix κij to achieve (19). With no restriction on the attack rates, setting νi = ν > 0 for all
i 6= k and routing all the Zombies to station k with probability 1 gives, using (21)XX
νaj
(αjk φj + βjk ψj + ν)aj ≥φk + ψk + νk =
j6=k

j6=k

X

aj ≤ (φk + ψk + νk )/ν → 0

when ν → +∞j6=kThen the positive utilizations ai go to 0 for all i 6= k and the problem is reduced to mink∈S wk .
Hence, a more realistic problem is setting a limited budget b for the attacks
Xνi ≤ b(22)

i∈S

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

and so the combined routing probabilities rij of the customers, balancers, and Zombies given in(10) can be expressed as follows
rij =δji ϕj + κji νjϕi + νi∀ i, j ∈ S

(25)

16

Given k ∈ S such that ak = 1, the Optimal Attack Problem (OAP) consists in manipulating theZombie arrival rates νi and routing κij probabilities such that:Xmin
w i aiκij ,νi ,ai

(26)

i6=k

s.t. ai =X δji ϕj + κji νjϕi + νiX
κij ≥ 0,
κij = 1,∀ i ∈ S \ {k}(27)

1{(i,j)∈E}/ κij = 0

(28)

aj

j∈S

j

νi ≥ 0,X

νi ≤ b(29)i

We have also included the ai in the decision variables since they vary. In fact, the ai arefunction of κij , νi and can be written directly as ai (κ, ν).
L EMMA 1. For any attack strategies νi and κij :ai > 0 for all i ∈ S(30)

ai is uniquely defined for all i ∈ S(31)

Proof. By assumption, the probabilities αij constitute an irreducible Markov chain. By equation(10), the probabilities rij lead to an irreducible Markov chain as well. The {ai }i vector satisfying
equations (27) is proportional to the steady state distribution for the transition probabilities {rij }ij
and by the Perron-Frobenius theorem, it is positive [28]. Finally, the constraint ak = 1 completely
fixes the vector {ai }i .
V. A NALYTICAL RESULTS
We first study a scenario in which the attacker aims at reducing the asymptotic availabilities
at all but one station by a constant factor for a network in equilibrium. In this case, we showthat the best strategy consists in routing all attacks to a single destination and we are able toderive analytical results for the rates of attacks.
A. Uniformly reducing availabilities
We consider a re-balancing network where the combined rate {φi }i and routing probabilities{δij }ij of the real and re-balancing passengers are given, and we denote {ai }i∈S the resulting
availabilities (before attacks). We consider a simple scenario in which the attacker reduces the17availabilities at all stations by a constant factor, i.e. availability at station k is set to 1 and α ≥ 1
is maximized such that:
ãi =



1

if i = kai /αif i 6= k(32)

where ãi are the availabilities resulting from the attacks. Now we propose and prove theoptimality of an attack strategy that maximizes α.
T HEOREM 1. Consider a (balanced) MaaS system with initial asymptotic availabilities {ai }i∈S .
If we are given a budget b for the attacks that is at least a certain amount:Xb ≥ (1 − ak ) ϕkδkj /aj

(33)

j6=k

Then the best attacks such thatPi νi ≤ b, resulting in station k having asymptotic availability

equal to 1 and all other stations’ availabilities decrease by the same factor α ≥ 1 can beachieved by the following policy:
νi =

κij =





ai

P bδkij6=k δkj /aj

if i 6= k
(34)


0
if i = k1 if i 6= k, j = k(35)0 otherwise
We call it the “Single-Destination Attack Policy” (SDAP) since all attacks are routed to k. It
results in:
α = ak +b
ϕkP

j6=k δkj /aj

Proof. The balance equations before attacks are:X
aj ϕj δji = ai ϕi∀i ∈ S

(36)

(37)

j6=i

After attacks, the equations can be written as:
Xãj (νj κji + ϕj δji) = ãi (νi + ϕi ) ∀ i ∈ S
j6=i

(38)

18

Given (32), the above equation at index k is:
X aj(νj κjk + ϕj δjk) = νk + ϕkαj6=k1
νk + ϕk=Pαj6=k aj (νj κjk + ϕj δjk)

(39)
(40)

We first maximize α with respect to the routing probabilities {κij }ij , which is clearly achieved
when κij satisfies the policy (35). As a result, equations (38) combined with (32) and (35)
become:X ajai
ϕj δji + ϕk δki = (νi + ϕi ) ∀ i 6= k
α
α

(41)

j ∈{i,k}/Multiplying by α and subtracting (38) on both sides:ϕk δki (α − ak ) = ai νi∀ i 6= k(42)

α = ak + ai νi /(ϕk δki ) ∀ i : δki > 0(43)

From (42), νi is proportional to δki /ai for all i 6= k, thusνP ii6=k νi=Pδki /aij6=k δkj /aj∀ i 6= k(44)

Plugging the above expression into (43)Hence α is maximized whenPPνi
P i6=kα = ak +ϕk j6=k δkj /aj(45)

i6=k νi = b, setting {νi }i∈S

to follow policy (34) (using (44)).

We verify that the policy derived above is feasible given (37). Finally, we want α ≥ 1, which
implies (33).
We make some comments on the effectiveness of attacks discussed presented in Theorem 1.
Under the SDAP, ak = 1 reduces condition (33) to b ≥ 0, i.e. any budget leads to α ≥ 1. If
ak < 1, then α ≥ 1 requires a minimum positive budget given by (33). However, if ak < 1 and(33) is not verified, then α < 1 and re-normalizing so that we get valid asymptotic availabilities
after attacks gives
ãi =



α

if i = kai

if i 6= k(46)

where there exists i 6= k such that ai = 1. In this particular case, the attack only increases
the asymptotic availability at station k while keeping other availabilities constant. Consequently,

19

using the optimality of the SDAP within the framework of Theorem 1, we have the following
corollaryC OROLLARY 1. Given a MaaS system with availabilities {ai }i∈S and a budget b ≥ 0, if theobjective is to reduce the asymptotic availability of all stations by a constant factor α ≥ 1
except one station, inequality (33) is a necessary condition for optimality. A sufficient conditionnoPfor optimality is choosing the index k from the set i ∈ S : b ≥ (1 − ai ) ϕi j6=i δij /aj thatminimizes
!
wk +

X

wi a0i

1+

i6=k

!−1

b
ϕk

P

0
j6=k δkj /aj(47)

B. Case of balanced network under attacks
The result in Theorem 1 holds for MaaS systems with or without re-balancing passengers. If
the MaaS is balanced, i.e. ai = 1 for all i ∈ S, then the SDAP reduces toνi = bδki ∀ i 6= k, νk = 01 if i 6= k, j = kκij =0 otherwise

(48)
(49)

resulting in ãi = 1/α for all i 6= k and ãk = 1, with:
α = 1 + b/ϕk

(50)

Hence, for a balanced network in equilibrium, the passenger loss incurred by this attack strategy
when the fleet size approaches infinity is asymptotically

X
X 
1
wi 1 −wi (ai − ãi ) =
α
i∈S
i6=k
=

b X
wi
ϕk + b i6=k

(51)
(52)

We note that the attacks have great effects for small budgets, with incurred losses scaling linearly
in b:
X
i∈S

wi (ai − ãi ) ≈b Xwiϕk i6=kforb  ϕk(53)

Hence, when routing the attacked vehicles to a single destination station k, it is best to pick astation k with low customer demand and low re-balancing rate ϕk = φk + ψk and small weight20

wk . Concretely, an attack sending all the vehicles to a single station k aims at having an excess
of supply at this station while depriving the rest of the network of vehicles. The quantity ϕkis the rate at which the vehicles are sent away from k from customer rides or re-dispatching,hence it is more effective to maliciously send vehicles in parts of the network with low activity.
C. Budget maximization as a prerequisite for optimality
We now show that all of the budget b has to be used for an attack to be optimal. While thisresult is intuitive and can be proved directly from the KKT conditions associated to the OAP,
we present an alternate proof which gives additional insights on the OAP. Theorem 1 leads tothe following result:
T HEOREM 2. Equality

Pi∈S νi = b is a necessary condition for a solution of the OAP to be

optimal.
Proof. Suppose b > 0 (otherwise there is no attack). Let (ai , νi , κij ) be a feasible solution ofP
the OAP such that i∈S νi < b. We show that it is not optimal. We combine the Zombies tothe real and re-balancing passengers:ϕ̃i := ϕi + νi(54)

δ̃ij := (δji ϕj + κji νj )/(ϕi + νi )Xb̃ := b −
νi > 0

(55)
(56)

i∈S

Then applying policy the SDAP with ϕ̃i , δ̃ij , b̃, ai and k such that ak = 1 decreases the ai for
i 6= k by a factor α > 1 (using (36) and the assumptions that b, ϕk > 0) Since the wi ’s are
positive by assumption and the ai ’s are positive from Lemma 1, the objective decreases by apositive amount. Let us denote ν̃i and κ̃ij the resulting attack policy. Then, the combination of(νi , κij ) and (ν̃i , κ̃ij ) given by ν̃i + νi and (κ̃ji ν̃j + κji νj )/(ν̃i + νi ) is still feasible for the OAP
and decreases the objective by a positive amount.
VI. B LOCK - COORDINATE DESCENT
In this section, one of our contributions is to propose an algorithm to efficiently solve the OAP.
Noting that first-order methods are not tractable because of the balance constraints, we propose
a block-coordinate descent algorithm in which the three blocks can be solved very efficiently,

21

two being linear programs (LP) with N 2 variables, and the third one a quadratically constrained
quadratic program (QCQP) with N variables (N being the number of stations). We also add aPsmall cost of attacking p i νi to the objective4 such that objective becomes:XXminw i ai + p
νi(57)
κij ,νi ,ai

i6=k

i

A detailed justification of it is provided in Section VI-E.
A. Non-tractable first-order methods
The OAP (26)-(29) is non-convex because the equality constraints (28) are not linear, hence
the well-known Lagrangian approach fail to provide sufficient conditions for optimality of asolution [4]. So one can only hope to find stationary points. In addition, first-order methods
such as gradient descent algorithms are not tractable in practice. Specifically, the vector {ai }i∈S
is a function of κij , νi from Lemma 1, hence the gradient of the objective is given byX{∂νi al }i∈Swi ∂κij al (i,j)∈S×S
l6=k

(58)

where each partial derivative of ai satisfies a set of N − 1 linear equations obtained by differentiating the balance constraints (27). Hence, computing the gradient prohibitively requires
to solve N 2 linear programs of dimension N − 1 by differentiating the constraints (27). The
total complexity for computing the gradient is (N 2 − N )2 ≥ (N − 1)4 , where N for a typical
implementation of the model like in NYC is of the order of 500. One 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 Algorithm 1. We pose the Minimum Attack Problem (MAP)and the Attack Routing Problem (ARoP) and show that they can be re-formulated as linear
programs (LP) 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 Nvariables which are {νi }i∈S and can be solved efficiently using a projected gradient descentalgorithm. 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 canbe interpreted as specific attack scenarios in their own right. Specifically, in each scenario, theattacker is given a fixed allocation of either the availabilities ai , the attack rates νi , or the attack
4

This can be seen as a `1 -regularization term.

22routing κij , and he wants to allocate the two other types of “resources” optimally to harm thesystem. We also describe how each one of these programs fits into the proposed block-coordinate
descent algorithm.
Algorithm 1 Algorithm for solving the AOP.
1: choose arbitrary station k ∈ S.
2: initialize νi and κij
3: while stopping criteria not satisfied:
4:

update ai , κij via Attack Routing Pb. (ARoP) with νi fixed.

5:

update νi , κij via Min Attack Pb. (MAP) with ai fixed.

6:

update ai , νi via Attack Rate Pb. (ARaP) with κij fixed.

7: return ai , νi , κij

B. 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 stations i ∈ S that remotely spoof the hailing apps of nearby
vehicles, to send them to specific locations. Hence, given νi , the attacker wants to optimize therouting to achieve objective (19). This is the Attack Routing Problem (ARoP), which can be
re-formulated as a Linear Program from this lemma
T HEOREM 3. Let us consider the following linear program (LARoP)X
minwi yij
yij

s.t.

(59)

ij

X

(λi yij − νj yji ) =j6=iyij ≥ 0,Xδji ϕj yjl∀ i 6= k

(60)

j>l

X

ykj = 1

(61)

j6=k

Let yij? be an optimal solution to LARoP. Then, an optimal solution of the ARoP is
X

yij?

(62)

κij = yij? /ai

(63)

ai =

j6=i

Proof. We can obtain LARoP from the OAP by fixing νi and making the change of variables
yij := κij ai to equations (26) – (28).

23

We decrease theP

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 block-coordinate descent algorithm.
C. Attack Rate Problem (ARaP)In this scenario, the attacker hacks the apps of the vehicles to display “ghost” demands at
specific stations i. With fixed routing κij , the attack rates νi are chosen to achieve objective (26).
The Attack Rate Problem (ARaP) consists in optimizing the OAP with respect to the rates νifor all i and the asymptotic availabilities ai for i 6= k, while the routing of attacks κij are fixed.
P
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:
L EMMA 2. The Jacobian matrix (∂ai /∂νj )i6=k,j∈S of dimension (N − 1) × N has columns
xj ∈ RN −1 for j ∈ S that satisfy(D − M ) xj = vj

∀j ∈ S(64)

where D is a diagonal matrix with entries {ϕi + νi }i6=k , M = {φj δji + νj κji }i6=k,j6=k , andvj ∈ RN −1 for j ∈ S are vectors with entries {aj (κji − 1{i=j} )}i6=k where 1A is the indicatorfunction 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 gradientof the objective:{νi }i∈S :=Π ({νi }i∈S − t g)Xg :=(∂ai /∂νj )j∈S + p

(65)
(66)

i6=k
S
where t > 0 is the step size and Π is the projection onto the `1 -ball of radius b, i.e. {x ∈ R≥0:Pi∈S xi ≤ b}. We use the O(N log N ) implementation described in [9]. We use a step size√
decreasing in 1/ n where n is the number of iterations and complement it with a simple line

search to have a lower objective at each iteration.
t ← t/2 while f ({νi }i∈S − t g) > f ({νi }i∈S )

(67)

24

D. Minimum Attack Problem (MAP)
We consider a scenario in which the attacker wants to achieve target availabilities ai at eachP
station in the network with the minimum cost of attacks i νi . The Minimum Attack Problem(MAP) can be formulated as follows
Xminνiκij ,νi(68)

is.t. ai =X δji ϕj + κji νjϕi + νij∈SX
κij ≥ 0,
κij = 1,∀ i ∈ S \ {k}(69)

1{(i,j)∈E}/ κij = 0

(70)

aj

j

νi ≥ 0 ∀ i ∈ S(71)

The constraints can be formulated as flow constraints
T HEOREM 4. Let us define
si := ai ϕi −X

aj δji ϕj∀i ∈ S(72)

j6=i

and consider the following Quadratic Program
X xij
min
xij
ai
i,j
X
s.t.
(xji − xij ) = si(73)∀i ∈ S(74)∀ i, j ∈ S

(75)

j6=i

xij ≥ 0 1{(i,j)∈E}/ xij = 0This is always feasible. Let x?ij be an optimal solution to it. Then, an optimal solution to the
MAP is:νi =Xx?ij /ai

(76)

j6=i

κij =



x? /(νi ai )if νi > 0
1/ P 1{(i,j)∈E}

otherwise

ij

j

(77)

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

25

which converts the MAP into the above program with {si }i∈S given by (72) and νi =P

j6=i xij /ai

as a result of the change of variable. Note that xij can be interpreted as the rate of attack fromstation i to j. This problem is feasible because the capacity on each edge is unbounded and thesource flows sum to 0:
X
i

si =

X

ai ϕ i −iXaj δji ϕi = 0(79)

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 (29)to the MAP using the solution of the previous step as initial solution, and solve it efficiently
using CPLEX. Note that the objective of the above program can be generalized to any convex
function, and a linear objective results in a min-cost-flow problem (MCFP). This reduction to a
MCFP was shown in [51] for the purpose of re-balancing vehicles with an objective minimizing
the number of re-balancing tripsminXψi , βij

ψi Tij βij

(80)

i,j

where ψi , βij are the balancers arrival rates and routing probabilities respectively. In our case,
the MAP step of our algorithm redistributes the highest attack rates among stations, thus avoiding
numerical corner cases associated to the sparsity promoting constraint (29).
E. Note on the penalization
We include the `1 -regularization term in the objective so that it becomes:
XX
w i ai + p
νiminκij ,νi ,ai

i6=k

(81)

i

The main reason is numerical. Having a term in the objective that depends on the attack rates νienables to pose the MAP block of our block-coordinate descent algorithm, when the availabilities
ai are fixed. The MAP essentially computes a better re-allocation of the attacks (in terms of totalP
rate minimization) to incur the same loss i wi ai to the MaaS system. If the MAP computes
Pa strictly better attack strategy, then necessarily i νi < b, and from Theorem 2, the unused
part of the budget can be used to increase the customer loss of the MaaS system, which isaccomplished by the two other steps of the block-descent algorithm.
Had we known the gain for the attacker from incurring passenger loss to the MaaS system, e.g.
a rival company stealing a fraction of the passengers that are lost to the other system, along with26

the knowledge of the cost of attacks, we could have solved the OAP with p equal to the ratio of
the attack cost over the gain from passenger loss for the attacker. This can be solved efficiently
with the proposed gradient descent algorithm and would embed directly a benefit-cost analysis
into the optimization program. However, without the knowledge of these parameters, a more
systematic way to proceed consists in setting the weight p of the penalty to be small enoughso that all the budget is used, and compute the loss incurred from the attacks under different
values of the budget b. This enables to analyze the costs and benefits of attacking under different
values of the parameters, which we do in the next section.

Fig. 3. Effect of Radius of Attacks. (a): Target availability pattern following a pixelated version of the “Cal” logo. (b),(c): Best attack policy to achieve 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 stations j from an origin i, and thecolor of each square encodes the attack rate. (d): Total attack rate per hour needed to achieve the specified availabilities
as a function 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 from regionswith low availabilities (yellow in (a)) and send them directly to the borders of Manhattan. Hence, limiting the attack
radius greatly hinders the attacks’ effectiveness, and increasing the radius past 1-2 km results in diminishing returns.

VII. Q UANTIFYING COUNTERMEASURES
We now study the economics of the resiliency of MaaS systems to DoS attacks and illustrate
our results with a case study in Manhattan. In particular, we conduct a cost-benefit analysis and27find that raising the expected cost of attacks to 1.5 times the gain for the attacker from incurring
passenger loss protects MaaS systems from DoS attacks.
A. Data sources and methodology
Specific to the case study in Manhattan, we choose the tiles to be approximately the size of
two city blocks which is a good trade-off between precision and tractability: 1) any taxi thatis within two blocks of a pickup location can reach the exact location within minutes, 2) thedestination is more than two blocks away, hence trips do not stay within a tile, and 3) Manhattan
is then divided into 531 tiles (see Figure 1), which gives a problem with 5312 ≈ 300, 000 decisionvariables that can be solved efficiently. The time windows are chosen to be one/two-hour longwhich is small enough to ignore time variability in the taxi demand. Using the 1.1 billion taxi
trips from January 2009 to June 2015 provided by the NYC TLC, we extracted 75M passenger
rides on all weekdays between 5pm and 7pm and we learned the customer demand φi , αij using
the methodology presented in Section 2. The total customer arrival rate is about 10,600 per hour(see Figure 1) and there are about 2,500 taxis in the network in this time period.
P
We then solve the MAP with objective min i,j φi Tij αij to estimate the optimal re-balancing
process ψi , βij . Combining the customer demand and balancing process (assuming the system isbalanced), the solution of the OAP provides an attack strategy that maximizes the passenger loss
in the network. While the OAP is a useful framework for computing optimal attack strategies
for a system in equilibrium, we also simulate a Jackson network with N 2 ≈ 300, 000 nodes,
described in (11), (12), to dynamically estimate the passenger loss L incurred by the attacks
during the first hour after the attacks have started.
B. Cost-benefit analysis
Following the methodology in [6], we propose a basic economic model of supply and demand
for attacks. Assuming that attackers make rational decisions, a market of attacks is a usefulstarting point for evaluating the volume of attacks, in which the profit for the attacker is givenPby αL − β i νi where αL is the gain for the attacker as a linear function the incurred passengerP
loss, and β i νi the cost of the attacks. The parameters α and β can be seen as a level of security,
where the security increases if α is lower and β higher. Hence, given a level of security (α, β),attackers balance the cost of additional attacks against the benefits from additional attacks. We

28

now provide simple estimates for α, β, an in-depth study of the costs and benefits of attacks
being beyond the scope of the article.
Explicit cost of attacks: The explicit cost of attacks is generally very low. For instance, forride-sharing services such as Uber or Lyft, pickup requests being cancelled using a real accountcost $5 per unit. The cost a fake account is less than $1 since both credit card numbers and phone
numbers (tied to human verification farms) reportedly cost less than $0.5 per unit [43], [8]. In
addition, there is a fixed cost, e.g. the hardware required for generating the attacks. Following theattack on Waze [46], it is possible to emulate Android phones on a computer. Hence, the fixed
cost is less than $2000 to host (potentially thousands of) fake Uber/Lyft accounts. Based on thefollowing study [17], an attack on a fleet of Internet-connected autonomous vehicles requires
the analysis of the hardware of one vehicle to be able to gain remote access to other vehicles ofthe fleet. Hence, the fixed cost of attacking MaaS systems is independent of the fleet size andthe rate of attacks, which makes MaaS systems particularly vulnerable to attacks.
Hidden cost of attacks: The hidden costs are arguably much higher than the explicit costs.
For current ride-sharing systems such as Uber and Lyft, suspicious (or malicious) accounts
can be detected and blocked easily, along with its associated phone and credit card numbers.
Buying phone and credit card numbers on the black markets has a risk of being caught by
law enforcement agencies. These hidden costs can be modeled as β hidden = P (detection) ×
Penalty i.e. a probability of being detected times the penalty of being caught. Hence, more
efficient law enforcement and crimes detection can achieve a higher level of security by increasing
P (detection) and the Penalty. It is worth noting that some taxi companies, e.g. Taxis G7 in
France (http://www.taxisg7.fr/), does not require the creation of a PIN verified account to makea request, hence P (detection) = 0 are the only (explicit) cost is the call ($.16/min). Hidden costs
also include the working time necessary for designing DoS attacks which can take the form ofa salary paid to the hackers. The cost of labor can be high and it is an increasing function of
the level of protection of cyber-physical systems again security breaches.
Gain for the attacker: Reasons for DoS attacks are multiple,5 e.g. extortion, blackmail,expression of anger and criticism, punishment (for refusing an extortion demand and thus
disrupting the attackers’ business model). Because of the wide variety of motives, the benefits
should be estimated case by case. In the case of anti-competition practice in two-sided networks
5

See: https://zeltser.com/reasons-for-denial-of-service-attacks/

29(e.g. Uber and Lyft), the gains for DoS attacks can be enormous since successful platforms enjoy
increasing returns to scale [36]. The high costs and high benefits of attacks on a large-scale MaaS
system justifies the need of a business model for the attacker to make rational decisions.
The defender side: Protecting mass-produced systems (e.g. Internet-connected vehicles, smart
watches etc.) against security breaches is costly, hence companies are encouraged to under invest
in cyber security. While a cost-benefit analysis can also be conducted to estimate the optimal
amount of security for the defender, this study is beyond the scope of the article.
C. Controlling availabilities
In this experiment, given any arbitrary set of availabilities ai for i ∈ S (S being the setof stations), we find the minimal cost of attacks such that the resulting availabilities match theprovided ones. We show that we can create arbitrary availability patterns in the city, in particularthe “Cal” logo, see Figure 3a. Assuming a balanced MaaS system, we first balance the network
using the methodology of [51], i.e. solving the MAP (69)-(71) (i.e. the second step in ourblock-coordinate descent algorithm to solve the OAP) with the availabilities uniformly equal to
1 and with an objective that minimized the number of re-balancing vehicles (80). This yields a
total rate of 2,200 re-balancing vehicles per hour. We then compute the attack strategy on thebalanced network by solving the MAP. When the attacking radius is unlimited, injecting only
800 Zombies per hour achieves the availability pattern encoded in the “Cal” logo. Assumingthat a unit of attack is $5 (current cancellation for a Uber/Lyft ride), only $4000 per hour issufficient to deplete the network following this pattern.
Next, we restrict the radius of attacks by limiting the routing from a station i to station j tobe between 1 and 15 in terms of Manhattan distance (or `1 distance), with a station block as aunit of length (0.3km per block). We find the minimum attacks rate needed to create the “Cal”
logo, as illustrated by Figures 3.
D. Minimizing availabilities
In this experiment, we solve the OAP that minimizes the time usage (16). We note that there
are very large disparities in customer arrival rates: the stations close to Grand Central station
having customer arrival rates of 200 vehicles per hour while the stations along East river have
one customer arrival every four hours on average between 5 and 7pm. To avoid numericaldifficulties related to it, we cluster adjacent blocks together such that the minimum aggregated30

arrival rate at a station is 30 customers per hour, resulting in a reduction to 331 blocks. We thenbalance the network and apply the proposed block-coordinate descent algorithm for solving the
OAP with an objective (16) minimizing the customer time usage in the network. The different
steps are summarized in Algorithm 1.

Fig. 4. Network Simulation Results. A simulation is run with 2650 taxis in a Jackson network. After 1 hour of balancing,
the network is attacked (following a strategy given by a solution to the OAP). The budget of attacks is 3000 requests
per hour, corresponding to 19% of the total rate. The figure shows the passenger loss in log-scale per station over (a): 1
hour of balancing, (b): 1 hour of attacks. (c) shows the total number of customers lost over time. The total cumulativeloss is slightly above 2000 passengers one hour after the start of the attacks.

We do not set a limit on the radius of attacks and apply the descent method for values of thebudget b of attack rate in {100, 500, 1000, 1500, 2000, 2500, 3000, 5000, 7000, 10000} with theweight p of the `1 -penalty 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 total attack rate accounts for 0.8% to 44% of the total

31

Fig. 5. Optimal Attack Rates and Routing. (a) and (b): The attack rates and routing probabilities for a total budgetof 2000 Zombies per hour are showed in the same style as in Figure 3, 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 and a strategy computed from the OAP). The vertical scale on the left shows
the rate of passenger loss and the one on the right the financial loss assuming that a passenger spends $10.75 on anaverage. The red line denotes the price 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 showsthat 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.

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 sending Zombies to several spots around the center of Manhattan, see Figure VII-Da andb. In equilibrium, these target regions have high availabilities while the rest of Manhattan hasvery low availabilities. These results are similar to the analytical ones in Section V, where it wasproved that the optimal attack strategy is one that sends all the vehicles in a single destination
station (see Theorem 1).
E. Network simulation
Solving for the attack rates using the OAP gives very low objective values, with a loss ofcustomer 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 centerregion because the re-dispatch process does not send the vehicles in other parts of the network32

in reaction to the attacks. To account for the transient state, 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 the day used for our parameter inference).
We start from a closed network in equilibrium and introduce attacks. For each queue in thesimulation, customers, balancers and Zombies arrive with our specified rates, and are lost when
there are no vehicles in the queue. We then record the number of customers lost for one hourand subtract from this the base rate of loss when the network is balanced. One run of a Jackson
network simulation is presented in Figure 4 for a budget of 3000 attacks per hour. Slightly
above 2000 passengers are lost after one hour of attacks. This gives the seventh sample point
in Figure VII-Dc. Figure VII-Dc and VII-Dd show the results of our analysis. Assuming thatthe cost of an attack is $5 (the cost of canceling an Uber/Lyft ride) and the gain of the attacker
is $10.75 (the average cost of a ride in the area estimated from our data-set), Figure VII-Dc
shows that it is not economical to attack with more than 5000 Zombies per hour. From this, we
can deduce that a cost of attack greater than $15 protects the MaaS system against attacks. Thiscan be generalized to a cost of attacks being approximately 1.5 times higher than the gain fromincurring passenger loss.
VIII. C ONCLUSIONS AND FUTURE WORKWe described an analysis framework for quantifying the vulnerability to MaaS systems to
DoS attacks. We first model the customer demand as a discretized Poisson point process learned
from taxi data in Manhattan. The model for the MaaS system is cast into a Jackson network
which enables to formulate a mathematical program for attack strategies that maximize thepassenger loss in equilibrium. The strategy is then implemented on a Jackson network simulation
to dynamically estimate the passenger loss incurred by the attacks. We then present a cost-benefit
analysis for the attacker which is a first step in estimating the volume of attacks. For the casestudy of Manhattan in the context of anti-competition practice, it is demonstrated that DoS
attacks costing more than $15 per unit do not compensate the benefits for the attacker fromincurring passenger loss and stealing passengers.
The present work opens up exciting avenues of future work. We have largely ignored congestion effects on the network and would like to include them in future work. We also assumed
that the MaaS company does not respond to the attacks. Hence, future work include methods todetect suspicious routing of the vehicles, and a attacker-defender game.

33

ACKNOWLEDGMENTS
The authors would like to thank Cathy Wu, Ramtin Pedarsani, and Chao Zhang for insightful
discussions on the problem.
R EFERENCES[1] Urban life: Open-air computers. The Economist, 2012.
[2] F. Baskett, K. M. Chandy, R. R. Muntz, and F. Palacios-Gomez. Open, closed, and mixed networks of queues with different
classes of customers. Journal of the Association for Computing Machinery, 22:248–260, 1975.
[3] 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.
[4] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, March 8 2004.
[5] A. A. Cardenas, S. Amin, and S. Sastry. Secure control: Towards survivable cyber-physical systems. International
Conference on Distributed Computing Systems, 2008.
[6] J. J. Cordes. An Overview of the Economics of Cybersecurity and Cybersecurity Policy. CSPRI Report, 2011.
[7] L. A. Cox. Game Theory and Risk Analysis. Risk Analysis, 29, 2009.
[8] B. Dean. Your stolen credit card data is probably worth only 50 cents on the black market. The Week, 2015.
[9] 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.
[10] E. Fink. Uber’s dirty tricks quantified: Rival counts 5,560 canceled rides. CNN, 2014.
[11] R. Fischer-Baum and C. Bialik. Uber Is Taking Millions Of Manhattan Rides Away From Taxis. FiveThirtyEight Economics,
2015.
[12] L. Gannes. Here’s What It’s Like to Go for a Ride in Google’s Robot Car. recode, 2014.
[13] B. Geier. Car hacking: how big is the threat to self-driving cars? Fortune, 2014.
[14] D. K. George and C. H. Xia. Fleet-sizing and service availability for a vehicle rental system via closed queueing networks.
European Journal of Operational Research, 211(1):198–207, 2011.
[15] W. J. Gordon and G. F. Newell. Closed Queuing Systems with Exponential Servers. Operations Research, 15, 1967.
[16] L. V. Green, P. J. Kolesar, and W. Whitt. Coping with time-varying demand when setting staffing requirements for aservice system. 16, 2007.
[17] A. Greenberg. Hackers remotely kill a jeep on the highway - with me in it. Wired, 2015.
[18] E. Huet. Uber Says It’s Doing 1 Million Rides Per Day, 140 Million In Last Year. Forbes, 2014.
[19] E. Huet. Uber’s Global Expansion In Five Seconds. Forbes, 2014.
[20] R. W. Keener. Theoretical Statistics. Springer in Statistics, 2010.
[21] R. C. Larson and A. R. Odoni. Urban operations research. 1981.
[22] S. S. Lavenberg. Computer performance modeling handbook. Elsevier, 1983.
[23] R. Lawler. Uber Strikes Back, Claiming Lyft Drivers And Employees Canceled Nearly 13,000 Rides. TechCrunch, 2014.
[24] Z. Liao. Real-time taxi dispatching using Global Positioning Systems. ACM, 46:81–83, 2003.
[25] E. Mack. Elon Musk: Don’t fall asleep at the wheel for another 5 years. CNET, 2014.
[26] J. McDuling. Quartz, 2014.
[27] D. A. Menascé, V. A. F. Almeida, and L. W. Dowdy. Performance by Design: Computer Capacity Planning by Example.
2004.

34

[28] C. D. Meyer. Matrix Analysis and Applied Linear Algebra. Society for Industrial and Applied Mathematics, 2000.
[29] 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 in metropolitan areas a receding horizon control approach. International Conference on Cyber-Physical
Systems, pages 100–109, 2015.
[30] W. J. Mitchell, C. E. Borroni-Bird, and L. D. Burns. Reinventing the Automobile: Personal Urban Mobility for the 21stCentury. The MIT Press, 2010.
[31] J. Moller and R. P. Waagepetersen. Statistical Inference and Simulation for Spatial Point Processes. Chapman andHall/CRC, 2004.
[32] P. Mosendz and H. Sender. EXCLUSIVE: Here’s How Long It Takes to Get an Uber in U.S. Cities. Newsweek, December
4 2014.
[33] R. R. Muntz and J. W. Wong. Asymptotic properties of closed queueing network models. 8th Annual Princeton Conferenceon Information Sciences and Systems, pages 348–352, 1974.
[34] T. R. Nudell and A. Chakrabortty. Ensuring Localizability of Node Attacks in Consensus Networks via Feedback Graph
Design. American Control Conference, 2014.
[35] J. Reilly, S. Martin, M. Payer, and A. Bayen. On Cybersecurity of Freeway Control Systems: Analysis of CoordinatedRamp Metering Attacks. Transportation Research, Part B, 2014.
[36] J.-C. Rochet and J. Tirole. Platform Competition in Two-Sided Markets. Journal of the European Economic Association.
[37] S. Rodriguez. Lyft vs. Uber: The battle between the ridesharing rivals intensifies. Los Angeles Times, September 26 2015.
[38] C. Shunk. Average cost of car ownership rises to $8,946 per year. Autoblog, 2012.
[39] T. Slavin. Unless we stop driving cars, all other sustainable transport plans are pointless . The Guardian, 2015.
[40] K. C. Sou, H. Sandberg, and K. H. Johansson. Detection and Identification of Data Attacks in Power System. 2012
American Control Conference, 2012.
[41] K. Spieser, K. Treleaven, R. Zhang, E. Frazzoli, D. Morton, and M. Pavone. Toward a Systematic Approach to the Design
and Evaluation of Automated Mobility-on-Demand Systems: A Case Study in Singapore. in Gereon Meyer, Sven Beiker(editors). Road Vehicle Automation, (Lecture Notes in Mobility), Springer, 2014.
[42] A. Teixeira, D. Perez, H. Sandberg, and K. H. Johansson. Attack Models and Scenarios for Networked Control Systems.
High Confidence Networked Systems, 2012.
[43] K. Thomas, D. Latskiv, E. Bursztein, T. Pietraszek, C. Grier, and D. McCoy. Dialing Back Abuse on Phone Verified
Accounts. ACM CCS Conference, 2014.
[44] A. Toor. Uber wants to expand to 100 Chinese cities over the next year. The Verge, 2015.
[45] N. Trejos. Zipcar expands fleet to more airports. USA Today, 2015.
[46] N. Tufnell. Students hack Waze, send in army of traffic bots. Wired, 2014.
[47] K. Wagner. Lyft Expands, Passes Uber in Total U.S. Cities. Mashable, 2014.
[48] J. Weimer, S. Kar, and K. H. Johansson. Distributed Detection and Isolation of Topology Attacks in Power Networks.
HiCoNS, 2012.
[49] K. Zetter. Hackers can mess with traffic lights to jam roads and reroute cars. Wired, 2014.
[50] B. Zhang. This Study Revealed The Staggering Potential Of Self-Driving Cars. Business Insider, 2014.
[51] R. Zhang and M. Pavone. Control of robotic mobility-on-demand systems: a queueing-theoretical perspective. International
Journal of Robotics Research, 2015.
[52] B. Zhu, A. Joseph, and S. Sastry. Taxonomy of Cyber Attacks on SCADA Systems. Proceedings of CPSCom 2011: The
4th IEEE International Conference on Cyber, Physical and Social Computing, 2011.