Verifying security properties of internet protocol stacks: The split verification approach

We propose a novel method to construct user-space internet protocol stacks whose security properties can be formally explored and verified. The proposed method allows construction of protocol stacks using a C++ subset. We define a formal state-transformer representation of protocol stacks in which the protocol stack is specified in terms of three primary operations, which are constructed from sub-operations, in a compositional manner. We also define a Kripke model that captures the sequencing and attributes of stack operations. We propose a novel approach, called split verification, which combines theorem-proving and model-checking to establish properties for a protocol stack specification. In split verification, properties to be established for the stack are expressed as a combination of properties for primitive operations to be established via theorem-proving as well as temporal properties on operation sequencing, called promotion conditions, to be established via model-checking on the stack operations model. We use abstract Z specifications to represent operation properties and computational tree logic (CTL) formulae to represent promotion conditions. Operation properties are established by checking whether the operation(s) under consideration are correct refinements of the abstract Z specification(s). Our conclusion is that split verification: (a) avoids scalability issues caused by state-space explosion in model-checking and long unwieldy proofs in theorem-proving, and, (b) lowers cost of proof maintenance for localized changes in the stack.