NCSC-TG-030

Library No. S-240,572

Version 1

FOREWORD

A Guide to Understanding Covert Channel Analysis of Trusted Systems provides a set of good

practices related to covert channel analysis. We have written this guide to help the vendor and

evaluator communities understand the requirements for covert channel analysis as described in the

Department of Defense Trusted Computer System Evaluation Criteria (TCSEC). In an effort to

provide guidance, we make recommendations in this technical guide that are not cited in the

TCSEC.

This guide is the latest in a series of technical guidelines published by the National Computer

Security Center. These publications provide insight to the TCSEC requirements for the computer

security vendor and technical evaluator. The goals of the Technical Guideline Program are to

discuss each feature of the TCSEC in detail and to provide the proper interpretations with specific

guidance.

The National Computer Security Center has established an aggressive program to study and

implement computer security technology. Our goal is to encourage the widespread availability of

trusted computer products for use by any organization desiring better protection of its important

data. One way we do this is by supporting the Trusted Product Evaluation Program. This program

focuses on the security features of commercially produced and supported computer systems. We

evaluate the protection capabilities against the established criteria presented in the TCSEC. This

program, and an open and cooperative business relationship with the computer and

telecommunications industries, will result in the fulfillment of our country's information systems

security requirements. We resolve to meet the challenge of identifying trusted computer products

suitable for use in processing information that requires protection.

I invite your suggestions for revising this technical guide. We will review this document as the

need arises.

ACKNOWLEDGMENTS

The National Computer Security Center (NCSC) extends special recognition and acknowledgment

to Virgil D. Gligor as primary author and preparer of this document, to Jonathan K. Millen for

providing significant technical input for the covert channel identification and bandwidth

estimation sections, and to the first covert channel working group of the NCSC (which met from

1989 to 1991) for providing most of the material presented in Appendices A and 1B. Capt. James

K. Goldston (USAF) and Capt. James A. Muysenberg (USAF) are recognized for the development,

editing, and publication of this guide.

We wish to thank the many members of the computer security community who enthusiastically

gave their time and technical expertise in reviewing this guide and providing valuable comments

and suggestions.

TABLE OF CONTENTS

FOREWORD i

ACKNOWLEDGMENTS ii

1.0 INTRODUCTION 1

1.1 Background 1

1.2 Purpose 1

1.3 Scope 3

1.4 Control Objective 3

1.5 Document Overview 4

2.0 COVERT CHANNEL DEFINITION AND CLASSIFICATION 5

2.1 Definition and Implications 5

2.2 Classification 14

2.2.1 Storage And Timing Channels 14

2.2.2 Noisy and Noiseless Channels 20

2.2.3 Aggregated versus Non-Aggregated Channels 21

2.3 Covert Channels and Flawed TCB Specifications 23

3.0 COVERT CHANNEL IDENTIFICATION 25

3.1 Sources of Information for Covert Channel Identification 25

3.2 Identification Methods 27

3.2.1 Syntactic Information-Flow Analysis 28

3.2.2 Addition of Semantic Components to Information-Flow Analysis 32

3.2.3 Shared Resource Matrix (SRM) Method 34

3.2.4 Noninterference Analysis 38

3.3 Potential versus Real Covert Channels 41

3.4 TCSEC Requirements and Recommendations 46

4.0 COVERT CHANNEL BANDWIDTH ESTIMATION 49

4.1 Factors Affecting the Bandwidth Computation 49

4.1.1 Noise and Delay 49

4.1.2 Coding and Symbol Distribution 49

4.1.3 TCB Primitive Selection 50

4.1.4 Measurements and Scenarios of Use 51

4.1.5 System Configuration and Initialization Dependencies 52

4.1.6 Aggregation of Covert Channels 52

4.1.7 Transient Covert Channels 53

4.2 Bandwidth Estimation Methods 53

4.2.1 Information-Theory-Based Method for Channel-Bandwidth Estimation 53

4.2.2 Informal Method for Estimating Covert Channel Bandwidth 60

4.2.3 Differences Between the Two Methods 62

4.3 TCSEC Requirements and Recommendations 63

5.0 COVERT CHANNEL HANDLING 65

5.1 Elimination of Covert Channels 65

5.2 Bandwidth Limitation 67

5.3 Auditing the Use of Covert Channels 72

5.4 TCSEC Requirements and Recommendations 75

5.5 Handling Policies Based on Threat Analysis 76

6.0 COVERT CHANNEL TESTING 81

6.1 Testing Requirements and Recommendations 81

6.2 Test Documentation 81

7.0 SATISFYING THE TCSEC REQUIREMENTS FOR COVERT

CHANNEL ANALYSIS 83

7.1 Requirements for Class B2 83

7.1.1 Covert Channel Analysis 83

7.1.2 Audit 84

7.1.3 Design Documentation 85

7.1.4 Test Documentation 86

7.2 Additional Requirements for Class B3 86

7.2.1 Covert Channel Analysis 86

7.2.2 Audit 87

7.2.3 Design Documentation 87

7.2.4 Test Documentation 87

7.3 Additional Requirements for Class A1 87

ACRONYMS AND ABBREVIATIONS 89

GLOSSARY 91

REFERENCES 99

APPENDIX A ADDITIONAL EXAMPLES OF COVERT CHANNELS 109

A.1 Storage Channels 109

A.1.1 Table-Space Exhaustion Channels 109

A.1.2 Unmount of Busy File System Channels 110

A.1.3 Printer Attachment Channel 110

A.2 Timing Channels 111

A.2.l I/O Scheduling Channels 113

A.2.2 I/O Operation Completion Channels 113

A.2.3 Memory Resource Management Channels 114

A.2.3.1 Data Page Pool Channels 114

A.2.3.2 Active Segment Table Channels 114

A.2.4 Device Controller Contention Channels 115

A.2.5 Exclusive Use of Segments Channels 115

A.2.6 Synchronization Primitive Contention Channels 115

APPENDIX B TOOLS FOR COVERT CHANNEL ANALYSIS 117

B.1 FDM Ina Flow Tool 117

B.1.1 MLS 118

B.1.2 SRM 118

B.2 GYPSY Flow Analyzer 118

B.3 EHDM MLS Tool 119

B.4 Source-code Analysis Tool 121

1.0 INTRODUCTION

1.1 BACKGROUND

The principal goal of the National Computer Security Center (NCSC) is to encourage the

widespread availability of trusted computer systems. In support of this goal, the NCSC created a

metric, the Department of Defense (DoD) Trusted Computer System Evaluation Criteria (TCSEC)

[NCSC TCSEC], against which computer systems could be evaluated.

The TCSEC was originally published on 15 August 1983 as CSC-STD-001-83. In December

1985, the Department of Defense adopted it, with a few changes, as a Department of Defense

Standard, DoD 5200.28-STD. DoD Directive 5200.28, Security Requirements for Automated

Information Systems (AISs) [DoD Directive], requires the TCSEC be used throughout the

Department of Defense. The TCSEC is the standard used for evaluating the effectiveness of

security controls built into DoD AISs.

The TCSEC is divided into four divisions: D, C, B, and A. These divisions are ordered in a

hierarchical manner, with the highest division (A) being reserved for systems providing the best

available level of assurance and security. Within divisions C and B are subdivisions known as

classes, which are also ordered in a hierarchical manner to represent different levels of security in

these divisions.

1.2 PURPOSE

An important set of TCSEC requirements, which appears in classes B2 to A1,is that of covert

channel analysis (CCA). The objectives of CCA are:

· Identification of covert channels;

· Determination of covert channels' maximum attainable bandwidth;

· Handling covert channels using a well-defined policy consistent with the TCSEC

objectives; and

· Generation of assurance evidence to show that all channels are handled according to the

policy in force. To help accomplish these objectives, this guide (1) presents the relative

merits of covert channel identification methods and of the covert channel information

sources, (2) recommends sound bandwidth determination and handling policies and

methods based on the TCSEC requirements, and (3) defines the types of evidence that

should be provided for handling assurance.

This document provides guidance to vendors on what types of analyses they should carry out

for identifying and handling covert channels in their systems, and to system evaluators and

accreditors on how to evaluate the manufacturer's analysis evidence. Note, however, that the only

measure of TCSEC compliance is the TCSEC. This guide contains suggestions and

recommendations derived from TCSEC objectives but which are not required by the TCSEC.

This guide is not a tutorial introduction to any topic of CCA. Instead, it is a summary of

analysis issues that should be addressed by operating systems designers, evaluators, and

accreditors to satisfy the requirements of the B2-A1 classes. Thus, we assume the reader is an

operating system designer or evaluator already familiar with the notion of covert channels in

operating systems. For this reader, the guide defines a set of baseline requirements and

recommendations for the analysis and evaluation of covert channels. For the reader unfamiliar with

CCA techniques used to date, the following areas of further documentation and study may be

useful:

· Mandatory security models and their interpretation in operating systems [Bell and La

Padula76, Biba77, Denning83, Gasser88, Honeywell85a, Honeywell85b,

Luckenbaugh86, Rushby85, Walter74];

· Experience with covert channel identification reported in the literature to date

[Benzel84, Haigh87, He and Gligor90, Karger and Wray91, Kemmerer83, Lipner75,

Loepere85, Millen76, Millen8l, Millen89b, Schaefer77, Tsai90, Wray91];

· Bandwidth estimation techniques using standard information theory [Huskamp78,

Millen89a, Shannon and Weaver64]; informal bandwidth estimation techniques [Tsai

and Gligor88j;

· Covert channel handling techniques [Schaefer77, Shieh and Gligor90, Hu91]; and

· Other TCSEC guidelines relevant to covert channel handling [NCSC Audit, NCSC

Testing].

The reader who is intimately familiar with CCA techniques may want to refer only to the

sections on the "TCSEC Requirements and Recommendations" (i.e., Sections 3.4, 4.3, and 6.1) and

on "Satisfying the TCSEC Requirements for Covert Channel Analysis" (Chapter 7).

1.3 SCOPE

This guide refers to covert channel identification and handling methods which help assure that

existent covert channels do not compromise a system's secure operation. Although the guide

addresses the requirements of systems supporting the TCSEC mandatory policy, the analysis and

handling methods discussed apply equally well to systems supporting any nondiscretionary (e.g.,

mandatory) security policy [Saltzer and Schroeder75]. We make additional recommendations

which we derive from the stated objectives of the TCSEC. Not addressed are covert channels that

only security administrators or operators can exploit by using privileged (i.e., trusted) software. We

consider use of these channels an irrelevant threat because these administrators, who must be

trusted anyway, can usually disclose classified and sensitive information using a variety of other

more effective methods.

This guide applies to computer systems and products built with the intention of satisfying

TCSEC requirements at the B2-A1 levels. Although we do not explicitly address covert channels

in networks or distributed database management systems, the issues we discuss in this guide are

similar to the ones for those channels.

1.4 CONTROL OBJECTIVE

Covert channel analysis is one of the areas of operational assurance. As such, its control

objective is that of assurance. The assurance objective provided in [NCSC TCSEC] is the

following:

Systems that are used to process or handle classified or other sensitive information must be

designed to guarantee correct and accurate interpretation of the security policy and must

not distort the intent of that policy. Assurance must be provided that correct

implementation and operation of the policy exists throughout the system's life-cycle.

This objective affects CCA in two important ways. First, covert channels are the result of an

implementation of a nondiscretionary security policy at the operating system level; therefore,

depending on how this policy is implemented within a given system, the resulting system will have

fewer or more covert channels. Second, the existence of covert channels poses a potential threat to

the use of the mandatory policy throughout the system's life cycle. Thus, the identification and

handling of covert channels represents an important tenet of mandatory policy support in B2-A1

systems.

1.5 DOCUMENT ORGANIZATION

This guide contains seven chapters, a glossary, a bibliography, and two appendices. Chapter

2 reviews various definitions of covert channels, presents the policy implications of those

definitions, and classifies channels. Chapter 3 presents various sources of covert channel

information and identification methods, and discusses their relative practical advantages. Chapter

4 describes bandwidth estimation and illustrates a technique based on standard information theory

that can be applied effectively in practice. Chapter 5 reviews various covert channel handling

methods and policies that are consistent with the TCSEC requirements. Chapter 6 discusses covert

channel testing and test documentation. Chapter 7 presents TCSEC requirements for CCA, and

includes additional recommendations corresponding to B2-A1 evaluation classes. The glossary

contains the definitions of the significant terms used herein. The bibliography lists the references

cited in the text. Appendix A cites some examples of storage and timing channels. Appendix B

describes the capabilities of several tools for covert channel identification.

2.0 COVERT CHANNEL DEFINITION AND CLASSIFICATION

In this chapter we provide several definitions of covert channels and discuss the dependency

of these channels on implementations of nondiscretionary access control policies (i.e., of policy

models). Also, we classify channels using various aspects of their scenarios of use.

2.1 DEFINITION AND IMPLICATIONS

The notion of covert communication was introduced in [Lampson73] and analyzed in

[Lipner75, Schaefer77, Huskamp78, Denning83, Kemmerer83], among others. Several definitions

for covert channels have been proposed, such as the following:

· Definition 1 - A communication channel is covert if it is neither designed nor intended

to transfer information at all. [Lampson73] (Note: Lampson's definition of covert

channels is also presented in [Huskamp78].)

· Definition 2 - A communication channel is covert (e.g., indirect) if it is based on

"transmission by storage into variables that describe resource states." [Schaefer77]

· Definition 3 - Covert channels "will be defined as those channels that are a result of

resource allocation policies and resource management implementation." [Huskamp78]

(Note: The computing environment usually carries out resource allocation policies and

implementation.)

· Definition 4 - Covert channels are those that "use entities not normally viewed as data

objects to transfer information from one subject to another." [Kemmerer83]

The last three of the above definitions have been used successfully in various security designs

for new and retrofitted operating systems and in general covert channel analyses. However, none

of the above definitions brings out explicitly the notion that covert channels depend on the type of

nondiscretionary access control (e.g., mandatory) policy being used and on the policy's

implementation within a system design. A new definition using these concepts can be provided that

is consistent with the TCSEC definition of covert channels, which states that a covert channel is "a

communication channel that allows a process to transfer information in a manner that violates the

system's security policy."

· Definition 5 - Given a nondiscretionary (e.g., mandatory) security policy model M and

its interpretation I(M) in an operating system, any potential communication between

two subjects I(Sh) and I(Si) of I(M) is covert if and only if any communication between

the corresponding subjects Sh and Si of the model M is illegal in M. [Tsai90]

The above definition has several consequences that help explain the relevance (or lack thereof)

of covert channels to different access control policies, as listed below:

(1) Irrelevance of Discretionary Policy Models

The above definition implies that covert channels depend only on the interpretation of

nondiscretionary security models. This means the notion of covert channels is irrelevant to

discretionary security models.

Discretionary policy models exhibit a vulnerability to Trojan Horse attacks regardless of their

interpretation in an operating system [NCSC DAC, Gasser88]. That is, implementations of these

models within operating systems cannot determine whether a program acting on behalf of a user

may release information on behalf of that user in a legitimate manner. Information release may take

place via shared memory objects such as files, directories, messages, and so on. Thus, a Trojan

Horse acting on behalf of a user could release user-private information using legitimate operating

system requests. Although developers can build various mechanisms within an operating system

to restrict the activity of programs (and Trojan Horses) operating on behalf of a user [Karger87],

there is no general way, short of implementing nondiscretionary policy models, to restrict the

activity of such programs. Thus, given that discretionary models cannot prevent the release of

sensitive information through legitimate program activity, it is not meaningful to consider how

these programs might release information illicitly by using covert channels.

The vulnerability of discretionary policies to Trojan Horse and virus attacks does not render

these policies useless. Discretionary policies provide users a means to protect their data objects

from unauthorized access by other users in a relatively benign environment (e.g., an environment

free from software containing Trojan Horses and viruses). The role of nondiscretionary policies is

to confine the activity of programs containing Trojan Horses and viruses. In this context, the

implementation of mandatory policies suggested by the TCSEC, which forms an important

subclass of nondiscretionary security policies, must address the problem of unauthorized release

of information through covert channels.

(2) Dependency on Nondiscretionary Security Policy Models

A simple example illustrates the dependency of covert channels on the security policy model

used. Consider a (nondiscretionary) separation model M that prohibits any flow of information

between two subjects Sh and Si Communication in either direction, from Sh to Si and vice versa, is

prohibited. In contrast, consider a multilevel security model, M', where messages from Sh to Si are

allowed only if the security level of Si dominates that of Sh. Here, some communication between

5h and Si may be authorized in M'.

The set of covert channels that appears when the operating system implements model M' may

be a subset of those that appear when the same operating system implements model M. The covert

channels allowing information to flow from Sh to Si in interpretations of model M could become

authorized communication channels in an interpretation of model M'.

The dependency of covert channels on the (nondiscretionary) security policy models does not

imply one can eliminate covert channels merely by changing the policy model. Certain covert

channels will exist regardless of the type of nondiscretionary access control policy used. However,

this dependency becomes important in the identification of covert channels in specifications or

code by automated tools. This is the case because exclusive reliance on syntactic analysis that

ignores the semantics of the security model implementation cannot avoid false illegal flows. We

discuss and illustrate this in sections 3.2.2 and 3.3.

(3) Relevance to Both Secrecy and Integrity Models

In general, the notion of covert channels is relevant to any secrecy or integrity model

establishing boundaries meant to prevent information flow. Thus, analysis of covert channels is

equally important to the implementation of both nondiscretionary secrecy (e.g., [Bell and La

Padula76, Denning76, Denning77, Denning83, NCSC TCSEC]) and integrity models (e.g.,

[Biba77, Clark and Wilson87]). In systems implementing nondiscretionary secrecy models, such

as those implementing the mandatory security policies of the TCSEC at levels B2-A1, CCA assures

the discovery of (hopefully all) illicit ways to output (leak) information originating from a specific

secrecy level (e.g., "confidential/personnel files/") to a lower, or incomparable, secrecy level (e.g.,

"unclassified/telephone directory/"). Similarly, in systems implementing nondiscretionary

integrity models, such analysis also assures the discovery of (hopefully all) illicit ways to input

information originating from a specific integrity level (e.g., "valued/personnel registry/") to a

higher, or incomparable, integrity level (e.g., "essential/accounts payable/"). Without such

assurances, one cannot implement appropriate countermeasures and, therefore, nondiscretionary

security claims become questionable at best. Figures 2-1(a) and 2-1(b) illustrate the notion of

illegal flows in specific nondiscretionary secrecy and nondiscretionary integrity models.

Figure 2-1. Legal and Illegal Flows

Example 0 - Relevance of Covert Channels to an Integrity Model

Figure 2-2 illustrates the relevance of covert channels to nondiscretionary integrity models.

Although this figure assumes a specific nondiscretionary integrity model (i.e., Biba's [Biba77]),

covert channels are equally relevant to all nondiscretionary integrity models. In Figure 2-2, a user

logged in at the integrity level IL1 invokes, through a command processor (i.e., the shell), an

accounts payable application that prints payees, names on signed-check papers on a printer. The

user is trusted to operate at integrity level IL1 and, by virtue of this trust, his input to the accounts

payable application is also classified at integrity level IL1. For similar reasons, both the accounts

payable application and the printer are activated at the current integrity level IL1. However, the

accounts payable application (and, possibly, the shell) consists of an untrusted set of programs.

Figure 2-2. Relevance of Covert Channels to an Integrity Model

The presence of untrusted software in the above example should not be surprising. Most

application programs running on trusted computing bases (TCBs) supporting nondiscretionary

secrecy consist of untrusted code. Recall that the ability to run untrusted applications on top of

TCBs without undue loss of security is one of the major tenets of trusted computer systems.

Insisting that all applications that might contain a Trojan Horse, which could use covert channels

affecting integrity, be included within an integrity TCB is analogous to insisting that all

applications that might contain a Trojan Horse, which could use covert channels affecting secrecy,

be included within a secrecy TCB, and would be equally impractical.

If the untrusted accounts payable application contains a Trojan Horse, the Trojan Horse

program could send a (legal) message to a user process running at a lower integrity level IL2,

thereby initiating the use of a covert channel. In this covert channel, the Trojan Horse is the

receiver of (illegal) lower integrity-level input and the user process is the sender of this input.

The negative effect of exploiting this covert channel is that an untrusted user logged in at a

lower integrity level could control the accounts payable application through illegal input, thereby

producing checks for questionable reasons. One can find similar examples where covert channels

help violate any nondiscretionary integrity boundary, not just those provided by lattice-based

integrity models (e.g., [Biba77]). Similar examples exist because, just as in the case of TCBs

protecting sensitive information classified for secrecy reasons, not all applications running on

trusted bases protecting sensitive information for integrity reasons can be verified and proved to

be free of miscreant code.

(4) Dependency on TCB Specifications

To illustrate the dependency of covert channels on a system's TCB specifications (Descriptive

or Formal Top-Level), we show that changes to the TCB specifications may eliminate existent, or

introduce new, covert channels. The specifications of a system's TCB include the specifications of

primitives which operate on system subjects, objects, access privileges, and security levels, and of

access authorization, object/subject creation/destruction rules, for example. Different

interpretations of a security model are illustrated in [Honeywell85a, Honeywell85b,

Luckenbaugh86]. Changes to a TCB's specifications may not necessarily require a change of

security model or a change of the security model interpretation.

Example 1 - Object Allocation and Deallocation

As an example of the effect of TCB specification changes on covert channel existence (and

vice versa), consider the case of an allocator of user-visible objects, such as memory segments. The

specifications of the allocator must contain explicit "allocate/deallocate" (TCB) operations that can

be invoked dynamically and that subjects can share. A covert channel between the subjects using

these user-visible objects exists here [Schaefer77]. However, if the dynamic allocator and,

consequently, its specifications are changed to disallow the dynamic allocation/deallocation of

objects in a shared memory area, the covert channel disappears. Static object allocation in a shared

memory area, or dynamic object allocation in a memory area partitioned on a security level basis,

need not change the interpretation of the system's subjects and objects; it only needs to change the

specification of the rules for the creation and destruction of a type of object. Although eliminating

dynamic sharing of resources and either preallocating objects or partitioning resources on a per-

security-level basis represent effective ways to remove some covert channels, they are neither

necessary nor possible in all cases because they may cause performance losses.

Though this example illustrates the dependency of covert channels on TCB specifications, it

is not a general solution for eliminating covert channels. In fact, we can find other examples to

show that changing a TCB's specifications may actually increase the number of covert channels.

Example 2 - Upgraded Directories

As a second example of the strong dependency between the covert channel definition and TCB

specifications, consider the creation and destruction of upgraded directories in a system supporting

mandatory security and using specifications of interfaces similar to those of UNlX. The notion of

an upgraded directory [Whitmore73, Schroeder77, Gligor87], its creation and removal, is

illustrated in Figures 2-3(a)-(d).

In such a system, whenever a user attempts to remove an upgraded directory from level Lh >

Li where he is authorized to read and write it (as in Figure 2-3(c)), the remove operation fails

because it violates the mandatory authorization check (the level of the removing process, Lh, must

equal that of the parent directory, Li). In contrast, the same remove operation invoked by a process

at level Li < Lh succeeds (Figure 2-3(d)).

However, a covert channel appears because of the specification semantics of the remove operation

in UNIX "rmdir." This specification says a nonempty directory cannot be removed. Therefore, if

the above user logs in at level Li and tries to remove the upgraded directory from the higher level

Lh, the user process can discover whether any files or directories at level Lh > Li are linked to the

upgraded directory. Thus, another process at level Lh can transmit a bit of information to the user

process at level Li < Lh by creating and removing (e.g., unlinking) files in the upgraded directory.

Figure 2-4 illustrates this concept.

Figure 2-3. Creation and Destruction of an Upgraded Directory at Level Lh > Li

Figure 2-4. Covert Channel Caused by (UNIX) TCB Interface Conventions (where Lh > Li)

This covert channel would not appear if nonempty directories, and the directory subtree started

from them, could be removed (e.g., as in Multics [Whitmore73, Bell and La Padula76]). However,

if the specification of directory removal is changed, disallowing removal of nonempty directories

(as in UNIX), the covert channel appears. One cannot eliminate the channel without modifying the

UNIX user-visible interface. This is an undesirable alternative given that user programs may

depend on the interface convention that nonempty UNIX directories cannot be removed. One

cannot invent a new TCB specification under which either directories are not user-visible objects

or in which the notion of upgraded directories disappears for similar reasons; that is, the UNIX

semantics must be modified.

2.2 CLASSIFICATION

2.2.1 Storage and Timing Channels

In practice, when covert channel scenarios of use are constructed, a distinction between covert

storage and timing channels [Lipner75, Schaefer77, NCSC TCSEC, Hu91, Wray91] is made even

though theoretically no fundamental distinction exists between them. A potential covert channel is

a storage channel if its scenario of use "involves the direct or indirect writing of a storage location

by one process [i.e., a subject of I(M)] and the direct or indirect reading of the storage location by

another process." [NCSC TCSEC] A potential covert channel is a timing channel if its scenario of

use involves a process that "signals information to another by modulating its own use of system

resources (e.g., CPU time) in such a way that this manipulation affects the real response time

observed by the second process." [NCSC TCSEC] In this guide, we retain the distinction between

storage and timing channels exclusively for consistency with the TCSEC.

In any scenario of covert channel exploitation, one must define the synchronization relationship

between the sender and the receiver of information. Thus, covert channels can also be

characterized by the synchronization relationship between the sender and the receiver. In Figure 2-

5, the sender and the receiver are asynchronous processes that need to synchronize with each other

to send and decode the data. The purpose of synchronization is for one process to notify the other

process it has completed reading or writing a data variable. Therefore, a covert channel may

include not only a covert data variable but also two synchronization variables, one for sender-

receiver synchronization and the other for the receiver-sender synchronization. Any form of

synchronous communication requires both the sender-receiver and receiver-sender

synchronization either implicitly or explicitly [Haberman72]. Note that synchronization operations

transfer information in both directions, namely from sender to receiver and vice versa and,

therefore, these operations may be indistinguishable from data transfers. Thus, the synchronization

and data variables of Figure 2-5 may be indistinguishable.

Some security models, and some of their interpretations, allow receiver-sender

communication for subsets of all senders and receivers supported in the system. For example, all

mandatory security models implemented in commercial systems to date allow information to flow

from a low security level to a higher one. However, sender-receiver synchronization may still need

a synchronization variable to inform the receiver of a bit transfer. A channel that does not include

sender-receiver synchronization variables in a system allowing the receiver-sender transfer of

messages is called a quasi-synchronous channel. The idea of quasi-synchronous channels was

introduced by Schaefer in 1974 [Reed and Kanodia78].

Figure 2-5. Representation of a Covert Channel between Sender S and Receiver R (where Lh> Li

or L* * Li)

In all patterns of sender-receiver synchronization, synchronization data may be included in the

data variable itself at the expense of some bandwidth degradation. Packet-formatting bits in ring

and Ethernet local area networks are examples of synchronization data sent along with the

information being transmitted. Thus, explicit sender-receiver synchronization through a separate

variable may be unnecessary. Systems implementing mandatory security models allow messages

to be sent from the receiver to the sender whenever the security level of the sender dominates that

of the receiver. In these cases, explicit receiver-sender synchronization through a separate variable

may also be unnecessary.

The representation of a covert channel illustrated in Figure 2-5 can also be used to distinguish

between scenarios of storage and timing channels. For example, a channel is a storage channel

when the synchronization or data transfers between senders and receivers use storage variables,

whereas a channel is a timing channel when the synchronization or data transfers between senders

and receivers include the use of a common time reference (e.g., a clock). Both storage and timing

channels use at least one storage variable for the transmission/sending of the information being

transferred. (Note that storage variables used for timing channels may be ephemeral in the sense

that the information transferred through them may be lost after it is sensed by a receiver. We

discuss this in more detail in Appendix A.) Also, a timing channel may be converted into a storage

channel by introducing explicit storage variables for synchronization; and vice versa, a storage

channel whose synchronization variables are replaced by observations of a time reference becomes

a timing channel.

Based on the above definitions of storage and timing channels, the channels of Examples 1

and 2 are storage channels. Examples 3 and 4 below illustrate scenarios of timing channels.

Appendix A presents additional examples of both storage and timing channels.

Example 3 - Two Timing Channels Caused by CPU Scheduling

Quantum-based central processing unit (CPU) scheduling provides two typical examples of timing

channels (Figure 2-6). In the first example, the sender of information varies the nonzero CPU time,

which it uses during each quantum allocated to it, to send different symbols. For 0 and 1

transmissions, the sender picks two nonzero values for the CPU time used during a quantum, one

representing a 0 and the other a 1. This channel is called the "quantum-time channel" in

[Huskamp78]. The receiver of the transmitted information decodes the transmitted information by

measuring its waiting time for the CPU. If only the receiver and the sender are in the system, the

receiver can decode each transmitted bit correctly with probability one for some quantum sizes. A

condition of this channel is that the sender be able to block itself before the end of some quantum

and reactivate itself before the beginning of the next quantum. The sender can meet this condition

in a variety of ways depending upon the size of the quantum (e.g., a typical range for quanta is 50-

1000 milliseconds). For example, the sender may use an "alarm clock" to put itself to sleep for a

fraction of the quantum time, or it may generate a page fault (whose handling may take only a

fraction of a quantum time also). A quantum of 100-200 milliseconds is sufficiently large for either

case.

Figure 2-6. Two CPU Timing Channels

In the second example of Figure 2-6, the sender transmits information to the receiver by

encoding symbols, say 0s and 1s, in the time between two successive CPU quanta. This channel is

called the "interquantum-time channel" [Huskamp78], and is shown in Figure 2-6(b) for the case

where only the sender and the receiver appear in the system. To send information, the sender and

the receiver agree on set times for sending the information. The transmission strategy is for the

sender to execute at time "ti" if the i-th bit is 1, and to block itself if the i-th bit is 0. The receiver

can tell whether the sender executes at time ti because the receiver cannot execute at the same time.

Example 4 - Other Timing Channels Caused by Shared Hardware Resources

The CPU scheduling channels of Example 3 appear because processes at different secrecy or

integrity levels share a hardware resource, namely the CPU. Other sharable hardware resources

provide similar timing channels. For example, in any multiprocessor design, hardware resources

are shared. Multiple processors share the same bus in shared-bus architectures, share the same

memory ports in bus-per-processor architectures, and share multiple busses and memory ports in

crossbarswitch architectures, as shown in Figure 2-7. In all multiprocessor architectures, each

instruction referencing the memory must lock the shared resource along the CPU-memory

interconnection path for at least one memory cycle. (The number of cycles during which the shared

resource must be locked depends on the instruction semantics.) Hardware controllers of the shared

resource mediate lock conflicts. When the shared resource is no longer needed during the execution

of the instructon, the resource is unlocked.

Whenever two processes at two different levels execute concurrently on two separate

processors, a covert channel appears that is similar to the CPU interquantum channel presented in

Example 3. That is, the sender and the receiver processes establish by prior agreement that the

sender process executes at time"ti"if the i-th bit is a 1 and does not execute (or at least does not

execute memoryreferencing instructions) at time "ti" if the i-th bit is a 0. The receiver can execute

a standard set of memory-referencing instructions and time their execution. Thus, the receiver can

discover whether the sender executes at time "ti" by checking whether the duration of the standard

set of timed instructions was the expected 1 or longer. As with the CPU channels of Example 3,

these channels appear in any multiprocessor system regardless of the nondiscretionary model

interpretation. Note that adding per-processor caches, which helps decrease interprocessor

contention to shared hardware resources, cannot eliminate these channels. The sender and receiver

processes can fill up their caches and continue to exploit interprocessor contention to transmit

information.

Appendix A provides other examples of timing channels, which also appear due to the sharing

of other hardware resources.

Figure 2-7. Examples of Shared Hardware Resources in Multiprocessor Architectures

2.2.2 Noisy and Noiseless Channels

As with any communication channel, covert channels can be noisy or noiseless. A channel is

said to be noiseless if the symbols transmitted by the sender are the same as those received by the

receiver with probability 1. With covert channels, each symbol is usually represented by one bit

and, therefore, a covert channel is noiseless if any bit transmitted by a sender is decoded correctly

by the receiver with probability 1. That is, regardless of the behavior of other user processes in the

system, the receiver is guaranteed to receive each bit transmitted by the sender.

The covert channel of Example 2 is a noiseless covert channel. The sender and receiver can

create and remove private upgraded directories, and no other user can affect in any way whether

the receiver receives the error/no_error signal. Thus, with probability 1, the receiver can decode

the bit value sent by the sender. In contrast, the covert channels of Examples 3 and 4 are noisy

channels because, whenever extraneous processes-not just the sender and receiver-use the shared

resource, the bits transmitted by the sender may not be received correctly with probability 1 unless

appropriate error-correcting codes are used. The error-correcting codes used depend on the

frequency of errors produced by the noise introduced by extraneous processes (shown in Figure 2-

5) and decrease the maximum channel bandwidth. Thus, although error-correcting codes help

change a noisy channel into a noiseless one, the resulting channel will have a lower bandwidth than

the similar noise-free channel.

We introduce the term "bandwidth" here to denote the rate at which information is transmitted

through a channel. Bandwidth is originally a term used in analog communication, measured in

hertz, and related to information rate by the "sampling theorem" (generally attributed to H. Nyquist

although the theorem was in fact known before Nyquist used it in communication theory

[Haykin83]). Nyquist's sampling theorem says that the information rate in bits (samples) per

second is at most twice the bandwidth in hertz of an analog signal created from a square wave. In

a covert channel context, bandwidth is given in bits/second rather than hertz, and is commonly

used, in an abuse of terminology, as a synonym for information rate. This use of the term

"bandwidth" is also related to the notion of "capacity." The capacity of a channel is its maximum

possible error-free information rate in bits per second. By using error-correcting codes, one can

substantially reduce the error rates of noisy channels. Error-correcting codes decrease the effective

(i.e., error-free) information rate relative to the noisy bit rate because they create redundancy in the

transmitted bit stream. Note that one may use error-detecting, rather than error-correcting, codes

in scenarios where the receiver can signal the sender for retransmissions. All of these notions are

standard in information theory [Gallager68].

2.2.3 Aggregated versus Nonaggregated Channels

Synchronization variables or information used by a sender and a receiver may be used for

operations on multiple data variables. Multiple data variables, which could be independently used

for covert channels, may be used as a group to amortize the cost of synchronization (and, possibly,

decoding) information. We say the resulting channels are aggregated. Depending on how the

sender and receiver set, read, and reset the data variables, channels can be aggregated serially, in

parallel, or in combinations of serial and parallel aggregation to yield optimal (maximum)

bandwidth.

If all data variables are set, reset, and read serially, then the channel is serially aggregated. For

example, if process Ph of Example 2 (Figure 2-4) uses multiple upgraded directories designated

"empty/nonempty" before transferring control to process Pi, the signaling channel will be serially

aggregated. Similarly, if all data variables are set, reset, and read in parallel by multiple senders

and receivers, then the channel is aggregated in parallel. Note that combinations of serial/parallel

aggregaton are also possible. For example, the data variables may be set in parallel but read serially

and vice versa. However, such combinations do not maximize bandwidth and are, therefore, of

limited interest.

Parallel aggregation of covert channel variables requires, for bandwidth maximization

reasons, that the sender and receiver pairs be scheduled on different processors at the same time as

a group, as illustrated in Figure 2-8 and in [Gligor86]. Otherwise, the bandwidth of the parallel

aggregation degrades to that of a serially aggregated channel. The application programmer can

strictly control group scheduling of senders and receivers in multiprocessor operating systems such

as Medusa or StarOS [Osterhout80, Jones79], which use "coscheduling" [Osterhout82]. Also

group scheduling may be possible in multiple workstation systems such as those used in LOCUS

[Walker83] or Apollo [Leach83] whenever multiple workstatons are available to a single

application. In such systems, the analysis of individual covert channels is insufficient to determine

the maximum covert channel bandwidth.

Figure 2-8. Example of n Channels Aggregated in Parallel

Parallel aggregation of covert channels also requires, for bandwidth maximizaton reasons, that

the synchronization messages between all senders, and those between all receivers, be transmitted

at a much higher speed than those between senders and receivers. In practice, messages sent among

senders, and those sent among receivers, have negligible transmission delays compared to those

used by covert channels between senders and receivers. (Also, note that all messages among

senders and those among receivers are authorized messages.)

2.3 COVERT CHANNELS AND FLAWED TCB SPECIFICATIONS

An unresolved issue of covert channel definition is whether one can make a distinction

between a covert channel and a flaw introduced by the implementation of the security models. In

other words, one would like to differentiate between implementation flaws and covert channels, if

possible, for practical reasons. For example, both implementors and evaluators of systems

supporting mandatory access controls in class B1 could then differentiate between flaws and covert

channels. They could determine whether instances of leakage of classified information must be

eliminated or otherwise handled or ignored until the B2 level and above.

The covert communication Definition 5 does not differentiate between covert channels and

interpretation or TCB specification flaws. This definition implies that, in a fundamental sense,

covert channels are in fact flaws of nondiscretionary access control policy implementations, which

are sometimes unavoidable in practice regardless of the implementors' design (e.g., Example 3).

However, the focus of that definition on the notion of model implementation may help provide a

criterion for distinguishing between different types of covert channels or implementation flaws.

To define a distinguishing criterion, let us review Examples 1-4. Examples 1 and 2 show that

a change of the TCB specification can, in principle, eliminate the existent covert channels in the

specific systems under consideration. In contrast, Examples 3 and 4 show that as long as any

system allows the sharing of the CPUs, busses, memory, input/output (I/O) and other hardware

resources, covert channels will appear for any TCB specification. Furthermore, Example 2

illustrates that, in many systems, a change of TCB specification that would eliminate a covert

channel may sometimes be impractical. That is, evidence may exist showing that contemplated

changes of the TCB specification would cause a significant loss of compatibility with existing

interfaces of a given system. Similar examples can be found to illustrate that changes of TCB

specifications may help eliminate other covert channels (or flaws) at the expense of loss of

functionality or performance in a given system (e.g., Example 1).

The following criterion may help distinguish between different types of covert channels (or

flaws) in practice, thereby providing the necessary input for covert channel, or flaw, handling at

levels B1 versus levels B2-A1:

· Fundamental Channels - A flaw of a TCB specification that causes covert

communication represents a fundamental channel if and only if that flaw appears under

any interpretation of the nondiscretionary security model in any operating system.

· Specific TCB Channels - A flaw of a TCB specification that causes covert

communication represents a specific TCB channel if and only if that flaw appears only

under a specific interpretation of the nondiscretionary security model in a given

operating system.

· Unjustifiable Channels - A flaw of a TCB specification that causes covert

communication represents an unjustifiable channel if and only if that flaw appears only

under a specific but unjustifiable interpretation of a nondiscretionary security model in

a given operating system. (The primary difference between specific TCB and

unjustifiable channels is in whether any evidence exists to justify the existence of the

respective channels.)

Using this criterion, the covert channels of Examples 3 and 4 are fundamental channels,

whereas those of Examples 1 and 2 are specific TCB channels.

The above criterion for distinguishing different types of covert channels (or flaws) suggests

the following differentiation policy for B1 and B2A1 systems. For B1 systems, there should be no

handling obligation of fundamental covert channels; specific TCB channels should be handled

under the policies in force for classes B2Al (as recommended in Chapter 5 of this guide);

unjustifiable channels should be eliminated by a change of TCB specification or model

implementation for any B-rated systems.

3.0 COVERT CHANNEL IDENTIFICATION

We discuss in this chapter the representation of a covert channel within a system, the sources

of information for covert channel identification, and various identification methods that have been

used to date and their practical advantages and disadvantages. We also discuss the TCSEC

requirements for covert channel identification and make additional recommendations.

A covert channel can be represented by a TCB internal variable and two sets of TCB

primitives, one for altering (PAh) and the other for viewing (PVi) the values of the variable in a

way that circumvents the system's mandatory policy. Multiple primitives may be necessary for

viewing or altering a variable because, after viewing/altering a variable, the sender and/or the

receiver may have to set up the environment for sending/reading the next bit. Therefore, the

primary goal of covert channel identification is to discover all TCB internal variables and TCB

primitives that can be used to alter or view these variables (i.e., all triples <variable; PAh, PVi>).

A secondary, related goal is to determine the TCB locations within the primitives of a channel

where time delays, noise (e.g., randomized table indices and object identifiers, spurious load), and

audit code may be placed for decreasing the channel bandwidth and monitoring its use. In addition

to TCB primitives and variables implemented by kernel and trusted processes, covert channels may

use hardware-processor instructions and user-visible registers. Thus, complete covert channel

analysis should take into account a system's underlying hardware architecture, not just kernels and

trusted processes.

3.1 SOURCES OF INFORMATION FOR COVERT CHANNEL IDENTIFICATION

The primary sources of information for covert channel identification are:

· System reference manuals containing descriptions of TCB primitives, CPU and I/O

processor instructions, their effects on system objects and registers, TCB parameters or

instruction fields, and so on;

· The detailed top-level specification (DTLS) for B2-A1 systems, and the Formal top-

level specification (FTLS) for A1 systems; and

· TCB source code and processor-instruction (micro) code.

The advantage of using system reference manuals for both TCB-primitive and processor-

instruction descriptions is the widespread availability of this information. Every implemented

system includes this information for normal everyday use and, thus, no added effort is needed to

generate it. However, there are disadvantages to relying on these manuals for covert channel

identification. First, whenever system reference manuals are used, one can view the TCB and the

processors only as essentially "black boxes." System implementation details are conspicuous by

their absence. Thus, using system reference manuals, one may not attain the goal of discovering

all, or nearly all, channels. Whenever these manuals are the only sources of information, the

channel identification may only rely on guesses and possibly on analogy with specifications of

other systems known to contain covert channels. Second, and equally important, is the drawback

that analysis based on system reference information takes place too late to be of much help in

covert channel handling. Once a system is implemented and the manuals written, the option of

eliminating a discovered covert channel by removing a TCB interface convention may no longer

be available. Third, few identification methods exist that exhibit any degree of precision and that

can rely exclusively on information from system reference manuals. The inadequacy of using only

system reference manuals for CCA is illustrated in Example 6 of Section 3.2.3.

Most identification methods developed to date have used formal top-level TCB specifications

as the primary source of covert channel identification. The use of top-level specifications has

significant advantages. First, these specifications usually contain more detailed, pertinent

information than system reference manuals. Second, use of top-level specifications helps detect

design flaws that may lead to covert channels in the final implementation. Early detection of design

flaws is a useful prerequisite for correct design because one can minimize efforts expended to

correct design flaws. Third, tools aiding the identification process exist for the FTLS and thus one

gains additional assurance that all channels appearing within the top-level specifications are found

(see Appendix B).

However, total reliance on analysis of top-level specifications for the identificaton of covert

channels has two significant disadvantages. First, it cannot lead to the identification of all covert

channels that may appear in implementation code. Formal methods for demonstrating the

correspondence between information flows of top-level specifications and those of implementation

code do not exist to date. Without such methods, guarantees that all covert storage channels in

implementation code have been found are questionable at best. The only significant work on

specification-to-code correspondence on an implemented system (i.e., the Honeywell SCOMP

[Benzel84]) reported in the literature to date has been thorough but informal. This work shows that,

in practice, a significant amount of implementation code has no correspondent formal

specifications. Such code includes performance monitoring, audit, debugging, and other code,

which is considered security-policy irrelevant but which, nevertheless, may contain variables

providing potential storage channels.

Second, formal/descriptive top-level specifications of a TCB may not include sufficient

specification detail of data structures and code to detect indirect information flows within TCB

code that are caused by the semantics of the implementation language (e.g., control statements,

such as alternation statements, loops, and so on; pointer assignments, variable aliasing in structures

[Schaefer89, Tsai90]). Insufficient detail of specifications used for information flow and storage

channel analysis may also cause inadequate implementation of nondiscretionary access controls

and channel-handling mechanisms. This is the case because, using the results of top- level

specification analysis, one cannot determine with certainty the placement of code for access

checks, channel use audits, and time delays to decrease channel bandwidth within TCB code.

In contrast with the significant efforts for the analysis of design specifications, little practical

work has been done in applying CCA to implementation code or to hardware. Identifying covert

storage channels in source code has the advantages that (1) potentially all covert storage channels

can be found (except those caused by hardware), (2) locations within TCB primitives for placement

of audit code, de-lays, and noise can be found, and (3) adequacy of access-check placement within

TCB primitives could be assessed [Tsai90]. However, analysis of TCB source code is very labor-

intensive, and few tools exist to date to help alleviate the dearth of highly skilled personnel to

perform such labor-intensive activity.

3.2 IDENTIFICATION METHODS

All of the widely used methods for covert channel identification are based on the identification

of illegal information flows in top-level design specifications and source code, as first defined by

[Denning76, 77, 83] and [Millen76]. Subsequent work by [Andrews and Reitman80] on

information-flow analysis of programming language statements extended Denning's work to

concurrent-program specifications.

3.2.1 Syntactic Information-Flow Analysis

In all flow-analysis methods, one attaches information-flow semantics to each statement of a

specification (or implementation) language. For example, a statement such as "a: = b" causes

information to flow from b to a (denoted by b Æ a) whenever b is not a constant. Similarly, a

statement such as "if v = k then w: = b else w: = c" causes information to flow from v to w. (Other

examples of flows in programming-language statements are found in [Denning83, Andrews and

Reitman80, Gasser88]). Furthermore, one defines a flow policy, such as "if information flows from

variable x to variable y, the security level of y must dominate that of x." When applied to

specification statements or code, the flow policy helps generate flow formulas. For exampIe, the

flow formula of "a: = b" is security level(a) > security_level(b). Flow formulas are generated for

complete program and TCB-primitive specifications or code based on conjunctions of all flow

formulas of individual language statements on a flow path. (Formula simplifications are also

possible and useful but not required.) These flow formulas must be proven correct, usually with

the help of a theorem prover. If a pro-gram flow formula cannot be proven, the particular flow can

lead to a covert channel flow and further analysis is necessary. That is, one must perform semantic

analysis to determine (1) whether the unproven flow is real or is a false illegal flow, and (2)

whether the unproven flow has a scenario of use (i.e., leads to a real-not just a potential-

channel). Example 5 of this section and Examples 7 and 8 of Section 3.3 illustrate the notion of

false illegal flow and the distinction between real and potential channels.

Various tools have been built to apply syntactic flow analysis to formal specifications. For

example, the SRI Hierarchical Development Methodology (HDM) and Enhanced HDM (EHDM)

tools [Feiertag80, Rushby84] apply syntactic analysis to the SPECIAL language. Similarly, the Ina

Flo tool of the Formal Development Methodology (FDM) [Eckmann87] and the Gypsy tools

[McHugh and Good85, McHugh and Ackers87] have been used for syntactic information-flow

analyses. Appendix B reviews these tools. Experience with information-flow analysis in practice

is also reported in references [Millen78, MiIlen81].

Syntactic information-flow analysis has the following advantages when used for covert

channel identification:

· It can be automated in a fairly straightforward way;

· It can be applied both to formal top-level specifications and source code;

· It can be applied incrementally to individual functions and TCB primitives; and

· It does not miss any flow that leads to covert channels in the particular specification (or

code).

All syntactic information-flow analysis methods share the following three drawbacks:

· Vulnerability to discovery of false illegal flows (and corresponding additional effort to

eliminate such flows by manual semantic analysis);

· Inadequacy of use with informal specifications; and

· Inadequacy in providing help with identifying TCB locations for placing covert

channel handling code.

All syntactic flow-analysis methods assume each variable or object is either explicitly or

implicitly labeled with a specific security level or access class. However, as pointed out in

[Kemmerer83], covert channels use variables not normally viewed as data objects. Consequently,

these variables cannot necessarily be labeled with a specific security level and, therefore, cannot

be part of the interpretation of a given nondiscretionary security model in an operating system.

Instead, these variables are internal to kernels or trusted processes and their security levels may

vary dynamically depending upon flows between labeled objects. Therefore, the labeling of these

variables with specific security levels to discover all illegal flows also renders these code-analysis

methods vulnerable to discovery of false flow violations. These false flow violations are called

"formal flow violations" in references [MilIen78, Schaefer89, Tsai90].

Example 5 - A False Illegal Flow

An example of a false flow violation in the fragment of code shown in Figure 3-1(a) is

illustrated in Figures 3-1(b, c). Here, both the alterer and the viewer of the "msgque Æ mode"

variable is the TCB primitive "msgget" of Secure Xenix. The flow formula sl(u.u_rval1) sl(qp)

sl(msgque Æ mode) sl(flag) sl(uapÆmsgflg), where sl stands for the security level, cannot

be proven because the security levels of the variables vary dynamically, depending on the security

levels of the processes invoking the "msgget" primitive. Thus, syntactic flow analysis would

identify this flow as il legal. However, an examination of the program conditions under which this

flow can actually occur (shown in Figure 3-1 (b)) quickly reveals this flow is legal. This flow can

occur because the conditions enabling the flow at run time include security checks of the

nondiscretionary model interpretations for both viewing and altering InterProcess Communication

(IPC) objects. These checks prevent all illegal flows through the "msgque Æ mode" variable.

Practical examples of false illegal flows appear in all covert channel analyses relying

exclusively on syntactic flow analysis. For example, sixty-eight formulas that could not be proven

have been found in the SCOMP analysis using the Feiertag Flow tool [Benzel84, Millen89b]. Only

fourteen of these flows caused covert channels; the balance were all false illegal flows. Similar

examples can be given based on experience with other flow tools. For instance, even in a small

(twenty-line) program written in Ina Jo, the lna Flow tool discovered one hundred-seventeen illegal

flows of which all but one were false [Cipher90].

Information-flow analysis does not lend itself to use on informal (e.g., English language)

specifications. This means that, if one uses information-flow analysis for B2-B3 class systems, one

should apply it to source code. Furthermore, discovery of illegal flows in formal top-level

specifications (for class A1 systems) offers little help for identifying TCB locations where covert

channel handling code may be necessary. The identification of such locations requires semantic

analysis of specifications and code.

Figure 3-1. An Example of a False Illegal Flow Caused by Syntactic Flow Analysis

3.2.2 Addition of Semantic Components to Information-Flow Analysis

Reference [Tsai90] presents a method for identification of potential storage channels based on

(1) the analysis of programming language semantics, code, and data structures used within the

kernel, to discover variable alterability/visibility; (2) resolution of aliasing of kernel variables to

determine their indirect alterability; and (3) information-flow analysis to determine indirect

visibility of kernel variables (e.g., the "msgque Æ mode" variable in Figure 3-1). These steps

precede the application of the nondiscretionary (secrecy or integrity semantic) rules specified in

the interpretation of the security model, and implemented in code, to the shared variables and

kernel primitives. This last step helps distinguish the real storage channels from the legal or

inconsequential ones. The delay in the application of these rules until the security levels of shared

variables can be determined with certainty (i.e., from the levels of the objects included in the flows

between variables) helps avoid additional (manual) analysis of false illegal flows. Furthermore,

discovery of all locations in kernel code where shared variables are altered/viewed allows the

correct pla