Really Unlearned? Verifying Machine Unlearning via Influential Sample Pairs

Machine unlearning enables pre-trained models to eliminate the effects of partial training samples. Previous research has mainly focused on proposing efficient unlearning strategies. However, the verification of machine unlearning, or in other words, how to guarantee that a sample has been successfully unlearned, has been overlooked for a long time. Existing verification schemes typically rely on machine learning attack techniques, such as backdoor attacks or membership inference attacks. As these techniques are not formally designed for verification, they are easily bypassed when an untrustworthy model provider in MLaaS undergoes rapid fine-tuning to meet the verification conditions only, rather than executing <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">real</i> unlearning. In this paper, we propose a formal verification scheme, IndirectVerify, to determine whether unlearning requests have been successfully executed. We design influential sample pairs: one referred to as <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">trigger samples</i> and the other as <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">reaction samples</i>. Users send unlearning requests regarding trigger samples and use reaction samples to verify if the unlearning operation has been successfully carried out. We propose a perturbation-based scheme to generate those influential sample pairs. The objective is to perturb only a small fraction of training samples to trigger samples, leading to the misclassification of reaction samples. This indirect influence will be used for our verification purposes. In contrast to existing schemes that employ the same samples for all processes, our scheme, IndirectVerify, provides enhanced robustness, making it less susceptible to bypassing processes.