![]() |
![]() |
![]() |
![]() |
![]() |
Validating an SDL System
In the previous exercises, we have navigated manually in the behavior tree. We have also found an error situation by studying the Navigator and the printed trace in the Command window.
In this exercise, we will show how to find errors and possible problems by automatically exploring the state space of the Demongame system. This is referred to as validating an SDL system.
What You Will Learn
- To perform an automatic state space exploration
- To examine reported errors using the Report Viewer
- To change state space and exploration options
- To restrict the state space without affecting the behavior
- To check the system coverage of an exploration
- To use user-defined rules
- To perform a random walk exploration
Performing a Bit State Exploration
Automatic state space exploration can be performed using different algorithms. The algorithm called bit state exploration can be used to efficiently validate reasonably large SDL systems. It uses a data structure called a hash table to represent the system states that are generated during the exploration.
An automatic state space exploration always starts from the current system state. Since we want to explore the complete Demongame system, we must first go back to the start state of the behavior tree.
- Go to the top of the tree by clicking the Top button in the Explore module.
- Start a bit state exploration by clicking the Bit-State button. After a few seconds, a tool called the Report Viewer is opened. We will soon describe this window; in the meantime, just move it away from the main window.
- For a small system such as Demongame, the exploration is finished almost immediately and some statistics are printed in the text area. They should look something like:
** Starting bit state exploration **Search depth : 100Hash table size : 1000000 bytes** Bit state exploration statistics **No of reports: 1.Generated states: 2569.Truncated paths: 156.Unique system states: 1887.Size of hash table: 8000000 (1000000 bytes)No of bits set in hash table: 3642Collision risk: 0 %Max depth: 100Current depth: -1Min state size: 68Max state size: 124Symbol coverage : 100.00
- Search depth : 100
The search depth limits the exploration; it is the maximum depth, or level, of the behavior tree. If this level is reached during the exploration, the current path in the tree is truncated and the exploration continues in another branch of the tree. It is possible to change the search depth by setting an option in the SDL Explorer UI.- No of reports: 1.
The exploration found one error situation. This error will be examined in the next exercise.- Truncated paths: 156.
The maximum depth was reached 156 times, i.e., there are parts of the behavior tree that were not explored. This is a normal situation for SDL systems with infinite state spaces. Demongame is such a system, since the game can go on forever.- Collision risk: 0 %
The risk for collisions was very small in the hash table that is used to represent the generated system states. If this value is greater than zero, the size of the hash table may have to be increased by setting an option; otherwise, some paths may be truncated by mistake. This situation will not occur in this tutorial.- Symbol coverage : 100.00
All SDL symbols in the system were executed during the exploration. If the symbol coverage is not 100%, the validation cannot be considered finished. This situation will occur in a later exercise.Examining Reports
The error situations reported from a state space exploration can be examined in the Report Viewer. The Report Viewer window displays the reports in the form of boxes in a tree structure.
- The top box shows how many reports there are (in this case only one).
- On the next level in the report tree, there is one box for each type of report, stating the number of reports of that type.
- On the next level, it is possible to see the actual reports. However, this level of the tree is by default collapsed, indicated by the small triangle icon below the report type boxes.
- To expand the report, double-click on the report type box Output. You will now see a box reporting the error we have found manually earlier. In addition, the tree depth of the error situation is shown.
- If you look in the Navigator and Command windows, you can see that the SDL Explorer is still in the start state of the system, even though a state space exploration has been performed. We will now go to the state where the error has occurred.
- Double-click the report box in the Report Viewer. The following things will now happen:
- The printed trace of the error situation is displayed in the text area of the Explorer UI and in the Command window.
- The Navigator moves to the error state and displays the error.
- An MSC Editor is opened, showing the MSC trace to the current state. You can see that the signal Bump was not received by any process, since the Game process has not yet been created. You should move the MSC Editor window so that it does not cover the other windows.
- Move up two steps by using the Up button. Of the two transitions possible from this state, the one that is part of the path leading to the error is indicated by three asterisks "***" (see Figure 130). This is the transition chosen when using the Down button.
- Move up to the top of the tree (click the Top button in the Explore module). Move down again to the error by using the Down button repeatedly.
Exploring a Larger State Space
We will now run a more advanced bit state exploration, with a different setting of the state space options. This will make the state space much larger, so that more error situations can be found.
- Go back to the top of the behavior tree (use the Top button).
- In the Options1 menu, select Advanced. This sets a number of the available state space options in one step, as you can see by the commands executed in the text area:
Command : def-sched allCommand : def-prio 1 1 1 1 1Command : def-max-input-port 2Max input port length is set to 2.Command : def-rep-log maxq offNo log for MaxQueueLength reports- In addition, we will increase the search depth of the exploration from 100 (the default) to 300. From the Options2 menu, select Bit-State: Depth. In the dialog, enter 300 and click OK.
- Since the behavior tree becomes much larger with these option settings, the exploration will take longer to finish. We will therefore show how to stop the exploration manually.
- Start a new bit state exploration. In the text area, a status message is printed every 20,000 transitions that are executed. Stop the exploration after one of the first status messages by pushing the Break button in the Explore module. The text area should now display something like this:
*** Break at user input ***** Bit state exploration statistics **No of reports: 2.Generated states: 50000.Truncated paths: 1250.Unique system states: 21435.Size of hash table: 8000000 (1000000 bytes)No of bits set in hash table: 41557Collision risk: 0 %Max depth: 300Current depth: 235Min state size: 68Max state size: 168Symbol coverage : 100.00
If the exploration finishes by itself before you have had a chance to stop it manually, redo this exercise from step 1. but increase the search depth even more, e.g. 3000 or even 10000.
- Note the following differences in the printed information compared to the previous exploration:
- No of reports: 2.
The exploration found an additional error situation. This is an effect of more transitions being able to execute from each state in the behavior tree.- Max depth: 300
Current depth: <number>
The exploration was at the printed depth in the behavior tree at the moment it was stopped. However, since the exploration uses a depth-first algorithm, the maximum depth of 300 was reached at an earlier stage. The exploration may be continued from the current depth if you wish to explore the remaining parts of the behavior tree.
- In the Report Viewer, open the two report type boxes to see both reports with a double-click on each. The Report Viewer window should now look something like:
- For now, just note on which depth each of the reported situations occurred; do not double-click any of the reports. (The depths may be different from the ones shown in the figure.)
- Continue the exploration by clicking the Bit-State button again. A dialog is opened, asking if you would like to continue the interrupted exploration or restart it from the beginning.
- In the dialog, select Continue and click OK. Wait for the exploration to finish by itself.
- In the Report Viewer, open the two reports again. Note that the depth values have changed. This is because only one occurrence of each report is printed; the one found at the lowest depth so far.
- Go to the state where an unsuccessful create of the Game process was reported (double-click the Create report).
- To see what caused the unsuccessful create, look at the MSC trace.
- At the receipt of the last Newgame signal, the Main process attempts to create a Game process. However, the already active Game process has not yet consumed the previous GameOver signal, and has therefore not been terminated. Since you cannot have more than one instance of the Game process in the Demongame system, the process create could not be executed!
Restricting the State Space
The SDL Explorer makes it possible to limit the state space in several different ways. We will now explore one of these methods that in many cases is very efficient. This is done by using the Define-Variable-Mode command.
This command is used to instruct the Explorer to ignore certain variables when matching states during the state space exploration. The mode can for each variable be set to either "Skip" or "Compare". The implication of setting the mode to "Skip" is that the search may be pruned even if a new state is encountered during the search. This happens if the only difference between the new state and a previously visited state is that the values of some of the skipped variables are different.
We will now apply this to our DemonGame system. The variable Count in the Game process keeps track of the current score for the game, and the value of this variable does not have any real impact on the behavior of the system. So, we will now instruct the explorer to ignore this variable when performing a search.
- Go to the top of the tree by clicking on the Top button.
- Enter the command define-variable-mode in the command line in the Explorer UI, select the Game process in the first dialog, the Count variable in the second dialog and Skip in the last dialog. You have now instructed the Explorer to ignore the Count variable.
- Start a bit state exploration by clicking on the Bit-State button. (Select to Restart the exploration if a dialog is opened.)
- When the search stops compare it with the previous exploration. The only difference between the two explorations is that the second one ignores the Count variable. However, while the first exploration took a long time to finish, the second one only took a few seconds! The printed statistics show very small numbers in comparison.
The lesson to learn from this is that it in many cases it is possible to drastically reduce the time needed for explorations by checking the variables in the system. Look for variables that do not have any impact on the behavior (i.e. that does not influence decision statements or the expression used in an "output to" statement). Also look for variables that do not change their value during the exploration. This can for example be arrays that are initialized at system start up but then never changes (or at least not changed in the intended exploration). The mode for these types of variables should be set to "Skip".
Checking the Validation Coverage
If the symbol coverage after an automatic state space exploration is less than 100%, the Coverage Viewer can be used to check what parts of the system that have not been executed. To attain a symbol coverage less than 100% for the Demongame system, we will set up the exploration in a special way.
- Go to the top of the tree.
- First, we need to restore the smaller, default state space. Select Default from the Options1 menu. Note that the Navigator changes back to display only a single possible transition from the top node.
- To avoid reaching all system states, we will reduce the search depth of the exploration from 100 to just 10. Use the Bit-State: Depth menu choice from the Options2 menu and specify a maximum depth of 10.
- Start a bit state exploration. The printed statistics should now inform you that the symbol coverage is about 82%.
- To find out which parts of the Demongame system that have not been reached, open the Coverage Viewer from the Commands menu.
Change to a transition coverage tree by clicking the Tree Mode quick-button.
- You can now see that none of the transitions from the state Winning in the Game process has been executed. To explore this part of the system in the explorer, you can go to the state Winning and start a new exploration from there. How to do this is explained in the following exercises.
Going to a State Using User-Defined Rules
To go to a particular system state, you could use the Navigator to manually find the state by studying the transition descriptions and the printed trace in the Command window. This can be both tedious and difficult, especially for larger systems than Demongame. Instead, we will show an easier way: by using a user-defined rule.
When performing state space exploration, the explorer checks a number of predefined rules in each system state that is reached. It is when such a rule is satisfied that a report is generated.
In this exercise, we will show how to define a new rule to be checked during state space exploration. The rule will be used to find the state Winning in the Game process.
- Make sure you still are at the top of the behavior tree.
- Define a new rule by selecting Define Rule from the Commands menu. In the dialog that appears, enter the rule definition
state(Game:1)=Winning
- This very simple rule says that the state of the process instance Game:1 must be equal to Winning. By defining the rule, a report will be generated when a state space exploration reaches a state that satisfies the rule.
- Start a bit state exploration. Since we have not changed any of the options since the last exploration the same statistics will be printed, with the exception that an additional report is generated.
- From the Report Viewer, go to the reported situation where the user-defined rule was satisfied. You have now reached the first place in the behavior tree where the Game process is in the state Winning.
- We now instruct the explorer to use this state as the root of the behavior tree. To do this, enter the command define-root on the input line and select Current in the dialog.
We can now change options, define a new rule or load an MSC. These new settings will then be used in all explorations based on the new root. Also all list/goto-path commands will use the path from the new root and the MSC trace will give the trace from the new root.
- Before continuing, do not forget to clear the user-defined rule. To do this, enter the command clear-rule on the input line.
In our case we will only clear the rule and start another type of state space exploration from this state; a random walk.
Performing a Random Walk
Apart from bit state exploration, there is another exploration method known as random walk. A random walk simply explores the behavior tree by repeatedly choosing a random path down the tree. This is mainly useful for SDL systems where the state space can be very large. But also for a small system like Demongame, it can be as effective as other exploration methods.
- Start a random walk exploration from the current state by clicking the Random Walk button. From the printed statistics, you can see that the symbol coverage now has become 100%.
- Load the Coverage Viewer with the new coverage information by selecting Show Coverage Viewer from the Commands menu. Change to transition coverage and display the whole tree. Note that all transitions have executed a large number of times. When the exploration selects a random path down the tree, there is no mechanism to avoid that already explored paths are explored once more. Therefore, the same transition may be executed any number of times
- Exit the Coverage Viewer from the File menu.
- Reset the system by selecting Reset from the Options1 menu. You are now back at the top of the tree, and the root of the tree is reset to the original root, the start state of the system.
http://www.ibm.com/rational |
![]() |
![]() |
![]() |
![]() |