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. Thus, it is, firstly, important to test both the implementation of a firewall and, secondly, the correct configuration for each use. While the former can be done once and for all by the firewall vendor, the latter needs to be done by the customer for each and every installation. In practice, an extensive compliance test of firewall configurations is often neglected, even if the security risk of wrong configurations is high: NSA found that inappropriate or incorrect security configurations (most often caused by configuration errors at the local base level) were responsible for 80 percent of Air Force vulnerabilities. [16, p. 55] A particular variant of configuration testing is the test of collections of firewalls and routers for their combined behaviour. This is an important scenario for at least two different reasons: first, the security of cloud offerings (for any variant of cloud computing, for example, infrastructure-as-aservice, platform-as-a-service, software-as-a-service) relies on securely separated network segments and thus on correctly configured routers and firewalls. Consequently, the approach discussed in this paper is applicable to any cloud data centre and can support any cloud company in offering secure services to their customers. Second, firewall policies change over time, sometimes modified by different administrators, who may belong to different stake-holders enforcing their own security interests. Depending on the concrete testing scenario, a firewall policy can play the role of a program ('Does a firewall interpret its configuration file correctly?') or the role of a policy specification ('Is protocol x possible from a to b?'). For both implementation integration tests as well as configuration tests, the technique presented in this paper can be used to generate runtime testers used in 'hardwarein-the-loop' scenarios during installation and maintenance. Several approaches for the generation of test cases are well known: while unit-testoriented test generation methods essentially use preconditions and post-conditions of system operation specifications, sequence-test-oriented approaches essentially use temporal specifications or automata based specifications of system behaviour. Usually, firewalls combine both aspects: whereas firewall policies are static, the underlying network protocols may depend on protocol states which some policies are aware of. This combination of complexity and criticality makes firewalls a challenging and rewarding target for security testing in the sense of the ISO 29199 specification [29, Section 4.36], that is, conformance testing of security properties. While there is an overlap of the detectable vulnerabilities, this form of conformance testing complements penetration testing approaches that simulate an attacker trying to circumvent security infrastructures. In this paper, a formal model of firewall policies as packet filtering functions or transformations over them in HOL is presented. Thus, the presented approach can cover data-oriented as well as temporal security policies. On the basis of this formal model, 11] automatically generates abstract test cases. From the latter, concrete test driver can be derived that can be used for both testing firewall implementations as well as network configurations. While applying HOL-TESTGEN 'out-of-the-box' to these kind of model works for smaller policies, it does not scale well to policies of practically relevant size, that is, common rule sets with several hundred rules in medium-sized company networks. The situation is particularly worsened if the underlying state is evolving over time (as in stateful firewalls). To overcome this technical difficulty, a policy transformation strategy that transforms a given policy into a functionally equivalent one while improving the effectiveness of test generation by orders of magnitude is developed. The theorem-prover-based approach allows both to formally prove the correctness of this policy transformation, as well as integrating it into the symbolic computations of HOL-TESTGEN. Summing up, this paper has the following main contributions: 1. a formal model of stateless and stateful firewall policies, instantiating the generic Unified Policy Framework (UPF) [12], 2. a specification-based test generation approach that can be used for testing the correctness of firewall implementations as well as testing that a concrete configuration of a network complies to a given policy specification, 3. a policy transformation approach that is formally proven correct; it is shown to increase the effectiveness of the approach by several orders of magnitude, FORMAL FIREWALL CONFORMANCE TESTING 3 4. a combination of unit and sequence test strategies, providing an efficient test technique for stateful firewalls, and 5. a domain-specific test tool built on top of HOL-TESTGEN that increases the degree of automation as well as the effectiveness of HOL-TESTGEN. This test tool provides an infrastructure for test execution and tracing on real firewalls and networks. This paper extends the previous work of the authors [6, 8, 10, 13, 14] in several aspects: first, partial solutions previously modelled directly in HOL are integrated in the UPF, which allows to highlight common principles. Second, the firewall policy model is extended significantly to include different network models (address representations) as well as pervasive support of NAT. Third, an investigation on the role of the optimisation on the equivalence classes underlying the test generation is added. And, finally, an empirical evaluation covering various aspects of the optimized test generation procedure is provided. The rest of the paper is structured as follows: after an introduction of the preliminaries, that is, Isabelle/HOL and the HOL-TESTGEN approach (Section 2), we discuss the formal model of stateless firewall policies in Section 3. In Section 5 we extend this model to stateful firewall policies. Section 4 presents the transformation of stateless firewall policies and discusses its effect on the underlying equivalence classes. Before the discussion of empirical results in Section 7, we describe our domainspecific test framework in Section 6. Finally, we discuss related work and draw conclusions in Section 8. The presented domain-specific test tool as well as all proofs and examples presented in this paper are part of the HOL-TESTGEN distribution, which can be downloaded from the website: http://www.brucker.ch/projects/hol-testgen/. FORMAL AND TECHNICAL BACKGROUND Isabelle [34] is a generic theorem prover. New object logics can be introduced by specifying their syntax and natural deduction inference rules. Among other logics, Isabelle supports first-order logic, Zermelo-Fraenkel set theory and the instance for Church's higher-order logic HOL, which is the basis of HOL-TESTGEN and which is introduced in this section. Moreover, Isabelle is also a generic system framework (roughly comparable with Eclipse) which offers editing, modelling, code generation, document generation and (as mentioned) theorem proving facilities, to the extent that some users use it just as programming environment for SML or to write papers over checked mathematical content to generate L A T E X output. Many users know only the theorem proving language Isar for structured proofs and are more or less unaware that this is a particular configuration of the system, that can be easily extended. This is what the HOL-TESTGEN system underlying this work technically is: an extended Isabelle/HOL configuration providing specialized commands for a document-centric model-based test generation method. Higher-order logic (HOL) [2, 17] is a classical logic based on a simple type system. It provides the usual logical connectives such as _ ∧ _, _ → _, ¬_ as well as the object-logical quantifiers ∀x. P x and ∃x. P x; in contrast to first-order logic, quantifiers may range over arbitrary types, including total functions f :: α ⇒ β. HOL is centred around extensional equality _ = _ :: α ⇒ α ⇒ bool. HOL is more expressive than first-order logic, because, for example, induction schemes can be expressed inside the logic. Being based on a polymorphically typed λ-calculus, HOL can be viewed as a combination of a programming language such as SML or Haskell, and a specification language providing powerful logical quantifiers ranging over elementary and function types. Isabelle/HOL is a logical embedding of HOL into Isabelle. The simple-type system underlying HOL has been extended by Hindley/Milner style polymorphism with type classes similar to Haskell. Isabelle/HOL offers support for a particular methodology to extend given theories in a logically safe way: a theory extension is conservative if the extended theory is consistent provided that the original theory was consistent. Conservative extensions can be constant definitions, type definitions, datatype definitions, primitive recursive definitions and well-founded recursive definitions. The sorting phase is formalized as a function mapping a list of syntactic policy operators (called combinators) to a list of combinators sorted according to the following principles: • If there is a DenyAll, it should be at the last place. • Rules dealing with the same set of networks should be grouped together, with the DenyAll's coming after the AllowPort's.
A more recent paper on HOL-TestGen REF presents a complete case study and establishes a formal correspondence between the specifications of the program under test and the properties that will be tested after optimization.
Formal firewall conformance testing: an application of test and proof techniques
Softw. Test. Verification Reliab.
Softw. Test. Verification Reliab.
Computer Science