Abstract. 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 [Formula: see text] antistochastic if the probability that a random graph [Formula: see text] satisfies [Formula: see text] is small but, with high probability, there is a small perturbation transforming [Formula: see text] into a graph satisfying [Formula: see text]. While for labeled graphs such properties are easy to obtain from binary covering codes, the existence of antistochastic properties for unlabeled graphs or, in other words, isomorphism-invariant antistochastic properties, is not so evident. If an admissible perturbation is either the addition or the deletion of one edge, we exhibit an isomorphism-invariant antistochastic property that is satisfied by a random graph of order [Formula: see text] with probability [Formula: see text], which is as small as possible. We also express another antistochastic property in terms of the degree sequence of a graph. This property has probability [Formula: see text], which is optimal up to a factor of 2.