Provably Valid and Diverse Mutations of Real-World Media Data for DNN Testing

Yuanyuan Yuan, Qi Pang, Shuai WangIEEE Trans. Software Eng 2024 · OpenReview

TL;DR

This paper introduces DEEPWALK, a novel framework for testing deep neural networks (DNNs) by generating diverse and perceptually valid mutated media data. It rigorously formulates and addresses the trade-off between mutation diversity and validity, proving that existing state-of-the-art methods fail on real-world data and proposing a manifold-based approach to overcome these limitations.

What Problem Does This Paper Address?

Deep neural networks (DNNs) are increasingly used in critical applications, but they can still make incorrect predictions. To identify these flaws, researchers need to generate diverse and realistic "mutated" inputs that can trigger these errors. Traditional methods often create mutations that are either too limited in diversity, break the perceptual validity of the data (e.g., an image of a dog no longer looks like a dog), or rely on imprecise heuristics. State-of-the-art generative models, while capable of producing infinite inputs, often fail to maintain perceptual validity for real-world data, leading to meaningless outputs. This paper addresses the challenge of generating mutated media data (images, audio, text) that are both perceptually diverse and valid, ensuring that triggered DNN faults are meaningful and not due to malformed inputs.

Methods

The core of DEEPWALK lies in its use of data manifolds. The authors propose that real-world media data, despite its high dimensionality, can be represented in a lower-dimensional "manifold" that captures its perceptual properties.

  1. Manifold Construction: DEEPWALK uses Generative Adversarial Networks (GANs) to learn these manifolds offline. Crucially, it handles different types of data (images, audio, text) and even different classes within those types by constructing separate manifolds.
  2. Perceptual Mutation: In the online testing phase, DEEPWALK "walks" on these learned manifolds. By moving along specific directions and step sizes on the manifold, it generates new data points that correspond to perceptually altered versions of the original data. This allows for mutations that change specific perceptual traits (e.g., a dog's posture) while preserving overall validity.
  3. Footprint-Aware Mutation: To balance exploration (finding new behaviors) and exploitation (leveraging successful mutation strategies), DEEPWALK uses a "footprint-aware" mutation strategy. It tracks successful mutation directions and step sizes on the manifold to guide future mutations, aiming to trigger more DNN behaviors.
  4. Sensitivity-Based Validation: To ensure perceptual validity, DEEPWALK prunes mutated data points that exhibit high "sensitivity" (measured by the Jacobian Frobenius Norm), as these are more likely to be out-of-manifold and thus perceptually invalid.

Datasets

The paper evaluates DEEPWALK on a variety of datasets across different media types and tasks:

  • Image Classification: ImageNet, CIFAR10
  • Autonomous Driving: CityScape (for driving scenes)
  • Machine Translation: SNLI (Stanford Natural Language Inference) dataset
  • Audio Classification: SC09 (spoken digits)

The authors use training data from the tested DNNs as seed corpus for manifold construction, simulating a realistic testing scenario.

Key Insights and Ideas

  • The "None Land" Problem: The paper rigorously proves that existing state-of-the-art generative model-based methods fail on real-world data because they map diverse data onto a single unified latent space. When the data has large inter-class distances (D) and many classes (K), this leads to generated outputs falling into a "None" region – meaningless data that is neither diverse nor valid.
  • Manifolds as the Key: By treating data as residing on distinct manifolds, DEEPWALK can maintain perceptual validity while achieving high diversity. This is because manifolds inherently capture the underlying perceptual structure of the data.
  • Perceptual Mutations are Powerful: The core idea of "walking on the manifold" allows for controlled, perceptual-level mutations that are more meaningful than byte-level changes or simple transformations. This approach is format-agnostic and doesn't require domain-specific knowledge.
  • Diversity and Validity are Intertwined: The paper provides theoretical backing for the trade-off between diversity (DIV) and validity (VAL), showing how they are intrinsically linked. DEEPWALK's approach aims to maximize DIV while retaining VAL through its manifold-based mutation and sensitivity-based pruning.

Key Results

  • Outperforms Baselines: DEEPWALK consistently outperforms prior mutation and generation methods in terms of testing comprehensiveness (e.g., Neuron Coverage, TensorFuzz Coverage) across various DNNs and tasks. For instance, it achieved significantly higher coverage increases.
  • Higher Quality Faults: DEEPWALK finds more error-triggering inputs, and these inputs are of higher quality, leading to better DNN repair. Retraining DNNs with DEEPWALK-generated inputs resulted in higher accuracy improvements (e.g., +7.13% for ImageNet, +0.5% for CIFAR10) compared to other methods.
  • Generalizability: DEEPWALK demonstrates strong generalizability across different media types (image, audio, text), tasks (classification, regression, translation), and DNN architectures (including black-box scenarios).
  • Reduced Invalid Inputs: Unlike prior methods that generated a high percentage of format-invalid images (e.g., 76.96% for TensorFuzz), DEEPWALK generates virtually no format-invalid inputs.

Limitations and Future Work

  • Fine-Grained Annotations: Perceptual mutations can alter fine-grained annotations (e.g., steering angles in driving scenes), potentially harming metamorphic testing if the ground truth changes. The authors suggest future work on constructing "sub-manifolds" to address this.
  • Perception Coverage Metrics: The paper proposes the development of "perception coverage" metrics, which would focus on covering perceptual properties rather than just neuron states, offering a more input-centric view of testing.
  • Interpretable Root Cause Analysis: DEEPWALK's ability to visualize mutations on manifolds could be leveraged for more interpretable root cause analysis of DNN faults.
  • Computational Cost: While DEEPWALK is efficient, manifold construction (especially for complex datasets like ImageNet) can be computationally intensive.

Summary updated

Abstract

Deep neural networks (DNNs) often accept high-dimensional media data (e.g., photos, text, and audio) and understand their perceptual content (e.g., a cat). To test DNNs, diverse inputs are needed to trigger mis-predictions. Some preliminary works use byte-level mutations or domain-specific filters (e.g., foggy), whose enabled mutations may be limited and likely error-prone. State-of-the-art (SOTA) works employ deep generative models to generate (infinite) inputs. Also, to keep the mutated inputs perceptually valid (e.g., a cat remains a “cat” after mutation), existing efforts rely on imprecise and less generalizable heuristics. This study revisits two key objectives in media input mutation — perception diversity ( Div ) and validity ( Val ) — in a rigorous manner based on manifold, a well-developed theory capturing perceptions of high-dimensional media data in a low-dimensional space. We show important results that Div and Val inextricably bound each other, and prove that SOTA generative model-based methods fundamentally fail to mutate real-world media data (either sacrificing Div or Val ). In contrast, we discuss the feasibility of mutating real-world media data with provably high Div and Val based on manifold. Following, we concretize the technical solution of mutating media data of various formats (images, audios, text) via a unified manner based on manifold. Specifically, when media data are projected into a low-dimensional manifold, the data can be mutated by walking on the manifold with certain directions and step sizes. When contrasted with the input data, the mutated data exhibit encouraging Div in the perceptual traits (e.g., lying vs. standing dog) while retaining reasonably high Val (i.e., a dog remains a dog). We implement our techniques in DeepWalk for testing DNNs. DeepWalk constructs manifolds for media data offline. In online testing, DeepWalk walks on manifolds to generate mutated media data with provably high Div and Val . Our evaluation tests DNNs executing various tasks (e.g., classification, self-driving, machine translation) and media data of different types (image, audio, text). DeepWalk outperforms prior methods in terms of the testing comprehensiveness and can find more error-triggering inputs with higher quality. The tested DNNs, after repaired using DeepWalk 's findings, exhibit better accuracy.
BibTeX
@article{yuan2024provably,
  author = {Yuanyuan Yuan and Qi Pang and Shuai Wang},
  title = {{Provably Valid and Diverse Mutations of Real-World Media Data for DNN Testing}},
  journal = {IEEE Trans. Software Eng.},
  year = {2024},
  url = {https://openreview.net/forum?id=p2rAZNyd4f},
}
Figure