Testing vs. Formal Verification: Complementary Approaches
Both testing and formal verification play important roles in ensuring AI safety. This post explores their strengths, limitations, and how to use them together.
Testing Approaches
Unit Testing
Test individual components:
- Functions and modules
- Data processing pipelines
- Model predictions on examples
Integration Testing
Test component interactions:
- End-to-end workflows
- API compatibility
- System integration
Property-Based Testing
Generate test cases automatically:
- Define properties that should hold
- Generate random inputs
- Check invariants
- Tools: Hypothesis, QuickCheck
Adversarial Testing
Search for failures:
- Adversarial examples
- Edge cases
- Stress testing
- Red teaming
Metamorphic Testing
Test using input relationships:
- Define metamorphic relations
- Generate related inputs
- Check output relationships
- Useful when oracle problem exists
Formal Verification Approaches
Static Verification
Analyze without execution:
- Prove properties for all inputs
- Mathematical guarantees
- No runtime overhead
Dynamic Verification
Monitor during execution:
- Runtime checks
- Assertion checking
- Property monitoring
Comparison
| Aspect | Testing | Formal Verification |
|--------|---------|-------------------|
| Coverage | Sample-based | All inputs (or provable bounds) |
| Guarantees | Confidence | Mathematical proof |
| Scalability | Generally good | Challenging for large systems |
| Cost | Lower | Higher |
| Expertise | Broad availability | Specialized knowledge |
| False positives | None (by design) | Possible with incomplete methods |
| False negatives | Possible | None (with sound methods) |
When to Use Each
Use Testing When:
- Exploring system behavior
- Rapid iteration needed
- Properties hard to formalize
- System too complex for verification
- Budget/time constraints
- Finding common bugs
Use Verification When:
- Safety-critical applications
- Regulatory requirements
- Properties can be formalized
- Complete guarantees needed
- Test oracle problem exists
- Certification required
Combining Approaches
Complementary Strategies
1. Test to find, verify to prove
- Use testing to discover issues
- Use verification for critical properties
2. Verify core, test periphery
- Formally verify safety-critical components
- Test less critical parts thoroughly
3. Verification-guided testing
- Use verification to identify edge cases
- Generate targeted tests
- Focus testing on unverified aspects
4. Test-driven verification
- Start with test cases
- Generalize to formal properties
- Verify those properties
Workflow Integration
Phase 1: Development
- Unit tests for basic functionality
- Property-based tests for invariants
- Continuous testing
Phase 2: Hardening
- Formal verification of core properties
- Adversarial testing
- Metamorphic testing
Phase 3: Deployment
- Runtime monitoring
- Continuous testing in production
- Verification of updates
Best Practices
For Testing
1. Achieve high code coverage
2. Include edge cases
3. Test on diverse, representative data
4. Automate test execution
5. Regular regression testing
6. Document test rationale
For Verification
1. Start with simple properties
2. Prioritize critical safety properties
3. Use appropriate abstraction levels
4. Combine multiple techniques
5. Validate specifications with stakeholders
6. Document assumptions
For Integration
1. Define clear verification goals
2. Allocate resources appropriately
3. Train team in both approaches
4. Use tools that support both
5. Share insights between activities
6. Iterate based on findings
Tools and Ecosystems
Testing Frameworks
- **PyTest**: Python testing
- **Jest**: JavaScript testing
- **Hypothesis**: Property-based testing
- **DeepXplore**: Neuron coverage testing
Verification Tools
- **ERAN**: Neural network verification
- **Marabou**: SMT-based verification
- **TensorFlow Lattice**: Verified monotonicity
- **Coq/Isabelle**: Theorem provers
Integrated Approaches
- **VerifAI**: Testing and verification
- **Scenic**: Scenario specification and testing
- **VEGAS**: Verification-guided testing
Case Studies
Autonomous Driving
- Test: Simulation scenarios, real-world data
- Verify: Collision avoidance, lane keeping
- Monitor: Runtime safety checks
Medical Diagnosis
- Test: Clinical validation, diverse patient data
- Verify: Robustness bounds, fairness constraints
- Monitor: Confidence thresholds
Financial Systems
- Test: Historical data, stress scenarios
- Verify: Regulatory compliance, bounds
- Monitor: Anomaly detection
Future Directions
- **Automated specification inference**: Learn formal specs from tests
- **Scalable verification**: Handle larger, more complex systems
- **Better integration**: Unified tools and workflows
- **Learned components**: Verify learned systems effectively
Conclusion
Testing and formal verification are complementary approaches. Use testing for broad exploration and rapid iteration, verification for critical guarantees. The best approach combines both, leveraging their respective strengths.