  We study vulnerability of a uniformly distributed random graph to an attack
by an adversary who aims for a global change of the distribution while being
able to make only a local change in the graph. We call a graph property $A$
anti-stochastic if the probability that a random graph $G$ satisfies $A$ is
small but, with high probability, there is a small perturbation transforming
$G$ into a graph satisfying $A$. While for labeled graphs such properties are
easy to obtain from binary covering codes, the existence of anti-stochastic
properties for unlabeled graphs is not so evident. If an admissible
perturbation is either the addition or the deletion of one edge, we exhibit an
anti-stochastic property that is satisfied by a random unlabeled graph of order
$n$ with probability $(2+o(1))/n^2$, which is as small as possible. We also
express another anti-stochastic property in terms of the degree sequence of a
graph. This property has probability $(2+o(1))/(n\ln n)$, which is optimal up
to factor of 2.
