Membership Inference Attack (MIA) determines the presence of a record in a
machine learning model's training data by querying the model. Prior work has
shown that the attack is feasible when the model is overfitted to its training
data or when the adversary controls the training algorithm. However, when the
model is not overfitted and the adversary does not control the training
algorithm, the threat is not well understood. In this paper, we report a study
that discovers overfitting to be a sufficient but not a necessary condition for
an MIA to succeed. More specifically, we demonstrate that even a
well-generalized model contains vulnerable instances subject to a new
generalized MIA (GMIA). In GMIA, we use novel techniques for selecting
vulnerable instances and detecting their subtle influences ignored by
overfitting metrics. Specifically, we successfully identify individual records
with high precision in real-world datasets by querying black-box machine
learning models. Further we show that a vulnerable record can even be
indirectly attacked by querying other related records and existing
generalization techniques are found to be less effective in protecting the
vulnerable instances. Our findings sharpen the understanding of the fundamental
cause of the problem: the unique influences the training instance may have on
the model.