# Presentation: 371597

## Using Bigraphs to Model System Architecture

- Clive Blackwell
- Information Security Group
- Royal Holloway, University of London
- Email: C.Blackwell@rhul.ac.uk

## Presentation Outline

- The layered security model
- Introduction to bigraphs
- Modelling critical infrastructure with bigraphs
- Further work

- CSIIRW

- 15/05/2007

## Existing Systematic Models

- Basic Concepts and Taxonomy of Dependable and Secure Computing
- Avizienis, Laprie, Randell and Landwehr
- Longstanding work to Classify the important aspects of dependability including security
- Practical Architectures for Survivable Systems and Networks
- Neumann and Parker organised systems into eight layers for security analysis
- The external environment, user, application, middleware, networking, operating system, hardware and internal environment
- A Common Language for Computer Security Incidents
- Longstaff and Howard present a classification system for network security incidents
- Shows the different types of entity involved in an attack and their interrelationships

- CSIIRW

- 15/05/2007

**Notes:**
We consider this as a logical and useful aid to understanding systems, but we have introduced some new organisational criteria to give a simplified model that has only three layers. 
 The classification can be extended with dual concepts to model the defence, and by explicitly including the semantic and physical aspects of systems as well as computer and networks.

## The Layered Security Model

- Systems are modelled in a three-layer hierarchy
- The *semantic*** **or *conceptual layer* is the top layer
- Includes people, organisations and system requirements
- The *logical layer* is the intermediate layer
- Contains intangible entities including data and software that are stored and processed on computers
- The *physical layer**** ***is the bottom layer
- Represents the physical existence that all entities have in the real world
- Includes both tangible objects and electromagnetic radiation

- CSIIRW

- 15/05/2007

**Notes:**
The purpose of this layer is to carry out the objectives of semantic layer entities, as they cannot interact directly with logical entities. For example, people are represented by a logical proxy such as an account, a process or a cryptographic key to act on their behalf.  In addition, the logical layer contains helper entities such as network routers that aid other logical entities to fulfil their requirements. 

Every subject, object, relationship or piece of information has a physical representation
Any activity carried out by a system is ultimately on behalf of a semantic subject, but the work must take place at the physical layer
Higher layer entities cannot be understood at the physical layer

## Three-layer model with sub-layers

- Each layer can have sub-layers for detailed analysis
- We use Tanenbaum’s five-layer network model as sub-layers of our logical layer
- The link, network and transport layers are intermediate sub-layers
- The upper application and lower physical sub-layers interface to the social and physical layers of our model respectively

- CSIIRW

- 15/05/2007

## Locations and communication

- Each layer has a separate concept of location and distance between entities
- Entities at each layer have different extents, dependencies and interactions
- Entities in different locations use channels to communicate
- Channels at higher layers are virtual, and must use a physical channel to communicate

- CSIIRW

- 15/05/2007

## Modelling protection requirements

- All systems have a horizontal scope at every layer
- Neumann considers four conceptual locations for compromise at every layer
- From outside, above, within and below
- Protection from an external entity at the same layer requires horizontal controls
- Protection from a higher layer entity requires a vertical boundary between the layers
- Insiders should be constrained by partitioning the system with additional internal system boundaries they should not be able to breach
- Some components that control the system must be trusted and so they should be made simple enough to assure
- Conclusion - All entities, apart from unconditionally trusted entities, should be outsiders relative to one or more controls that moderate their use of the system.

- CSIIRW

- 15/05/2007

**Notes:**
Insiders should be constrained by partitioning the system with additional internal system boundaries they should not be able to breach.  However, complete protection from insiders may not be possible, so these controls may use detection and recovery mechanisms such as auditing and redundancy, so that misuse of the system is detected and recovered from, rather than prevented.  Replication is an effective defence against insider attacks by backing up data or providing standby services in separate locations that insiders cannot access. 
They should reside in an inaccessible location at the bottom of the system or use a secure control network to stop external interference

## Representing the 3-layer model using bigraphs

- Any system represented in our model can be transformed into a bigraph
- Use the two levels of bigraphs to represent the lower two layers of our model
- Physical and logical layers are directly modelled
- Locations and communication channels can be physical or logical
- Represented by different types
- Semantic layer is represented indirectly through lower level activities and effects
- Vulnerabilities are never removed by the application of security mechanisms, but are transformed into other vulnerabilities
- All vulnerabilities have a physical or logical location or channel
- The protective mechanism and the channel between the protection and the resource is vulnerable
- Directly modelled by reaction rules in bigraphs, but not considered in most security models
- Keys are stored in locations that must be protected with additional controls
- Cryptographically protected resources exist in a virtual location encapsulated within special nodes that represent the protection
- Attackers have physical and logical scope and powers that can be represented by bigraphs
- Sites represent their location
- External names represent their potential communication
- Rewriting rules specify their powers

- CSIIRW

- 15/05/2007

## Bigraph Purpose

- Bigraphs are graphs with two constituent graphs representing locality and connectivity separately
- They are an attempt at a unifying theory for program semantics
- Have been shown to capture the semantics of the -calculus, Petri nets and mobile ambients faithfully
- Important aid to understanding systems with both physical and logical aspects
- Ubiquitous systems
- Understanding systems at multiple layers is essential for security
- This introduction to bigraphs is based on “Axioms for bigraphical structure” by Robin Milner

- CSIIRW

- 15/05/2007

## Bigraph description

- The ovals are nodes of the bigraph, which are the common component of the underlying place and link graphs.
- Place graph edges are shown implicitly
- The nodes are nested inside each other to represent placing one entity inside another
- Link graph edges are show explicitly
- Each node has ports* *which may be linked to other nodes which models communication
- The linking and the placing of nodes is independent, shown by the way links cross node boundaries in the diagram
- Each external link (shown emerging from the top in the diagram) can be joined to some link of a host bigraph to model external communication

- CSIIRW

- 15/05/2007

**Notes:**
Note - The link graph is actually a hypergraph as indicated by some arcs that link three nodes.

## Place Graph

- A *place graph *G = (V, ctrl, prnt): m****n has:
- An *inner width *m and an *outer width *n, both positive integers
- ctrl: V****** ** represents the kind of nodes
- A *parent map *prnt: mV ****Vn
- Represents n locations with a forest of n trees
- Represents m sites where other bigraphs can be placed
- The prnt map is the usual parent function for trees
- Represents containment
- Places can be real or virtual locations
- Keys, files and programs inhabit virtual locations

- CSIIRW

- 15/05/2007

## Composing Place Graphs

- Each root of the place graph G0 is planted in a site of G1
- Identification points disappear in the composition
- If Gi = (Vi, ctrli, prnti): mimi+1 (i = 0, 1) be place graphs,
- G1  G0 = (V, ctrl, prnt) has prnt = (IdV0  prnt1)  (prnt0  IdV1).
- prnt(p) = prnt0(p) if p m0V0 and prnt0(p)V0
- prnt(p) = prnt1(m) if pV0 and prnt0(p) = mm1
- new parent node in inhabitant graph
- prnt(p) = prnt1(p) if pV1

- CSIIRW

- 15/05/2007

## Link Graphs

- A link graph G = (V, E, ctrl, link): XY
- Finite sets X of inner names, Y of outer names
- Function link: XP  EY called the link map.** **
- The inner names X and ports P are the *points *of G, and the edges E and outer names Y its *links*.
- The link map connects the attachment points to a communication channel
- The interior link graph  has a communication pattern that is enabled by the exterior link graph through the binding between interfaces
- We draw a link graph’s inner names below it, and its outer names above
- Outer names can represent local or global communication
- An outer name is an *open *link, an edge is a *closed *link
- The link graph can represent point-to-point or group communication
- The link map is a hypergraph, so ‘edges’ can connect several points

- CSIIRW

- 15/05/2007

## Composing link graphs

- The outer names of the interior link graph link to an exterior link graph via its corresponding inner names
- Let Gi = (Vi, Ei, ctrli, linki): XiXi+1 (i = 0, 1) be two link graphs, then G1  G0 = (V, E, ctrl, link) has
- link = (IdE0  link1) ○ (link0  IdP1)
- link(p) =** **link0(p) if p  X0P0 and link0(p)E0
- link1(x) if p  X0P0 and link0(p) = x X
- outer name of G0 links to edge, which makes it local to composed graph or to outer name of G1, which potentially makes it global
- link1(p) if pP1

- CSIIRW

- 15/05/2007

## Bigraph Definition

- Define the composition of bigraphs in terms of the underlying operations on their constituent graphs** **
- An* interface *I = m, X consists of
- A positive integer m called a *width*, representing places
- a finite set X   called a *name set*
- A *bigraph *takes the form G = (V, E, ctrl, GP, GL): IJ
- The interfaces I =  m, X and J = n, Y are its *inner *and *outer faces*
- The map from I to J is determined by the underlying place and link graphs
- GP = (V, ctrl, prnt): mn a *place graph *
- GL = (V, E, ctrl, link ): XY a *link graph*

- CSIIRW

- 15/05/2007

**Notes:**
Bigraphs cannot be factored into two separate algebras, one for placing and the other for linking
The combination of a place graph with a link graph to form a bigraph depends crucially on the identity of nodes

## Composing Bigraphs

- The component place and link graphs are our previous examples
- The composition of the two bigraphs are formed from the combinations of the place graphs and link graphs, which have orthogonal operations
- The sites in F indicate where the roots of an inhabitant bigraph G can be placed
- Then the outer names of G are linked to the corresponding inner names of F
- Note that G can be inserted two ways into F
- The two sites of G could represent a communication pattern that is implemented when inserted into F
- Some of the nodes in G could be keys to protect communication over F, which could represent an insecure medium such as the Internet

- CSIIRW

- 15/05/2007

## Reaction Rules

- Different controls can participate in different *reaction *or *rewriting rules*
- Each rule consists of a precondition, which may be transformed into a post-condition* *wherever it occurs
- Both of these conditions are bigraphs
- Atomic nodes do not have internal nodes
- Complex nodes can be active or passive
- The control is *active *if reactions can occur inside them
- It is *passive *if no internal reaction is allowed
- The only method of reaction possible is when the passive nodes are destroyed

- CSIIRW

- 15/05/2007

## Critical Infrastructure

- Very complex systems that are very difficult to analyse manually
- Large numbers of physical and computational entities and communication paths, and people with various powers
- Large horizontal physical and logical scope
- Allows pervasive access
- Subject to both physical and logical attacks on resources, control systems and communication links
- Intractable problem to avoid attacks
- Large and unmitigated number of vulnerabilities
- Goals of model in critical infrastructure protection
- Finds vulnerabilities
- Unexpected dependencies difficult to discover manually
- Suggest remediation measures
- Remove critical vulnerabilities
- Continue in face of an attack
- Avoid catastrophic failure modes
- Helps in design of system
- Avoid critical failure
- Partition systems to limit damage of successful attack

- CSIIRW

- 15/05/2007

**Notes:**
Very complex systems that are very difficult to analyse manually
Large numbers of physical and computational entities and communication paths, and people with various powers
Large horizontal physical and logical scope 
Allows pervasive access
Subject to both physical and logical attacks on resources, control systems and communication links 
Intractable problem to avoid attacks
Large and unmitigated number of vulnerabilities
Goals of model in critical infrastructure protection
Finds vulnerabilities
Unexpected dependencies difficult to discover manually
Suggest remediation measures
Replication of critical resources 
Continue in face of an attack
Avoid catastrophic failure modes
Helps in design of system 
Avoid critical failure
Partition systems to limit damage of successful attack

## Critical Infrastructure (2)

- The bigraph representation of our three-layer model can faithfully represent critical infrastructure.  It can:
- Check objectives are satisfied
- Can give assurance of protection of critical assets or indicate critical vulnerabilities
- Model architectural protection using defence-in-depth
- Model dependencies between components
- Discover linkage between layers
- Can discover attacks that operate and have effects at several layers
- Handle remote effects and dependencies
- Including transitive attacks that operate in several stages
- Represent attackers in various locations with various powers
- Including insider attacks
- Model different types of network and the interaction between them
- Model different scenarios by changes to attacker and defender

- CSIIRW

- 15/05/2007

**Notes:**
Our three-layer model can faithfully represent critical infrastructure systems: 
Check goal satisfaction
Can model dependencies between components
Linkage between layers
Can discover attacks that have operate and have effects at several layers
Encapsulation of entities within other entities
Can model architecture and design heuristics such as defence in depth 
Attackers in various locations with various powers
Can model insider attacks
Can handle remote effects and dependencies
Can handle transitive attacks that operate in several stages
Can models different types of network and the interaction between them
Can model what if attacks by changes to attacker and defender
Can give assurance of protection of critical nodes or indicate reliance on trusted nodes
Can discover critical assets and vulnerabilities
Can help with network architecture design 

## Critical infrastructure example

- Nodes of different types
- Outermost ellipses are buildings
- Circles are computers or machines
- Intermediate size ellipses may represent rooms
- Representing requirements
- The lower large ellipse represents a building containing a room with a telecommunication exchange or controller for an electricity substation S that can be accessed and controlled through the administrator’s workstation
- One defence goal is that there should be no path from the outside to S by either physical or logical means from unauthorised people or malware
- Cryptographic channels
- The administrator’s computer can be accessed remotely if the correct key is used for authentication, which is indicated by the graph reaction rule as shown

- CSIIRW

- 15/05/2007

## Critical Infrastructure example (2)

- A user can access the administrator’s workstation remotely when he authenticates by proving he has access to the key K represented in the reaction rule
- The defence initially set up the authentication mechanism
- Represented by the reverse of the reaction rule with the arrow in the opposite direction
- S can be accessed in multiple ways from outside
- Logically through transitive access via the administrator’s workstation A
- Physically by entering the building and then the room
- Via a multi-layer hybrid attack where both logical and physical accesses are combined
- The link to the room containing S could be used to send a command having a physical effect such as cutting the power supply to S
- All these controls can be represented using bigraphs and model checking could determine if the attacker can breach any of the controls to interfere with S

- CSIIRW

- 15/05/2007

## Conclusion

- We demonstrated an informal three-layer model for modelling security architecture
- We formalised the model using bigraphs
- We used bigraphs to analyse a simple critical infrastructure example
- We suggested how the model unifies the treatment of insiders and outsiders
- We have used the model to represent cryptographic primitives (NSPW 2007 submission)
- We are investigating Kerberos, a complex network security protocol, that considers both physical and logical vulnerabilities

- CSIIRW

- 15/05/2007

## Model References

- Avizienis, A, Laprie JC, Randell B and Landwehr C, “Basic Concepts and Taxonomy of Dependable and Secure Computing”, *IEEE Transactions on Dependable and Secure Computing*, vol 1, no 1 (2004).
- Neumann, PG, “Practical Architectures for Survivable Systems and Networks”, (2000), online at _[www.csl.sri.com/neumann](http://www.csl.sri.com/neumann)__._
- Howard JD and Longstaff TA, “A Common Language for Computer Security Incidents”, Sandia National Laboratories (1998), online at _[www.sandia.gov](http://www.sandia.gov/)__._

- CSIIRW

- 15/05/2007

## Bigraph References

- Blackwell C, “Using bigraphs to represent cryptographic primitives”, submitted to ACM New Security Paradigms Workshop (2007).
- Milner R (2005), “Axioms for bigraphical structure” (revised version of Cambridge Computer Laboratory Technical Report 581) at _[www.cl.cam.ac.uk/users/rm135](http://www.cl.cam.ac.uk/users/rm135)__._
- Milner R (2005), “Bigraphs, a Tutorial”, at _[www.cl.cam.ac.uk/users/rm135](http://www.cl.cam.ac.uk/users/rm135)__._

- CSIIRW

- 15/05/2007