Certifiable Prioritization for Deep Neural Networks via Movement Cost in Feature Space

Although deep neural networks (DNNs) have shown superior performance in different software systems, they also display malfunctioning and can even lead to irreversible catastrophes. Hence, it is significant to detect the misbehavior of DNN-based software and enhance the quality of DNNs. Test input prioritization is a highly effective approach to ensure the quality of DNNs. This method involves prioritizing test inputs in such a way that inputs that are more likely to reveal bugs or issues are identified early on, even with limited time and manual labeling efforts. Nevertheless, current prioritization methods still have limitations in three aspects: certifiability, effectiveness, and generalizability. To overcome the challenges, we propose a test input prioritization technique designed based on a movement cost perspective of test inputs in DNNs’ feature space. Our method differs from previous works in three key aspects: (1) certifiable—it provides a formal robustness guarantee for the movement cost; (2) effective—it leverages formally guaranteed movement costs to identify malicious bug-revealing inputs; and (3) generic—it can be applied to various tasks, data, models, and scenarios. Extensive evaluations across two tasks (i.e., classification and regression), six data forms, four model structures, and two scenarios (i.e., white box and black box) demonstrate our method’s superior performance. For instance, it significantly improves 53.97% prioritization effectiveness on average compared with baselines. Its robustness and generalizability are 1.41 \(\sim \) 2.00 times and 1.33 \(\sim \) 3.39 times that of baselines on average, respectively.