  Graph-based Anomaly Detection (GAD) is becoming prevalent due to the powerful
representation abilities of graphs as well as recent advances in graph mining
techniques. These GAD tools, however, expose a new attacking surface,
ironically due to their unique advantage of being able to exploit the relations
among data. That is, attackers now can manipulate those relations (i.e., the
structure of the graph) to allow some target nodes to evade detection. In this
paper, we exploit this vulnerability by designing a new type of targeted
structural poisoning attacks to a representative regression-based GAD system
termed OddBall. Specially, we formulate the attack against OddBall as a
bi-level optimization problem, where the key technical challenge is to
efficiently solve the problem in a discrete domain. We propose a novel attack
method termed BinarizedAttack based on gradient descent. Comparing to prior
arts, BinarizedAttack can better use the gradient information, making it
particularly suitable for solving combinatorial optimization problems.
Furthermore, we investigate the attack transferability of BinarizedAttack by
employing it to attack other representation-learning-based GAD systems. Our
comprehensive experiments demonstrate that BinarizedAttack is very effective in
enabling target nodes to evade graph-based anomaly detection tools with limited
attackers' budget, and in the black-box transfer attack setting,
BinarizedAttack is also tested effective and in particular, can significantly
change the node embeddings learned by the GAD systems. Our research thus opens
the door to studying a new type of attack against security analytic tools that
rely on graph data.
