  Identifying shortest paths between nodes in a network is an important task in
applications involving routing of resources. Recent work has shown that a
malicious actor can manipulate a graph to make traffic between two nodes of
interest follow their target path. In this paper, we develop a defense against
such attacks by modifying the weights of the graph that users observe. The
defender must balance inhibiting the attacker against any negative effects of
the defense on benign users. Specifically, the defender's goals are: (a) to
recommend the shortest paths possible to users, (b) for the lengths of the
shortest paths in the published graph to be close to those of the same paths in
the true graph, and (c) to minimize the probability of an attack. We formulate
the defense as a Stackelberg game in which the defender is the leader and the
attacker is the follower. In this context, we also consider a zero-sum version
of the game, in which the defender's goal is to minimize cost while achieving
the minimum possible attack probability. We show that this problem is NP-hard
and propose heuristic solutions based on increasing edge weights along target
paths in both the zero-sum and non-zero-sum settings. Relaxing some constraints
of the original problem, we formulate a linear program for local optimization
around a feasible point. We present defense results with both synthetic and
real network datasets and show that these methods often reach the lower bound
of the defender's cost.
