9.5 A Formal Description of Program Operation

To assist in the subsequent discussion of program specification, it will be useful to make this description somewhat more precise by introducing some notation conveniences. Assume that a software system S was designed to implement a specific set of mutually exclusive functionalities F. Thus, if the system is executing a function f ∈ F, it cannot be expressing elements of any other functionality in F. Each of these functions in F was designed to implement a set of software specifications based on a user's requirements. From a user's perspective, this software system will implement a specific set of operations, O. This mapping from the set of user-perceived operations O to a set of specific program functionalities F is one of the major tasks in the software specification process.

A pilot astronaut on the Space Shuttle is not aware of the functionality of the Primary Avionics Software System (PASS) that governs the complete operation of the shuttle. A metaphor has been carefully constructed by system designers that permits the pilot to control the shuttle as if it were a standard airplane. The pilot, for example, has a control stick that controls two user-perceived operations: roll and pitch. These operations are implemented in software functions that monitor, for example, the change in resistance in x- and y-coordinate rheostats in the base of the control stick. The pilot operates the spacecraft. The software functions monitor the change in resistance in the rheostats.

Each operation that a system may perform for a user can be thought of as having been implemented in a set of business requirements. There may be a one-to-one mapping between the user's notion of an operation and a program function. In most cases, however, there will be several discrete functions that must be executed to express the user's concept of an operation. For each operation o that the system may perform, the range of functionalities f must be well known. It is possible, then, to define a relation IMPLEMENTS over O × F such that IMPLEMENTS(o, f) is true if functionality f is used in the specification of an operation, o. Within each operation, one or more of the system's functionalities will be expressed. For a given operation o, these expressed functionalities are those with the property:

F^(o) = {f:F|∀IMPLEMENTS(o,f)}

For each operation o ∈ O, there is a relation p' over O × F such that p'(o, f) is the proportion of activity assigned to functionality f by operation o. An example of the IMPLEMENTS relation for two operations implemented in four specified functions is shown in Exhibit 5. In this exhibit, we can see that functions f₁ and f₂ are used to implement the operation o₁. We can also see that functionality f₂ is a functional part of both operations.

Exhibit 5: Example of the IMPLEMENTS Relation

*O × F*	f₁	f₂	f₃	f₄
O₁	T	T
O₂		T	T	T

Exhibit 6 provides an example of the p' relation. These numbers represent the proportion of time each of the functions will execute under each of the operations. In operation o₁ functionality f₁ may or may not execute. The functionality f₂, on the other is hand, is quite likely to execute on operation o₁.

Exhibit 6: Example of the p'Relation

*P'(o, f)*	f₁	f2	f₃	f₄
o₁	0.2	0.8	0	0
o₂	0	0.4	0.4	0.2

The software design process is basically a matter of assigning functionalities in F to specific program modules m ∈ M, the set of program modules. The design process can be thought of as the process of defining a set of relations, ASSIGNS over F × M such that ASSIGNS(f, m) is true if functionality f is expressed in module m. For a given software system S, let M denote the set of all program modules for that system. For each functionality f ∈ F, there is a relation p over F × M such that p(f, m) is the proportion of execution events of module m when the system is executing function f. Exhibit 7 shows an example of the ASSIGNS relation for the four functions presented in Exhibit 5. In this example we can see that the function f₁ has been implemented in the program modules m₁ and m₂ . One of these modules, m₁, will be invoked regardless of the functionality. It is common to all functions. Other program modules, such as m₂, are distinctly associated with a single function.

Exhibit 7: Example of the ASSIGNS Relation

F × M	m_l	m₂	m₃	m₄	m₅	m₆	m₇	m₈
f₁	T	T
f₂	T		T		T			T
f₃	T		T	T	T	T
f₄	T		T		T	T	T

Exhibit 8 provides an example of the p relation. These numbers represent the likelihood that each of the program modules will execute when a particular functionality is invoked. Exhibit 8 represents the proportion of time distributed across each of the six hypothetical program modules. We can see, for example, that p(f₁, m₁) = 1. This means that whenever functionality f₁ is invoked, module m₁ will always be executed. On the other hand, we can also observe that p(f₃, m₅) = 0.2. In this case, there is a relatively low chance that module m₅ will execute, given that functionality f₂ has been invoked.

Exhibit 8: Example of the p Relation

p(f,m)	m₁	m₂	m₃	m₄	m₅	m₆	m₇	m₈
f₁	1	1	0	0	0	0	0	0
f₂	1	0	1	0	1	0	0	1
f₃	1	0	1	1	0.2	0.3	0	0
f₄	1	0	1	0	1	1	1	0

There is a relationship between program functionalities and the software modules they will cause to be executed. These program modules will be assigned to one of three distinct sets of modules that, in turn, are subsets of M. Some modules may execute under all of the functionalities of S. This will be the set of common modules. The main program is an example of such a module that is common to all operations of the software system. Essentially, program modules will be members of one of two mutually exclusive sets. There is the set of program modules M_c of common modules and the set of modules M_F that are invoked only in response to the execution of one or more functionalities. It is clear, then, that M_F = M-M_c.

The set of common modules, M_c ⊂ M is defined as those modules that have the property:

M_c = {m: M | ∀f ∈ F • ASSIGNS(f,m)}

All of these modules will execute regardless of the specific functionality being executed by the software system.

Yet another set of software modules may or may not execute when the system is running a particular function. These modules are said to be potentially involved modules. The set of potentially involved modules is:

In other program modules, there is extremely tight binding between a particular functionality and a set of program modules. That is, every time a particular function f is executed, a distinct set of software modules will always be invoked. These modules are said to be indispensably involved with the functionality f. This set of indispensably involved modules for a particular functionality f is the set of those modules that have the property:

As a direct result of the design of the program, there will be a well-defined set of program modules M_f that might be used to express all aspects of a given functionality f. These are the modules that have the property:

From the standpoint of software design, the real problems in understanding the dynamic behavior of a system are not necessarily attributable to the set of modules M_i that are tightly bound to a functionality or to the set of common modules M_c that will be invoked for all executing processes. The real problem is the set of potentially invoked modules M_p. The greater the cardinality of this set of modules, the less certain we can be about the behavior of a system performing that function. For any one instance of execution of this functionality, a varying number of the modules in M_p may execute.

For each functionality f ∈ F, there exists a relation c over F × M such that c(f,m) defines the cardinality of the set of functionalities that can call a given module. The c relation can be used to partition the set of program modules into two distinct sets. One set contains the modules associated exclusively with one and only one functionality.^[1] This is the set of uniquely related modules M_u, where:

M_u={m:M| f ∈ F,c(f,m) = 1}

The second set contains the modules that might be executed by more than one functionality, that is, the set of shared modules M_s, to wit:

M_s={m:M|f ∈ F•c(f,m)>1}

There are two distinct ways, then, that we can view program modules associated with functionalities. First, given a functionality, we can characterize each module as indispensably associated with that functionality or potentially associated with it. Second, each program module may or may not be uniquely associated with a given functionality. These two different module classifications are shown in Exhibit 9.

Exhibit 9: Module Classification

Among Functionalities	Within a Functionality
Unique Shared	Indispensable Potential

A functionality will, by definition, be required to have at least two modules and that at least one of them is an element of the set of uniquely related modules and not of the set of potentially involved modules. That is:

If each program module were distinctly associated with a single functionality, then the dynamic behavior of a system could be readily understood and modeled. The two sets M_i and M_s are tightly bound to a distinct functionality. The real problem resides in the set of shared modules M_s and it increases in severity if those modules also belong to M_p. The greater the cardinality of the set of potentially executable modules, the more difficult the task of determining the behavior of a system performing that functionality. In the extreme case, a functionality could express essentially disjoint sets of modules every time it is executed. (Many programs demonstrate this characteristic and they are extremely difficult to test.)

It is clear that each functionality will exercise a certain subset of modules. To return to our example, we can see from Exhibit 10 that functionality f₁ does invoke two modules: m₁, and m₂. Both modules are indispensable to the execution of functionality f₁. Module m_l is shared with all other functionalities. Module m₂ is uniquely associated with functionality f₁. In Exhibit 10 we can also see that functionality f₃ has some interesting properties. The set is nonempty in this case. Whenever we exercise f₃ we can execute from three to five modules. It will be difficult to test this functionality in relation to all other functionalities. Sometimes it will execute module m₅ and sometimes it will not. Sometimes it will execute module m₆ and sometimes it will not. Sometimes it will execute both modules and sometimes it will not.

Exhibit 10: Modules Associated with Functionalities


f₁	{m₁,m₂}	{}	{m₁}	{m₂}
f2	{m₁, m₃, m₅, m₈}	{}	{m₁, m₃, m₅}	{m₈}
f₃	{m₁, m₃, m₄}	{m₅, m₆}	{m₁, m₃, m₅, m₆}	{m₄}
f₄	{m₁, m₃, m₅, m₆, m₇}	{}	{m₁, m₃, m₅, m₆}	{m₇}

Sometimes it will be desirable to know what functionality is executing at any given moment. We have built a system that will make such a deduction very difficult. For example, if we have just observed the execution of module m₁, we cannot deduce which functionality we are executing. Similarly, there is an equivalent problem with module m₃. There is somewhat more information in the observation of the execution of module m₆. If we have just observed this module execute, then we will know that we are executing either f₃ or f₄. The case for module m₂ is very different. Whenever we see this module executing, we know for a fact that we are now executing functionality f₁.

Now let us return to the problem of operations. Users see and perform operations. Functionalities are used by systems designers to implement the set of user operations. From the relationships defined above, we can now clearly establish the relationship between user operations and specific modules that will be exercised in response to a user invoking a particular operation. That is, each operation will be implemented by a specific set of functionalities. These functionalities will, in turn, invoke a specific set of modules when they are executed. Thus, for each operation o, we can clearly establish a set of program modules associated with the expression of that operation at runtime.

Each operation is distinctly expressed by a set of functionalities. If a particular operation o is defined by functionalities a and b, then the set of program modules that are bound to operation o is:

If one operation is to be distinguished from another, then there must be certain aspects of its implementation in functionalities that will be unique. For an operation to be considered distinct, it will be required to have at least one distinct functionality. That is, o_i ∈ O if the set of distinct functionalities defined as:

has cardinality greater than one.

If we insist that each operation has at least one distinct functionality, then it is possible to identify a set of modules for each operation that is uniquely associated with that operation. This set of modules for operation o_i is:

When a program is executing a module m, where , it is quite clear that the user is expressing operation o_i. If we wish to determine exactly what the user is doing at any point, we have only to instrument the set of modules . As we receive telemetry from each of the modules so instrumented, the sequence of user operations will be eminently clear.

We can now map the operations in our example to specific program modules. This mapping is shown in Exhibit 11. The specific value of this mapping is twofold. First, if the specification for operation O₁ must be changed, we can identify which modules are associated with this operation. Second, there are certain modules that tag each operation that is, they uniquely identify the operation. If, for example, we saw either module in the set {m₂, m₈}, we would then know that operation o₁ was currently being executed by the user.

Exhibit 11: Modules Associated with Operations


O₁	{m₁,m₃,m₅,m₈}	{m₂}	{m₁,m₃,m₅}	{m₂,m₈}
O₂	{m₁,m₃,m₅,m₆,m₇}	{}	{m₁,m₃,m₅}	{m₃,m₄,m₆,m₇}

^[1], Elbaum, S.G. and Munson, J.C., Investigating Software Failures with a Software Blackbox, Proceedings of the 2000 IEEE Aerospace Applications Conference, IEEE Computer Society Press, November 2000.