Formal Firewall Conformance Testing: An Application of Test and Proof Techniques

By Achim D. Brucker, Lukas Brügger, and Burkhart Wolff.

Firewalls are an important means to secure critical ICT infrastructures. As configurable off-the-shelf products, the effectiveness of a firewall crucially depends on both the correctness of the implementation itself as well as the correct configuration. While testing the implementation can be done once by the manufacturer, the configuration needs to be tested for each application individually. This is particularly challenging as the configuration, implementing a firewall policy, is inherently complex, hard to understand, administrated by different stakeholders and thus difficult to validate. This paper presents a formal model of both stateless and stateful firewalls (packet filters), including NAT, to which a specification-based conformance test case generation approach is applied. Furthermore, a verified optimisation technique for this approach is presented: starting from a formal model for stateless firewalls, a collection of semantics-preserving policy transformation rules and an algorithm that optimizes the specification with respect of the number of test cases required for path coverage of the model are derived. We extend an existing approach that integrates verification and testing, that is, tests and proofs to support conformance testing of network policies. The presented approach is supported by a test framework that allows to test actual firewalls using the test cases generated on the basis of the formal model. Finally, a report on several larger case studies is presented.

Keywords:
Model-Based Testing, Conformance Testing, Security Testing, Firewall, Specification-Based Testing, Testing Cloud Infrastructure, Transformation for Testability, HOL-TestGen, Test and Proof, Security Configuration Testing

Please cite this work as follows:
A. D. Brucker, L. Brügger, and B. Wolff, “Formal firewall conformance testing: An application of test and proof techniques,” Software Testing, Verification & Reliability (STVR), vol. 25, no. 1, pp. 34–71, 2015, doi: 10.1002/stvr.1544. Author copy: https://logicalhacking.com/publications/brucker.ea-formal-fw-testing-2014/

BibTeX
@Article{ brucker.ea:formal-fw-testing:2014,
  author    = {Achim D. Brucker and Lukas Br{\"u}gger and Burkhart Wolff},
  journal   = {Software Testing, Verification \& Reliability (STVR) },
  publisher = {John Wiley \& Sons },
  address   = {},
  language  = {USenglish},
  title     = {Formal Firewall Conformance Testing: An Application of Test
               and Proof Techniques},
  volume    = {25},
  number    = {1},
  pages     = {34--71},
  year      = {2015},
  areas     = {security, formal methods},
  doi       = {10.1002/stvr.1544},
  keywords  = {Model-Based Testing, Conformance Testing, Security Testing,
               Firewall, Specification-Based Testing, Testing Cloud
               Infrastructure, Transformation for Testability, HOL-TestGen,
               Test and Proof, Security Configuration Testing},
  abstract  = {Firewalls are an important means to secure critical ICT
               infrastructures. As configurable off-the-shelf products, the
               effectiveness of a firewall crucially depends on both the
               correctness of the implementation itself as well as the
               correct configuration. While testing the implementation can be
               done once by the manufacturer, the configuration needs to be
               tested for each application individually. This is particularly
               challenging as the configuration, implementing a firewall
               policy, is inherently complex, hard to understand,
               administrated by different stakeholders and thus difficult to
               validate. This paper presents a formal model of both stateless
               and stateful firewalls (packet filters), including NAT, to
               which a specification-based conformance test case generation
               approach is applied. Furthermore, a verified optimisation
               technique for this approach is presented: starting from a
               formal model for stateless firewalls, a collection of
               semantics-preserving policy transformation rules and an
               algorithm that optimizes the specification with respect of the
               number of test cases required for path coverage of the model
               are derived. We extend an existing approach that integrates
               verification and testing, that is, tests and proofs to support
               conformance testing of network policies. The presented
               approach is supported by a test framework that allows to test
               actual firewalls using the test cases generated on the basis
               of the formal model. Finally, a report on several larger case
               studies is presented.},
  note      = {Author copy: \url{https://logicalhacking.com/publications/brucker.ea-formal-fw-testing-2014/}},
  pdf       = {https://logicalhacking.com/publications/brucker.ea-formal-fw-testing-2014/brucker.ea-formal-fw-testing-2014.pdf},
}