In-Depth

Use-Case Tree

Use cases1,2 have proved effective in many areas of software development, including requirements gathering, object identification, test case generation, and user manual documentation. A new application of use cases is the verification of software specifications prior to implementation. Use-case trees show a new view of the system and, constructed from the state-transition models of object-oriented specifications, can be used to verify the system specification for correctness. Paths from the root of the tree to leaf nodes correspond to use-case scenarios, and there should be no more paths in the tree than there are scenarios.

The use-case tree provides a new view of a system in that it shows an overall picture of all the possible scenarios the system can take. This has a flowchart feel that is often desired by project managers, for example, to gain an overall picture of how the system is expected to behave.

The use-case tree could be incorporated quite comfortably into the UML as it is based on existing formalisms (use cases and state transition models).

The use-case tree has evolved from the development of COMX3 and its object-oriented counterpart Object COMX.4 These methods are based on the formal specification technique of communicating X-machines.5 In Object COMX, a formal specification of the system can be verified using a reachability analysis, which involves the construction of a reachability tree. Researching ways in which the tree could be used to prove system correctness led to the development of the use-case tree.

USE CASES
Use cases were developed by Ivar Jacobson and put to use for the first time in 1967 while he worked in the development of large telecommunication switching systems. Subsequently, he employed the use case as a basis for the Objectory process1 and since then use cases have formed an important element of many object-oriented software development projects worldwide.

Use cases were originally developed for use in the requirements gathering and analysis phases of software development because they were seen as an excellent way to bridge the gap between customers and analysts/designers. Customers benefit from the way use cases describe, in natural language, all the scenarios in the system. Analysts/designers benefit from use cases because they help to identify the objects of the system. Use cases have proved effective in these other areas of software development:6

  • Object-oriented modeling: Use cases lead the analysis phase into the object-oriented modeling phase through use-case scenario models (collaboration diagrams in UML, for example). Each event in the scenario can be regarded, directly or indirectly, as a method of an object, and thus the modeler can start to build up the objects of the system and their methods.
  • Test case generation: A thorough set of use cases and their scenarios, including error-handling scenarios, can be passed on to the testing team as a basis for their test cases.
  • Project scheduling: Use cases can also be of use to the project manager in the generation of schedules, ensuring that every requirement of the system is represented in the project plan.
  • User manual documentation: Because use cases are often written from a user-driven perspective, they form very useful input to the user manual documentation.

This article presents a new area of application for the use case: the verification of the system specification. This technique will be presented via a case study, described in the next section.

CASE STUDY
Lottery kiosk
In the UK, many newsagents are able to sell lottery tickets. What is particularly annoying are the long queues that can build up within the shop, worsened by the fact that many of the people in the queue are buying more than just lottery tickets (cigarettes, for example). Those people who require just lottery tickets must wait their turn.

A lottery kiosk would be a dedicated service for lottery tickets only. Some of these exist in shopping precincts, employing personnel to sell the tickets. A lottery kiosk would be totally automatic. A user would enter coinage, choose their numbers (including a lucky dip option where the kiosk chooses a random set of numbers), and their ticket would be dispensed. The kiosk would process this data and send it to the main computer at lottery headquarters.

The kiosk must make sure the user has entered the correct coinage and entered valid numbers (not the same number in one line), all within time limits. The user can request a refund of their coins prior to number entry. The kiosk itself can run out of paper or can receive messages from headquarters to put it "out of order."

Use cases
A number of use cases and their scenarios have been identified for the lottery kiosk, as listed.


Use Case 1: The user attempts to obtain a lottery ticket.
    Scenario 1: The user successfully obtains a lottery ticket using
    their chosen numbers.
    Scenario 2: The user successfully obtains a lottery ticket using
    the lucky dip option.
    Scenario 3: The user takes too long in choosing their numbers—refund coins.
    Scenario 4: The user takes too long choosing their numbers—
    restart.
    Scenario 5: The user has entered the wrong, or not enough,
    coinage.
    Scenario 6: The user requires their coins refunded.
    Scenario 7: The user enters invalid numbers (such as the same
    number twice for a particular line).

Use Case 2: The kiosk is out of order.
    Scenario 1: The lottery kiosk runs out of paper (for the lottery
    tickets).
    Scenario 2: The kiosk is put out of order for some reason.
Each of these use cases can be described in more detail, as sequences of events. Use Case 1, Scenario 2 is detailed as follows. It is important here to associate each event in the scenario as a single distinct event on a single object.


Use Case 1, Scenario 2: The user successfully obtains a lottery 
ticket using the lucky dip option:
    1.  Default welcome display on screen
    2.  User enters coinage
    3.  Kiosk checks the coinage—calculates the number of lines
    4.  Kiosk displays the "Enter your numbers" screen
    5.  User presses the lucky dip button
    6.  A lucky dip combination is selected by the kiosk
    7.  Repeat steps 4 to 6 for each lucky dip required
    8.  Kiosk displays message "Ticket being printed.
		Thank you for using the lottery kiosk"
    9.  Ticket is printed
    10.  Kiosk displays message "Please take your ticket"
    11.  Ticket information is sent to lottery headquarters
    12.  User takes ticket
Formal specification
To be able to utilize the verification techniques offered by the use-case tree, the system needs to be specified in a particular manner. This form takes an object perspective of the system. Figure 1 is the object communication diagram of the lottery kiosk. The objects were identified from the use case descriptions: each event in the use case corresponds, either directly or indirectly, to a method of an object. Figure 1 shows the interaction of the objects within the system and with the environment. The arrows show the movement of data or control.

Figure 1
Figure 1. Object communication diagram of the lottery kiosk.

Each object can be modeled as a sequential process and this lends itself to be modeled in a state transition manner (in this case as communicating X-machines5). In Figure 2 the kiosk object is modeled in this manner, followed by the user interface object in Figure 3. Figure 3 has one state and two transitions, Display [26] and UserInput [27], which can occur at any time. Each transition responds to one or more events (from other objects or the environment) and subsequently performs an operation. As a result, it may trigger one or more events in other objects. The transitions are labeled as in the list that follows. The detailed specification of transition [5] is given. This transition is triggered by the coin monitor registering the value of the coins entered (value? = x). The kiosk registers this amount and sends a message to the user interface to inform the user they have 'x' lines of numbers to choose and to reset the clock (for time-out monitoring).

Figure 2
Figure 2. State transition model of the kiosk object.

Figure 3
Figure 3. State transition model of the user interface object.


    [0] InitialWelcomePage
    [1] ShowWelcomePage
    [2] CalculateNoLines
    [3] IncorrectCoinage
    [4] RefundIncorrectCoinage
    [5] EntersCorrectCoinage: Input: value? = x, From Coin
    Monitor) (x: INTEGER)
    Output: (screen! = 'You have' x 'lines', To User Interface)
    (action! = reset, To Clock)
    [6] AllowNumberEntry
    [7] InputNumbers
    [8] LuckyDip
    [9] CheckNumbers
    [10] Timeout
    [11] Restart
    [12] FinishNumberEntry
    [13] TicketPrinted
    [14] EndSession
    [15] Refund
    [16] PutOutOfOrder
    [17] BackToWorkingOrder
    [18] OutOfPaper
    [19] InPaper
Once all the objects and their transitions have been specified formally, the system is ready for verification via a use-case tree.

USE-CASE TREE CONSTRUCTION
A use-case tree shows, in a treelike structure, the possible global states and paths the system can take. It is developed from the state transition object specifications and shows a completely new view of the system. This view makes it easy to identify whether deadlock occurs or whether the system terminates (if it is supposed to). As well, each use-case scenario, as documented in the requirements analysis phase, should be represented as a path on the tree, so we can use the tree to prove system correctness.

Use-case tree construction
The construction of the use-case tree follows these steps:

  • Obtain the state transition diagrams of all of the objects to be used in the analysis.
  • Identify the initial state of these models—this is the state with the free arrow pointing into it. The combined states form the initial global state and this is the root node of the tree ROOT NODE.
  • From this root, node branches to the next possible global states are drawn. Each branch represents a state transition (labeled object.method). However, a state transition in one object can also cause state transitions to occur in other objects and so it is important to recognize these from the formal specification and represent them on the tree. The next global state is determined by assuming a predicate (on a transition) evaluates to TRUE, where the predicate is based on input from the environment. This is done in turn for each predicate on each transition, thus giving a set of permutations of possible next global states. All these global states are on the end of branches from the root node and are called "frontier" nodes.
  • Each of these frontier nodes are now treated in the same way as the root node in the previous step, and all the possible global states from these are placed on the end of branches from the node. Again, this is done through consideration of the presence of data from objects or data from the environment.
  • For each node placed on the tree, the following are checked:
    • Does the node contain all terminal states? If so, no more branching is required from this node and it is called a terminal node.
    • Does the node contain a global state that already appears on the tree? This is called a duplicate node. No more development of the tree is required from a duplicate node.
    • Can any more branching from this global state take place according to the formal specification? In other words, are there any more transitions from this global state (based on data from the environment or data communicated from another object) that can evaluate to TRUE? If not, and it is not a terminal node, then the node is called a deadlocked node and further action must be taken to eliminate it.
    • When each frontier node is identified as a duplicate, terminal, or deadlocked node, then no further construction of the tree can take place. The end nodes at the end of each branch are called leaf nodes, LEAF NODE.

The number of possible global states that a system can enter can be immense, even for small systems. This means the construction of the use-case tree is made increasingly harder as the size of the system increases. Identifying duplicate nodes can reduce the size of the tree. A duplicate node is simply a node representing a global state that already exists higher up in the tree. We do not have to consider any behavior after this state because it is already accounted for higher up in the tree. The same applies here to a global state that loops back on itself, which can also be regarded as a duplicate node. Duplicate nodes are labeled with [D] on the use-case tree.

Figure 4
Figure 4. Typical use-case tree structure.

The use-case tree for the lottery kiosk is presented as a list of the paths. In total, nine paths were identified; a selection of these is presented in Listing 1. These lists could be shown graphically in a treelike structure, as in Figure 4. Each list consists of nodes and events, labeled as follows:


•[state, state, state .... ]      represents a global state
—> Object.Event               represents an event
Inside the nodes are the global states, labeled in the following order and containing the following states:


KIOSK: Start (s), Out of Order (oo), Out Of Paper (oop),
Correct Coinage (cc), Incorrect Coinage (ic),
Enter Numbers (en), Ticket Printed (tp),
Restart/Refund (rr), Ticket Out (to)
TICKET PRINTER: In Paper (ip), Out Of Paper (op)
COIN MONITOR: Weigh Coins (wc)
CLOCK: Tick (t)
USER INTERFACE: Display (d)
USE-CASE TREE ANALYSIS
We can use the use-case tree to investigate a number of properties.

Correctness—use case verification
Correctness is the property that says the system performs as detailed in the requirements specification of that system. In this case, we can refer back to the list of use cases that were used to construct the requirements specification. Each use-case scenario should be represented on the use-case tree as a downward link of nodes, starting from the root node. There should be no more paths in the tree than there are use-case scenarios. Each branch of the use-case tree represents an event in the scenario. In addition to this, we can check that all states the system should enter do exist on the tree, as well as look out for any unwanted states the system may enter.

Reachability
In a set of interacting objects a global state G' is said to be reachable from a global state G if there exists a sequence of transition firings that transforms G to G'. Reachability can be identified on the use-case tree by a direct downward link from state G to G'.

Deadlock
Deadlock is shown by the presence of a deadlock node in the use-case tree. To overcome this, a release of resources from a particular object is required.

Termination
A set of interacting objects, which is required to terminate at some point, will have a use-case tree with reachable terminal nodes. Terminal nodes are leaf nodes composed of all terminal states.

Case study
The tree shows that deadlock does not occur in the system and that termination does not occur since there are no terminal states in any of the objects. The main use of the tree in this case is to prove the correctness of the specification against the use- case requirements. Each path of the tree (starting at the root) should correspond to a use-case scenario. There are nine paths in the tree, which correspond with the nine scenarios identified in the use case analysis.

Let's look at one use case associated with this system: the user obtaining a lottery ticket using the lucky dip option (Use Case 1, Scenario 2). To verify that our system satisfies this requirement, we must identify this sequence of events on the use-case tree as a sequence of branches, from the root node to a leaf node. This can be identified in Path 2 (Listing 1). The sequence of events in the use-case scenario can be mapped against the methods the branches in the paths represent. Other use-case requirements can be identified in the same way. The number of scenarios should equal the number of paths from the root node to leaf nodes on the tree.

CONCLUSION
The use-case tree is a diagrammatic representation of all the paths (scenarios) a system can take. It allows the software specification to be compared to the requirements specification (in use-case format) to prove its correctness, as well as analyzes the specification for properties such as freedom from deadlock, reachability, and termination.

The use-case tree for carrying out this analysis is easy to construct from a state transition model of the system (communicating X-machines, for example), and provides a new view of the system. Any discrepancies between the use-case tree and the use-case scenarios can be sorted out before implementation stage. This global view of the system can be used in other situations—to help in the understanding of the system, for example. The use-case tree fits comfortably with the formalisms of the UML.

However, there are certain drawbacks and limitations to this kind of technique. The use-case tree is based on the global state of the system and this can lead to the state explosion problem, even for small systems. This means the size of the tree can grow to unmanageable proportions. A method for splitting the tree into meaningful branches could be one avenue of research, as could the possibility of automating the process via a CASE tool.

The use-case tree works best with systems with one single thread of execution. It can still be applied to systems with concurrent threads, but will require more complex tree management. It also helps if the system is dynamic in nature and so lends itself to state transition modeling.

References

  1. Jacobson, I. et al. Object-Oriented Software Engineering: A Use Case Driven Approach, Addison–Wesley, Reading, MA, 1996.
  2. Schneider, G., and J. P. Winters. Applying Use Cases: A Practical Guide, Addison–Wesley, Reading, MA, 1998.
  3. Barnard, J. "COMX: A Methodology Using Communicating X-machines," Information and Software Technology, 40(5–6): 271–280, July 1998.
  4. Barnard, J. "Object COMX: Methodology Using Communicating X-machine Objects," JOOP, 12(7): 12–17, Nov./Dec. 1999.
  5. Barnard, J., J. Whitworth, and M. Woodward. "Communicating X-machines," Information and Software Technology, 38(6), June 1996.
  6. Hurlbut, R. R. A Survey of Approaches for Describing and Formalizing Use Cases, Document: XPT-TR-97-03, Expertech Ltd., Wheaton, IL, 1997.

Most   Popular