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.
- 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.
- 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.
- 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.
- 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