Organizing Electronic Services into Security Taxonomies

Paul S. Pedersen
Los Alamos National Laboratory
Mail Stop B265
Los Alamos, NM 87545
pedersen@lanl.gov

Disclaimers, etc.

This research was performed while the first author was with Los Alamos National Laboratory, and this paper is registered as a Los Alamos Unclassified Release. This research was sponsored in part by the Department of Energy, under contract number W-7405-ENG-36. The views and conclusions contained in this document are those of the authors alone.

Abstract

1. The Problem

However, between the decision to enter the electronic marketplace and the decision to deploy a specific service via a specific delivery method lies a period of exploration. We believe research needs to address this gap: how to illuminate the issues and tradeoffs between variations of services and delivery technologies. We offer this paper as an initial contribution: an attempt to extract a systematic methodology from our work in this area.

In general, vulnerability analysis consists of specifying the vulnerabilities and points of attack to which a given service is susceptible. However, in practice, we have found that managers considering electronic delivery usually provide a large set of related services, and implicitly expect the analysis to communicate the tradeoffs between vulnerabilities and features. Consequently, the ability to organize a set of services into a structure that clearly and concisely expresses their relations and their security risks is crucial for such an analysis to be effective. The understanding that an effective vulnerability analysis provides is, in turn, crucial for the decision on deploying electronic services to be sound.

The question, then, is how to construct and express this structure. Brute force enumeration of services and risks is inefficient and fails to meet the customer's implicit goals. Ad hoc methods require re-invention with each new set of services, and can fail to communicate the tradeoffs effectively. Furthermore, these methods do not scale to large sets of services---and communicating anything effectively for a large set requires understanding and exploiting organization inherent in that set.

On the other hand, a systematic methodology provides both efficiency for the analyst as well as effective communication for the customer. Furthermore, a sufficiently general methodology can also apply directly to organizing points of attack (since these are essentially just potential services unintentionally offered to the adversary). Additionally, a sufficiently expressive methodology can provide an understanding of the structure underlying a given set of services, which in turn can reveal when that set is incomplete.

>From our experience in organizing electronic services into security taxonomies as part of vulnerability analyses, we have developed a general, systematic methodology that uses the structure of a service set to organize and enumerate the corresponding vulnerability set. This methodology offers many advantages over ad hoc approaches, including making it easier to propagate changes in services to changes in vulnerabilities, to construct a complete list of vulnerabilities, to construct structured countermeasures, and to bring conciseness to service and vulnerability specifications (in some cases, reducing the length from exponential to polynomial).

Section 2 gives a theoretical presentation of the methodology. Section 3 applies the methodology to real-world examples from the domain of kiosk systems. We chose kiosk systems, since they are representative of a wide range of security issues in electronic commerce, from point-of-sale devices to networks to remote servers, from tamper-hardened public machines running dedicated browsers accessing a set of pages residing entirely on local CD-ROM to off-the-shelf private machines running Web browsers accessing the entire Web.

2. The Methodology

2.1. Definitions

Definition 1. An electronic service is an offered action characterized by some specific goal (which is usually defined loosely and imprecisely) and carried out via some computational device.

Examples of electronic services include transferring funds between savings and checking accounts via Automatic Teller Machines, and filing a 1040 tax form via the World Wide Web.

Typically, designers characterize a service by explicitly listing some correctness properties, but leaving many others unstated. Usually these properties divide into a small primary class (characterizing the basic functionality of the service) and a larger secondary class (characterizing all the extra conditions necessary for the service to be correct, fault-tolerant, secure, etc.). Fully enumerating the correctness properties that a service is implicitly expected to satisfy is often a substantial challenge in security analysis. For example, designers of a certain Automatic Teller Machine system failed to make explicit the assumption that no customer would ever initiate a ``withdraw cash'' transaction but leave the cash in the machine [4]. As a consequence, clients engaging in this unanticipated behavior forced machines into bizarre failure modes.

Definition 2. An implementation is a collection of hardware and software that realizes a particular service. In particular, an implementation must satisfy the primary correctness properties of a service. (However, in order to be fully correct, secure, and fault-tolerant, an implementation must satisfy all the properties.) For a service s, define IMP(s) to be the set of implementations of service s.

We assume that ``implementations'' are specified with granularity sufficiently coarse that two services can share an implementation. For example, if services s<sub>1</sub> and s<sub>2</sub> truly differ, than their implementations must differ at some close level of inspection---perhaps the code is not identical. However, such close scrutiny would prevent discussion of facts such as ``a kiosk with sufficient database access to implement change-of-address can also implement a guide to local stores''---hence our assumption.

Definition 3. Let s be a service. For an implementation I of this service, a vulnerability of I is a potential action that causes some of the correctness properties of the service to fail to hold. A vulnerability of s is the set of vulnerabilities common to all implementations of s. Define VULN(I) to be set of vulnerabilities of implementation I, and VULN(s) to be the set of vulnerabilities of service s.

2.3. Concisely Specifying Sets

Implementations

Vulnerabilities

• Should ``A followed by B'' also be a member? What if A is ``blow up the kiosk?''

• Should ``A and B concurrently'' be a member?

• If A' is not a member, should ``A' followed by B'' be a member? What if A' enables B?

We provide one sample solution to this problem. First, we define compound actions.

Definition 4. For actions A and B, define [A;B] to be the compound action consisting of doing A first, then doing B.

We now examine when such compound actions can be vulnerabilities. We consider the system consisting of implementation plus attacker to be in a particular state. With each action A we can associate two items:

• A set PRE_A consisting of all possible states of the system in which A can be applied. (As with implementation sets, this set might be expressed succinctly as a list of conditions which a state must satisfy.)

• A function FUN_A that indicates how A transforms systems states.

• PRE_[A;B] == FUN_A^-1 (PRE_B)

• FUN_[A;B] == FUN_B composed with FUN_A

This calculus lets us build a closure rule, specifying when compound actions can be vulnerabilities:

• Suppose for B in VULN(s), action A satisfies FUN_A^-1(PRE_B) is not empty. Then [A;B] is in VULN(s).

Enumerating some VULN(s) or VULN(I) reduces to enumerating some small set of atomic attacks, and then specifying the closure rule or rules which expand the atomic set into the full set.

This sample solution ignores the challenge of attacks composed of concurrent actions. Indeed, the problem of specifying all possible action combinations that comprise attacks is essentially the same as specifying all possible behaviors of computational devices (potentially with parallelism and randomization) -- which is a problem that has received much attention in its own right (e.g., [8]). This solution also ignores the challenges raised by complex correctness properties -- e.g., if a service must satisfy ``X or Y,'' then an allowable sequence of two actions that subvert X and Y respectively may be a vulnerability (unless the second action re-enables X). Fully exploring these problems lies beyond the scope of this paper; we will use our simple solution, but note that a suite of more advanced solutions may apply.

2.3. Vulnerabilities and the Service Order

2.3.1. The Service Order

Definition 5. For services s₁ and s₂, define s₁ <= s₂ when IMP(s₂) is a subset of IMP(s₁). Define s₁ < s₂ when this containment is proper.

This relation is a partial order: It is irreflexive: for no service s₁ can it be the case that s₁ < s₁. It is transitive: for services s₁, s₂, s₃, if s₁ < s₂ and s₂ < s₃ then s₁ < s₃. (Partial orders and lattices show up in previous security work---e.g.,[2,3,7]---but in different contexts from here.)

We can represent this structure by a directed acyclic graph:

Definition 6. For a finite set S and partial order <, define GRAPH(S,<) to be the directed graph consisting of:

• for each s in S, a node NODE_s;

• for all s₁,s₂ \in S, an edge NODE_s1 --> NODE_s2 exactly when s₁ < s₂.

The graph GRAPH(S,<) is transitively closed, since the order < is transitive. However, this graph is highly redundant: if edges exist from NODE_s1 to NODE_s2 and from NODE_s2 to NODE_s3, then an edge also exists from NODE_s1 to NODE_s3, even though the first two edges comprise a path from NODE_s1 to NODE_s3. It is easily shown that such a graph has a unique transitive reduction, where all redundant edges -- such as the one in this example from NODE_s1 to NODE_s3 -- are removed. This reduced graph still reflects the original order: s₁ < s₂ exactly when a path exists from NODE_s1 to NODE_s2.

Definition 7. For a finite set S and partial order <, define RGRAPH(S,<) to be the directed graph consisting of:

• for each s in S, a node NODE_s;

• for all s₁ and s₂ in S, an edge NODE_s1 --> NODE_s2 exactly when

  • s₁ < s₂

  • for no s₃ in S does s₁ < s₃ < s₂

The edges that remain in RGRAPH(S,<) represent the quantum steps in the service set. We introduce notation for these steps, and for the differences that separate a weaker service from a stronger one.

Definition 8. For s₁ and s₂ in S, define s₁ --> s₂ when NODE_s1 --> NODE_s2 in RGRAPH(S,<).

Definition 9. For any s₁ < s₂, define DIFF(s₁, s₂) to be the differences between s₂ and s₁. If the implementation sets are specified via a requirement list, then DIFF(s₁, s₂) would just be the set difference between the requirements for IMP(s₂) and those for IMP(s₁).

Definition 10. We write s₁ --d--> s₂ when s₁ --> s₂ and d = DIFF(s₁, s₂).

2.3.2. The Structure of the Service Order

• Are the individual quantum steps indeed quantum?

  • Can there exist sub-quanta? If s₁ --d--> s₂, can we split d into d₁ and d₂, and then introduce a new service s' with s₁ --d₁--> s' --d₂--> s₂?

  • Is the ``quantum'' step in fact a continuum? Is the continuum even a total order?

• Are the quantum steps independent? Suppose:

  s₁ --d₁--> s₂ --d₂--> s₃

  Can there exist services that accumulate these steps in a different order? For example, consider the possibility of an s' such that:

  s₁ --d₂--> s' --d₁--> s₃

  In general, should straight lines be lattices? That is, suppose RGRAPH(S,<) has a straight-line structure:

  s₁ --d₁--> s₂ --d₂--> ... --d_k--> s_k+1

  Often the rest of the lattice has been overlooked: the graph should really consist of all s_P such that:

  • P is a subset of {1,...,k} (with s_emptyset = s₁ and s_{1,...,k} = s_k+1)

  • s_P --d_i--> s_P' (when i not in P and P' is the union of P with {i})

2.3.3. Vulnerabilities and Ordering

Theorem 1. Let s₁ and s₂ be services. If s₁ < s₂, then VULN(s₁ is a subset of VULN(s₂).

Theorem 2. Let s₁ and s₂ be services, with s₁ < s₂. If B is in VULN(s₂) and action A subverts DIFF(s₁,s₂), then [A;B] is in VULN(s₁).

We also note the closure rule from Section 2.2 characterizing an implicit closure property for vulnerability sets:

Closure Rule. If B is in VULN(s) and action A satisfies FUN_A^-1 (PRE_B) not empty, then [A;B] is in VULN(s).

2.4. A Systematic Methodology

We begin with a set S of proposed services. We first consider construction of the service hierarchy:

• First, specify, for each s in S, the hardware and software configurations characterizing the implementations IMP(s).

• Use these implementation sets IMP(s) to order the services (e.g., to construct the transitively closed directed acyclic graph GRAPH(S,<)).

• Reduce GRAPH(S,<) to its transitive reduction RGRAPH(S,<), specifying the quantum steps in the service order.

• For each quantum step s₁ --> s₂ in this service order, determine the d that separates s₁ from s₂.

• Examine these quantum steps for completeness:

  • Is the step really quantum? If it can be further subdivided, then do so. If it is a continuum, then decide on a discrete approximation -- and explicitly indicate that this is only an approximation.

  • Are there sets of independent steps? If so, complete the lattice by adding any necessary new services.

Having constructed the service hierarchy, we next consider the vulnerabilities. We note that RGRAPH(S,<) has minimal services (that is, a service s₂ such that no s₁ exists with s₁ < s₂)---these are just the sources of the directed graph.

• For each minimal service s in RGRAPH(S,<), enumerate the basic vulnerabilities of s.

• Suppose s₁ --d--> s₂ and we have enumerated the basic vulnerabilities of s₁. We then enumerate the additional vulnerabilities of s₂. (Depending on S and d, these may be simply be the additional risks associated with the capabilities enabled by d).

• We then note that the complete set of vulnerabilities VULN(s) consists of the basic vulnerabilities, along with:

  • VULN(s₁), for all s₁ < s (from Theorem 1)

  • [A;B], for all B in VULN(s₂), s <= s₂, and suitable A (from Theorem 2 and the Closure Rule).

Examples

We note that, although modified for this presentation, these examples are not artificial; they not only originated from customer-directed research (e.g.,[1,5,6]), but also demonstrated by their initially unorganized format the need for a systematic methodology for security taxonomies.

3.1. Kiosk Services

3.1.1. The Initial Hierarchy

• K0 (standalone): providing public, seldom-altered information via a standalone kiosk (e.g., a kiosk in a public square that shows the location of stores downtown).

• K1 (networked): providing public, rapidly-changing information via a networked kiosk system (e.g., the above kiosk, modified to also show the latest specials at the stores).

• K2 (private information): providing private, remote information via a networked kiosk system (e.g., the above kiosk, modified to allow customers to make queries about current credit limits and the status of special orders).

• K3 (transactional): allowing clients to change private, remote information via a networked kiosk system (e.g., the above kiosk, modified to allow customers to pay bills electronically by transferring funds from bank accounts to store accounts).

This hierarchy expresses a range of services our customers were considering, and demonstrates several principles:

• that increasing the power of services requires increasing the power of the supporting kiosk system;

• that increasing power increases the potential vulnerabilities and the concomitant security measures (e.g., K1 requires protecting networks; K2 also requires authenticating clients)---the roots of Theorem 1;

• that attacks which increase the power of systems enable attacks that apply to these more powerful systems (e.g., penetrating user interface barriers in K2 enables data modification attacks natural to K3)---the roots of Theorem 2; and

• that an ordering even exists on ``power''---the roots of the service ordering.

3.1.2. Applying the Methodology

Inadequacies of the Initial Hierarchy

K0 --> K1 --> K2 --> K3

However, when we follow the methodology from Section 2.4, we see that this structure is incomplete: the d that characterize the above steps are not quantum, but are independent.

• Whether a kiosk is networked is independent of other service characteristics. Networks add the ability to interact with remote systems and databases---to extend in space the reach of the kiosk. Furthermore, the degree of this extension is not binary, and indeed not even totally ordered.

• Whether a service involves private information is independent of other service characteristics. Furthermore, privacy concerns can be refined to apply to data provided by the client, data returned to the client, or both.

• Whether a service involves permanent changes is independent of other characteristics. Furthermore, defining what constitutes a ``permanent change'' is tricky. In some sense, all services involve permanent changes, since we cannot roll back the user's experience. However, if we limit ``change'' to databases, we may still include simple informational services that are logged, and we may exclude services (such as generating a ticket) that change states in ways not easily described in terms of database writes. (We have not even mentioned the ambiguity introduced by re-using the distributed systems term ``transaction.'')

Furthermore, the hierarchy fails entirely to describe proposed services that involve a kiosk session initiating an action whose duration exceeds that of the session.

Addressing the Inadequacies

This decomposition yields a set of axes that describe the space of electronic services we had been considering. (However, this description is not unique, since spaces can be described by multiple sets of axes.) To keep our presentation tractable, we use high-level, somewhat subjective criteria.

Three of the six steps characterize the type of activity in the service:

• Spatial Extension. Does the service's reach extend to machines other than the immediate kiosk?

• Temporal Extension. Does the duration of the electronic actions initiated by a service session extend beyond the duration of the service session?

• Permanence. Upon successful completion, does the service make permanent (and significant) changes to the system?

The other three steps characterize the type of data in the service:

• Sensitivity. Is it critical that the system provide correct service?

• Input Privacy. Does the user provide private information as part of the service session?

• Output Privacy. Does the system provide private information to the user as part of a service session?

This set induces 2⁶ different service types: a type K_P for each subset P of the six properties. Following Section 2.3.1, we order these types using a lattice, putting K_P < K_P' when P is a subset of P'.

We offer examples for a few service types:

• Service Type: the empty set
  Example: K0, a standalone kiosk which a user queries for inconsequential public data which is returned immediately.

• Service Type: {sensitivity}
  Example: a kiosk like the one above, that instead provides emergency exit locations.

• Service Type: {spacial extension}
  Example: K1, discussed above.

• Service Type: {spacial extension, input privacy}
  Example: K2 above, for special order status, where users authenticate themselves with passwords.

• Service Type: {spacial extension, input privacy, output privacy}
  Example: K2 above, for credit limit information.

• Service Type: {spacial extension, permanence, input privacy, output privacy, sensitivity}
  Example: K4 above.

• Service Type: {sensitivity, input privacy}
  Example: a standalone kiosk through which a user accesses government services by entering private information, which the kiosk uses to fill out and print an application form (which the user then mails).

• Service Type: {spacial extension, temporal extension, sensitivity, input privacy, output privacy}
  Example: a networked kiosk through which a user accesses government service by entering private information, which the kiosk submits electronically. The response is returned via physical mail later.

We provide a more a thorough enumeration of examples in Chapter 1 in [5].

3.2. Kiosk Vulnerabilities

However, Section 3.1.2 presented these 2⁶ classes by organizing them into a partial order (which in this case consists of a simple lattice). We can then follow our methodology by using this structure to clearly and concisely enumerate the vulnerabilities. In this section, we illustrate this by a set of quick examples.

Basic Vulnerabilities of the Minimal Service

Basic Vulnerabilities of Intermediate Services

• Spatial Extension. Networked systems are subject to the vulnerabilities of disruptions, alteration, or eavesdropping of communications.

• Temporal Extension. Systems that permit users to initiate services that persist longer than the kiosk session introduce vulnerabilities associated with authentication, rights, and ease of launching these spawned processes. For example, temporal extension may permit using a brief session to launch attacks consisting of computationally-intensive and lengthy processes---attacks which temporal containment would render infeasible by forcing the perpetrator to remain exposed at the kiosk.

• Permanent Changes. Systems which permit users to make substantial, permanent changes to system state are directly subject to violation of integrity errors.

• Input Privacy Systems that require users to enter private information are subject to the vulnerability of exposure or alteration of that information.

• Output Privacy. Similarly, systems that return private information to the user are also subject to the vulnerability of exposure or alteration of that information.

• Spatial Extension and Privacy. A networked kiosk system which involves private information risks exposing this information via the network.

• Temporal Extension and Output Privacy. A system in which users launch services that later return private information risks exposing this information to unauthorized persons, because user authentication performed for the service session may no longer apply.

Upward Inheritance

Downward Inheritance

3.3 Kiosk Points of Attack

The Points of Attack

• a set of kiosks, each of which consists of a physical shell housing the internal kiosk operating system and software, accessed via the user interface;

• a network connecting the kiosks to each other and to the central host; and

• various remote sites, connected to the central host via remote lines.

Each of these components suggests a point of attack:

• the kiosk user interface;

• the physical environment of the kiosk;

• a fake kiosk;

• the internal kiosk software;

• the network;

• the insider who writes and controls the software at the kiosks and the central site;

• the remote lines.

An Initial Attempt to Enumerate Threats

• Using a bug or trapdoor to gain access to the operating system, then adding a Trojan Horse to tamper with how user data is processed.

• Using a bug or trapdoor to gain access to the operating system, then using this control to penetrate the software front-end at the main host, and then plant Trojan Horses there.

Enumerating the threats applicable at the kiosk software point of attack, the network point of attack, and the insider point of attack requires referring back to this subset of the user interface threats, with implied modifications.

Exhaustive enumeration leads to an extreme lack of clarity. Certain points of attack have natural threats. Not recognizing the inherent structure in the vulnerability set can result in burying these natural threats in the lists compound attacks at other points of attack. In the above example, the natural threats possible at the kiosk operating system level are never explicitly listed. The reader would go to the OS row, only to find a pointer back to the user interface row, where sufficiently close inspection reveals the natural OS attacks buried in compound attacks of the above form.

Not recognizing the inherent structure in the vulnerability sets also leads to a lack of flexibility. Suppose one discovers another attack possible for an adversary with operating system access. This attack makes new compound attacks possible. Since no central list exists of natural OS attacks, one must manually generate and insert all the new compound attacks throughout the list. This disorganization introduces many opportunities for error.

Similarly, suppose one wishes to use the enumeration of vulnerabilities to consider countermeasure. One can defend against a compound attack of the above forms by defending against the natural attack at the OS level, and also by defending against the enabling attack that granted access to the OS. Exhaustive enumeration will not make this defense structure clear---the defenses against the natural OS attacks will be buried in defenses against compound attacks, scattered throughout the table.

Applying the Methodology

To follow our methodology, we construct the service order by enumerating the quantum steps:

• The user interface precedes the kiosk software, since any attack possible via the user interface is possible by accessing the internal software. A bug or trapdoor in the user interface is an attack that subverts the difference.

• The physical kiosk similarly precedes the kiosk software. Physical penetration is an attack that subverts the difference.

• A fake kiosk similarly precedes the kiosk software. Copying software and connecting to a real kiosk (or its network) are attacks that subvert the difference.

• The kiosk software precedes the insider, since anything that can be done via tampered software can be done by an insider. Penetration of the software front-end to provide full system access is a potential attack subverting the difference.

• The network similarly precedes the insider. Penetration of the network front end to provide full system access is a potential attack subverting the difference.

• The remote line similarly precedes the insider. Penetration of the front end on this connection is a potential attack subverting the difference.

We can enumerate the threats possible at these points of attack simply by:

• moving up the order and enumerating the basic attacks possible at each point;

• noting that Theorem 1 means that any attack possible at lower point is possible at a higher point; and

• noting that Theorem 2 means that attacks at higher points (e.g., using software access to plant Trojan Horses) can be carried out at lower points (e.g., the user interface) by first carrying out an attack subverting the difference (e.g., using a bug or trapdoor in the user interface).

In Chapter 2 in [5], we use this new approach to provide a more complete enumeration.

4. Conclusions

• Collecting in one spot the natural threats for a point of attack makes it easier to communicate them, and to add and delete threats.

• Using the structure of a system to bring out the compound and inherited structure of many threats makes it easier to produce a complete list, and to construct structured countermeasures.

• Using the inherent structure of threats to organize a listing leads to a more concise presentation. Suppose we have a linear order of n points of attack, each with k natural threats and r subverting attacks that transform the point of attack to the next level. A brute force enumeration requires listing Omega(kn² + krⁿ) threats. Our methodology lets us specify this complete set with by listing only O(nk+nr) threats.

As we discussed in Section 1, we offer this work as an attempt to fill a perceived gap. One area of future work will lie in refining and validating our proposed methodology: not against specific services but against classes of services. How well does our session security taxonomy express risks in various approaches to payment over the Internet, or to the latest Web-based front-ends to existing information and data services? Other promising areas may lie in identifying and addressing other gaps.

Acknowledgments

References

[2] D. Bell and L. LaPadula. Secure Computer Systems: Mathematical Foundations and Model. Technical Report M74-244, MITRE Corporation. May 1973.

[3] D.E. Denning. ``A Lattice Model of Secure Information Flow.'' Communications of the ACM. 19: 236-243. May 1976.

[4] D. Fiske. ``Another ATM Story.'' The Risks Digest. Volume 6, Issue 66. 21 April 1988.

[5] J. Hochberg, S.W. Smith, M. Murphy, P. Pedersen, and B. Yantis. Kiosk Security Handbook. Los Alamos Unclassified Release LA-UR-95-1657, Los Alamos National Laboratory. May 1995.

[6] G. Morris, T. Sanders, A. Gilman, S. Adelson, and S.W. Smith. Kiosks: A Technological Overview. Los Alamos Unclassified Release LA-UR-95-1672, Los Alamos National Laboratory. May 1995.

[7] S. W. Smith. Secure Distributed Time for Secure Distributed Protocols. Ph.D. thesis. Computer Science Technical Report CMU-CS-94-177, Carnegie Mellon University. September 1994.

[8] G. Winskel. The Formal Semantics of Programming Languages: An Introduction. MIT Press, 1993.