math at work: i stars

4.2 BANDWIDTH ESTIMATION METHODS

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

Millen presents in [1989a] a method based on Shannon's information theory [Shannon and Weaver64]. In this method, one assumes the covert channels are noiseless, no processes other than the sender and receiver are present in the system during channel operation, and the sender-receiver synchronization takes a negligible amount of time. These assumptions are justified if the goal is the computation of the maximum attainable bandwidth. With these assumptions, one can model most covert channels that arise in practice as finite-state machines (graphs). Furthermore, these graphs are deterministic in that for any state transition corresponding to a given channel symbol (e.g., 0 or 1), only one next state appears in the graph. Figure 4-1 illustrates a state graph for a two- state channel. Most covert channels of interest in practice can be represented with two-state graphs. This is because, for most channels, the current state of the channel depends on the last signal sent and, thus, only two states are necessary to capture the scenario of information transfer.

Figure Missing

Figure 4-1. Two-State Graph for a Covert Channel

Example 10 - Scenario for a Two-State Covert Channel

A scenario for the transfer of 0s and 1s using a two-state graph can be defined by associating each transition of the graph with the transfer of a 0 or a 1. Each transition covers a sender's action followed by a receiver's action.

For example, to send 0 in state 0:

• sender transfers control to receiver;
• receiver reads the channel variable;
• receiver records 0;
• receiver resets the environment (if necessary);
• receiver transfers control to sender.

To send 0 in state 1:

• sender sets the channel variable to 0;
• sender transfers control to receiver;
• receiver reads the channel variable;
• receiver records 0;
• receiver resets the channel environment (if necessary);
• receiver transfers control to sender

To send 1 in state 0:

• sender sets the channel variable to 1;
• sender transfers control to receiver;
• receiver reads the channel variable;
• receiver records 1;
• receiver transfers control to sender

To send 1 in state 1:

• sender transfers control to receiver;
• receiver reads the channel variable;
• receiver records 1;
• receiver transfers control to sender.

One can determine the time required to send a 0 or 1 by listing the corresponding sequence of TCB primitive calls and adding up their times. Recall that the TCB primitive calls, and their total duration, depend on the state of the channel. Also, recall that the reading (not just the setting) of a 0 or a 1 will have different durations even if they are represented by the same TCB primitive call. For example, if the reading of a 0 in one state is represented by the "open" primitive call with a successful return and in the other state by "open" with a failure return, the reading of the 0 in the two states will have different durations because the latter call always has a shorter duration. The sequences of TCB primitive calls necessary to transfer 0s and 1s using a two-state graph may be different, and thus they may take four different amounts of time, say a, b, c, and d time units, respectively (as shown in Figure 4-1).

To determine the bandwidth of a channel represented with a two-state graph, N(t), one must find the number of possible transmissions of duration t. The bandwidth (i.e., capacity) of a channel can be expressed in terms of Nh(t) as follows:

C = lim(log2Nh(t))/t.

To find N_h(t), let N₀(t) be the total possible number of transmissions of duration exactly t beginning in one of the two states, and let N₁(t) be the total possible number of transmissions of duration exactly t beginning in the other state. (In general, there will be an N_h(t) for the h-th state where h ranges over the state set.) The number of transmissions satisfies a system of difference equations that can be read off the two-state graph. Each equation is based on the fact that the set of transmissions beginning in a given state consists of a union of several disjoint sets, discriminated by the initial symbol of the transmissions. The number of transmissions with a given initial symbol is equal to the total number of (shorter) transmissions beginning in the next state after the transition for that symbol.

The following system of equations can be used for the file-lock channel:

N₀(t)=N₀(t - a)+N₁(t - c)

N₁(t)=N₀(t - b)+N₁(t - d)

In general, the h^th equation has the form:

N_h(t' = Σ i(N_i(t - T_hi),

where T_hi is the time taken by a transition from state h to state i.

Note that N₀(t) is nonzero only for those values of t that are expressible as a sum of multiples of a, b, c, and d. To determine the bandwidth of the channel, it is only necessary to find the asymptotic upper limit of N₀(t) as t approaches infinity [Shannon and Weaver64]. This may be found in the form:

N_h(t)=A_h^*x^t

Substituting this solution, we obtain the system of equations:

A_h^*x^t = Σ (A_i^*x^t-T_hi)

and C = lim(log₂(A_h(x^t))/t = log₂x, when t -> infinity.

Note that there may be multiple solutions for x in the above equations. The largest solution provides the bandwidth (capacity).

We can express this system of equations in matrix form as (P-I)A = 0, where P is a matrix of negative powers of x. Since (P-I) is singular, its determinant Det(P-I) = 0. Figure 4-2 shows the system of equations, their determinant, and the solution.

Example 11 - Application to Two Secure Xenix Channels

Two of the Secure Xenix channels whose bandwidths were computed in reference [Tsai and Gligor88] for a PC/AT configuration are the inode table channel and the upgraded directory channel. In this example we illustrate Millen's method described above using measurements of Secure Xenix TCB primitives on an IBM PS/2 model 80 configuration. T_cs represents the context switch time, which is 3 milliseconds. The values of T_r (T_s) represent the duration of reading (setting) the covert channel variable, and the value of T_env represents the duration of setting up the transfer environment (e.g., a state transition).

Figure Missing

Figure 4-2. Simultaneous Equations, Determinant, Capacity (Bandwidth)

The lnode Table Channel

In this example the state 0 of the inode table channel is represented by the inode table full state, and the state 1 by the node table nonfull state. Figure 4-3 shows the state transitions defined

Figure Missing

Figure 4-3. State Graphs for the lnode Table Channel

State 0:

When the inode table is full, two T_cs and one viewing primitive "open(f)" with a failure return are needed to transfer a 1 from a sending process to a receiving process. Thus, the following times are needed to transfer a 1 from state 0:

T_r(full->full) = open(f), T_s(full->full) = 0, T_env(full->full) = 0.

When switching from the full state to the nonfull state, an alteration primitive "close(s)," a viewing primitive "open(s)," an environment set-up primitive "close(s)," and two T_cs are needed to send a 0. Thus, the following times are needed to transfer a 0 from state 0:

T_r(full->nonfull) = open(s), T_s(full->nonfull) = close(s), T_env(full->nonfull) = close(s).

State 1:

When the transition is from the nonfull state to the nonfull state, a viewing primitive "open(s)," an environment set-up primitive "close(s)," and two T_cs are needed to transfer a 0. Thus, the following times are needed to transfer a 0 from state 1:

T_r(nonfull->nonfull) = open(s), T_s(nonfull->nonfull) = 0, T_env(nonfull->nonfull) = close(s).

When switching from the nonfull state to the full state, an alteration primitive "open(s)," a viewing primitive "open(f)," and two T_cs are needed to transfer a 1. Thus, the following times are needed to transfer a 0 from state 1:

T_r(nonfull->full) = open(f), T_s(nonfull->full) = open(s), T_env(nonfull->full) = 0.

The bandwidth (i.e., capacity) of this channel, denoted by C in Figure 4-3, is 47.63 bits/second.

The Upgraded Directory Channel

In this example the state 0 of the upgraded directory channel is represented by the directory-full state, and the state 1 by the directory-nonfull state. The state transitions defined below and their durations are shown in Figure 4-4.

Figure Missing

Figure 4-4. State Graphs for the Upgraded Directory Channel

State 0:

When an upgraded directory is nonempty, two T_cs and one viewing primitive "rmdir(f)" with a failure return are needed to transfer a 1 from a sending process to a receiving process.

T_r(nonempty->nonempty) = rmdir(f), T_s(nonempty->nonempty) = 0, T_env(nonempty->nonempty) = 0.

When switching from the nonempty state to the empty state, an alteration primitive "unlink(s)," a viewing primitive "rmdir(s)," an environment set-up primitive "mkdir(s)," and two T_cs are needed to send a 0. Thus, the following times are needed to transfer a 0 from state 0:

T_r(nonempty->empty) = rmdir(s), T_s(nonempty->empty) = unlink(s), T_env(nonempty->empty) = mkdir(s).

State 1:

When the transition is from the empty state to the empty state, a viewing primitive "rmdir(s)," an environment set-up primitive "mkdir(s)," and two T_cs are needed to transfer a 0. Thus, the following times are needed to transfer a 0 from state 1:

T_r(empty->empty) = rmdir(s), T_s(empty->empty) = 0, T_env(empty->empty) = mkdir(s).

When switching from the empty state to the nonempty state, an alteration primitive "creat(s)", a viewing primitive "rmdir(f)", and two T_cs are needed to transfer a 1. Thus, the following times are needed to transfer a 1 from state 1:

T_r(empty->nonempty) = open(f), T_s(empty->nonempty) = open(s), T_env(empty->nonempty) = 0.

The bandwidth of this channel is denoted by C in Figure 4-4 and is 0.512 bits/second.

4.2.2 Informal Method for Estimating Covert Channel Bandwidth

A simple formula for computing the maximum attainable bandwidth of a noise-less covert channel in absence of any spurious processes that would delay senders and receivers was presented in [Tsai and Gligor88]. The formula is:

B(0) = b^*(T_r + T_s + 2T_cs)^**(-1),

In this formula, b represents the encoding factor (which we assume to be 1 in most practical cases), and

Formula Missing

where n is the number of total possible transitions. T_s(i) and T_r(i) are the times necessary to set and read a 0 or a 1 after having transmitted a 0 or a 1. Thus, n = 4. T_env(i) is the time to set up the environment to read a 0 or a 1. Note that in these formulas it is assumed that all environment setup for both variable reading and setting is done by the receiving processes.

In deriving this formula it is assumed that the setting of 0's and 1's take the same amount of time, and that all transmissions contain an equal distribution of 0's and 1's.

Example 12 - Application of the Bandwldth EstImation Formula

The maximum bandwidths of the two channels of Example 11 can be recalculated by using the above formula, as follows:

The Inode Table Channel

Ts = [T_s(full->full) + T_s(full->nonfull) + T_s(nonfull->nonfull) + T_s(nonfull->full)]/4

= [0 + close(s) + 0 + open(s)]/4

=(open+close)/4 = (12 + .2)/4 = 3.05 (ms)

Tr = [T,(full->full)+ T_env(full->full) + T_r(full->nonfull) + T_env(full->nonfull) + T_r(nonfull->nonfull) + T_env(nonfull->nonfull) + T_r(nonfull->full) + T_env(nonfull->full)]/4

= [open(f) + 0 + open(s) + close(s) + open(s) + close(s) + open(f) + 0]/4

=open + close/2 = 12.1 (ms)

Therefore,

B(0) = 1000/(l2.1 + 3.05 + 6) 47.28 bits/sec

The Upgraded Directory Channel

Ts = [T_s(nonempty->nonempty) + T_s(nonempty->empty) + T_s(empty->empty) + T_s(emptyÆnonempty)]/4

= [0 + unlink(s) + 0 + creat(s)]/4

=(creat + unlink)/4 = (30 + 22)/4 = 13(ms)

Tr = [T_r(nonempty->nonempty) + T_env(nonempty->nonempty) + T_r(nonempty->empty) + T_env(nonempty->empty) + T_r(empty->empty) + T_env(empty->empty) + T_r(empty->non-empty) + T_env(empty->nonempty)]/4

= [rmdir(f) + 0 + rmdir(s) + mkdir(s) + rmdir(s) + mkdir(s) + rmdir(f) + 0]/4

= [rmdir(s) + rmdir(f)l/2 + mkdir/2

=(180+3020)/2+260/2=1730 (ms)

Therefore,

B(0) = 1000/(1730 + 13 +6)=0.572bits/sec

http://www.fas.org/irp/nsa/rainbow/tg030.htm

_________________________

closest thing to my major related to work.

i ____ it.