Formal-Guided Fuzz Testing: Targeting Security Assurance From Specification to Implementation for 5G and Beyond

Ying Wang, Jingda Yang, Sudhanshu Arya, Ying Wang 0113IEEE Access 2024 · DOI

TL;DR

This paper introduces a novel "formal-guided fuzz testing" approach to automatically discover vulnerabilities in 5G networks. By combining the abstract power of formal verification with the exhaustive testing of fuzzing, they significantly improve efficiency and uncover previously unknown security flaws in 5G protocols and their implementations.

What Problem Does This Paper Address?

The advent of 5G and its increasing reliance on software and virtualization has created a complex ecosystem with a vast attack surface. Ensuring the security of these critical infrastructures is paramount, but traditional security testing methods have limitations. Formal verification, while good at abstracting specifications, can be labor-intensive and doesn't always translate directly to implementation flaws. Fuzz testing, on the other hand, provides comprehensive experimental evaluation but can be computationally expensive and may miss subtle issues if not guided effectively. This paper addresses the challenge of efficiently and comprehensively detecting vulnerabilities across both the protocol designs and their software implementations in 5G systems.

Methods

The core of this work is the "United Formal&Fuzz Systematic Framework (UFSF)," which creates a virtuous, recursive loop between formal verification and fuzz testing.

  1. Protocol Abstraction: Natural language 3GPP specifications are converted into unambiguous symbolic expressions (AAF flow-graphs), then into a properties table and dependency graph. This automates the creation of formal analysis models, reducing manual effort.
  2. Formal-based Vulnerability Detection: Using tools like ProVerif, formal methods are applied to the abstract models to identify potential vulnerabilities and derive "attack traces." This step also helps isolate specific areas for fuzz testing.
  3. Search Space Isolation: The output of formal verification divides the system's security landscape into three zones: provably secure, provably vulnerable (attack traces), and uncertain areas needing further investigation. This significantly narrows down the search space for fuzzing.
  4. Formal Guided Fuzz Testing: Attack traces and uncertain areas identified by formal verification are used to guide fuzz testing. This involves generating specific inputs for fuzzers, focusing on critical identifiers and potential attack vectors. This can be done at both the bit-level and command-level.
  5. Fortification: The vulnerabilities discovered through this combined approach are used to propose solutions and fortifications, which can then be fed back into the formal verification process to refine the models and further narrow search spaces.

This iterative process allows for mutual amplification, where formal methods guide fuzzing, and fuzzing results refine the formal models.

Datasets

The paper does not explicitly mention training or evaluation datasets in the traditional machine learning sense. Instead, it uses the 3GPP technical specifications (TS) and requirements (TR) for 5G protocols as its input for formal analysis. The evaluation is performed on the NSA 5G security processes, specifically focusing on the Radio Resource Control (RRC), Non-access Stratum (NAS), and Access Stratum (AS) authentication processes, using the srsRAN platform for implementation-level testing.

Key Insights and Ideas

  • Synergy is Key: The paper strongly advocates for the synergistic combination of formal verification and fuzz testing, demonstrating that their combined strengths far outweigh their individual limitations.
  • Automated Guidance: By using formal verification to generate specific attack traces and identify uncertain areas, fuzz testing becomes significantly more efficient and targeted, moving beyond random or purely rule-based approaches.
  • Hierarchical Assurance: The UFSF framework enables a hierarchical approach to security assurance, starting from protocol specifications and extending to implementation stacks, providing a more holistic view of system security.
  • Efficiency Gains: The formal-guided approach dramatically reduces the computational complexity of vulnerability detection, transforming exponential growth in computational cost to linear growth.
  • Real-World Impact: The approach successfully identified previously unknown vulnerabilities and attack models in critical 5G authentication processes, demonstrating its practical applicability.

Key Results

  • The authors identified 4 attack model categories and 61 vulnerabilities in the 5G NSA authentication and authorization procedure.
  • In bit-level guided fuzzing, their system uncovered 8 vulnerabilities.
  • In command-level fuzzing, the framework detected 44 vulnerabilities.
  • The proposed formal-guided fuzz testing strategy significantly reduces the number of fuzzing cases compared to brute-force and rule-based methods. For example, for the RRC Connection Request command, it requires only 9 fuzzing cases compared to over 2^45 for brute-force.
  • The approach demonstrated linear growth in computational complexity as the number of commands increased, a significant improvement over the exponential growth of traditional methods.

Limitations and Future Work

  • Scalability for Extremely Large Systems: While the approach significantly improves scalability, the paper acknowledges that for extremely large and complex systems, further optimizations might be needed.
  • Future Work: The authors plan to extend their framework into an automatic multi-dimensional vulnerability detection system with reinforcement loop feedback. This will involve considering a wider variety of data inputs, such as log files and cache states, and expanding the verification and vulnerability detection to other specifications and implementations, including IoT. They also aim to further explore the application of this framework to other protocols in 5G and Future G releases.

Summary updated

BibTeX
@article{wang2024formal,
  author = {Ying Wang and Jingda Yang and Sudhanshu Arya and Ying Wang},
  title = {{Formal-Guided Fuzz Testing: Targeting Security Assurance From Specification to Implementation for 5G and Beyond}},
  journal = {IEEE Access},
  year = {2024},
  doi = {10.1109/access.2024.3369613},
}

Loading related content...

Figure