Software Testing Methodologies�
UNIT-7 STATES, STATE GRAPHS, AND TRANSITION TESTING
Compiled with reference from:
Software Testing Techniques: Boris Beizer
Craft of Software Testing: Brain Marrick
Contents
SYNOPSIS
MOTIVATIONAL OVERVIEW
STATE GRAPHS
1. Implementation and Operation
2.Input Encoding and Input Alphabet
3.Output Encoding and Output Alphabet
4.State Codes and State-Symbol Products
5.Application Comments for Designers
6.Application Comments for Testers
�STATE GRAPHS�States
Figure11.1
STATE GRAPHS�States(continued)
1. Reverse gear
2. Neutral gear
3. First gear
4. Second gear
5. Third gear
6. Fourth gear
�STATE GRAPHS�Inputs and Transitions
�STATE GRAPHS�Inputs and Transitions
STATE GRAPHS�Outputs
STATE GRAPHS�State Tables
INPUT | |
STATE | OKAY | ERROR |
1 | 1/NONE | 2/REWRITE |
2 | 1/NONE | 4/REWRITE |
3 | 1/NONE | 2/REWRITE |
4 | 3/NONE | 5/ERASE |
5 | 1/NONE | 6/ERASE |
6 | 1/NONE | 7/OUT |
7 | . . . | . . . |
| | |
1. Each row of the table corresponds to a state.
2. Each column corresponds to an input condition.
3. The box at the intersection of a row and column specifies the next state (the transition) and the output, if any
STATE GRAPHS�Time Versus Sequence
Time | Sequence |
1. State graphs don’t represent time | 1.State graphs represent sequence. |
A transition might take microseconds or centuries; a system could be in one state for milliseconds and another for eons, or the other way around; | the state graph would be the same because it has no notion of time |
Although the finite-state machine model can be elaborated to include notions of time in addition to sequence, such as timed Petri nets
Software Implementation�1.Implementation and Operation
Software Implementation�1.Implementation and Operation
Software Implementation�1.Implementation and Operation
Software Implementation�2.Input Encoding and Input Alphabet
Software Implementation�3.Output Encoding and Output Alphabet
Software Implementation�4.State Codes and State-Symbol Products
Software Implementation�5. Application Comments for Designers
Software Implementation�6. Application Comments for Testers
GOOD STATE GRAPHS AND BAD�1. General
GOOD STATE GRAPHS AND BAD�2.State Bugs�2.1Number of States
Functional specifications are used to find
GOOD STATE GRAPHS AND BAD�2.State Bugs�Impossible States
GEAR | R, N, 1, 2, 3, 4 | = 6 factors |
DIRECTION | Forward, reverse, stopped | = 3 factors |
ENGINE | Running, stopped | = 2 factors |
TRANSMISSION | Okay, broken | = 2 factors |
ENGINE | Okay, broken | = 2 factors |
TOTAL | | = 144 states |
There are some combinations of factors that are impossible. The states inclusion of
these factors are known as impossible states. Impossible states do not have specific meaning in the system.
Power supply | On,Off | = 2 factors |
Operating System | Loaded, Unloaded | = 2 factors |
Processing Speed | Fast, Medium, Slow | = 3 factors |
Application | Running, Stopped | = 2 factors |
Power supply | Okay, Damage | = 2 factors |
TOTAL | | = 48 states |
GOOD STATE GRAPHS AND BAD�2.State Bugs�Equivalent States
GOOD STATE GRAPHS AND BAD�2.State Bugs�Equivalent States
GOOD STATE GRAPHS AND BAD�2.State Bugs�Equivalent States
GOOD STATE GRAPHS AND BAD�2.State Bugs�Equivalent States
GOOD STATE GRAPHS AND BAD�2.State Bugs�Equivalent States
GOOD STATE GRAPHS AND BAD�3.Transition Bugs�1. Unspecified and Contradictory Transitions
GOOD STATE GRAPHS AND BAD�3.Transition Bugs�3.2An Example
GOOD STATE GRAPHS AND BAD�3.Transition Bugs�3.2An Example
INPUT | |
STATE | OKAY | ERROR |
0 | 0/none | 1/ |
1 |
| 2/ |
2 |
| 3/ |
3 |
| 4/ |
4 |
| 5/ |
5 |
| 6/ |
6 |
| 7/ |
7 |
| 8/ |
There are only two input values, “okay” and “error.”
Rule 2: | If there is an error, rewrite the block. |
Rule 3: | If there have been three successive errors, erase 10 centimeters of tape and then rewrite the block. |
Rule 4: | If there have been three successive erasures and another error occurs, put the unit out of service. |
Rule 5: | If the erasure was successful, return to the normal state and clear the error counter. |
Rule 6: | If the rewrite was unsuccessful, increment the error counter, advance the state, and try another rewrite. |
Rule 7: | If the rewrite was successful, decrement the error counter and return to the previous state. |
GOOD STATE GRAPHS AND BAD�3.Transition Bugs�3.2An Example
INPUT | |
STATE | OKAY | ERROR |
0 | 0/NONE | 1/REWRITE |
1 |
| 2/REWRITE |
2 |
| 3/REWRITE |
3 |
| 4/REWRITE |
4 |
| 5/REWRITE |
5 |
| 6/REWRITE |
6 |
| 7/REWRITE |
7 |
| 8/REWRITE |
GOOD STATE GRAPHS AND BAD�3.Transition Bugs�3.2An Example
Rule 3: | If there have been three successive errors, erase 10 centimeters of tape and then rewrite the block. |
GOOD STATE GRAPHS AND BAD�3.Transition Bugs�3.2An Example
INPUT | |
STATE | OKAY | ERROR |
0 | 0/NONE | 1/REWRITE |
1 |
| 2/REWRITE |
2 |
| 3/REWRITE, ERASE, REWRITE |
3 |
| 4/REWRITE, ERASE, REWRITE |
4 |
| 5/REWRITE, ERASE, REWRITE |
5 |
| 6/REWRITE, ERASE, REWRITE |
6 |
| 7/REWRITE, ERASE, REWRITE |
7 |
| 8/REWRITE, ERASE, REWRITE |
Rule 4: | If there have been three successive erasures and another error occurs, put the unit out of service. |
GOOD STATE GRAPHS AND BAD�3.Transition Bugs�3.2An Example
Rule 3, if followed blindly, causes an unnecessary rewrite. It’s a minor bug, so let it go for now, but it pays to check such things. There might be an arcane security reason for rewriting, erasing, and then rewriting again.
INPUT |
|
STATE | OKAY | ERROR |
0 | 0/NONE | 1/RW |
1 |
| 2/RW |
2 |
| 3/ER, RW |
3 |
| 4/ER, RW |
4 |
| 5/ER, RW |
5 |
| 6/OUT |
6 |
|
|
7 |
|
|
Rule 5: | If the erasure was successful, return to the normal state and clear the counter. |
GOOD STATE GRAPHS AND BAD�3.Transition Bugs�3.2An Example
Rule 4 terminates our interest in this state graph so we can dispose of states beyond 6. The details of state 6 will not be covered by this specification; presumably there is a way to get back to state 0. Also, we can credit the specifier with enough intelligence not to have expected a useless rewrite and erase prior to going out of service.
INPUT |
STATE | OKAY | ERROR |
0 | 0/NONE | 1/RW |
1 |
| 2/RW |
2 |
| 3/ER, RW |
3 | 0/NONE | 4/ER, RW |
4 | 0/NONE | 5/ER, RW |
5 | 0/NONE | 6/OUT |
6 |
|
|
Rule 6: | If the rewrite was unsuccessful, increment the error counter, advance the state, and try another rewrite |
GOOD STATE GRAPHS AND BAD�3.Transition Bugs�3.2An Example
Rule 7: If the rewrite was successful, decrement the error counter and return to the previous state.
| INPUT |
STATE | OKAY | ERROR |
0 | 0/NONE | 1/RW |
1 | 0/NONE | 2/RW |
2 | 1/NONE | 3/ER, RW |
3 | 0/NONE�2/NONE | 4/ER, RW |
4 | 0/NONE�3/NONE | 5/ER, RW |
5 | 0/NONE�4/NONE | 6/OUT |
6 |
|
|
Rule 7 got rid of the ambiguities but created contradictions. The specifier’s intention was probably:
Rule 7A: If there have been no erasures and the rewrite is successful, return to the previous state.
GOOD STATE GRAPHS AND BAD�3.Transition Bugs�3.2An Example
GOOD STATE GRAPHS AND BAD�3.Transition Bugs�3.3 unreachable state
GOOD STATE GRAPHS AND BAD�3.Transition Bugs�3.4 Dead States
GOOD STATE GRAPHS AND BAD�4. Output Errors
GOOD STATE GRAPHS AND BAD�5. Encoding Bugs
STATE TESTING�1.Impact of Bugs
STATE TESTING�2. Principles
STATE TESTING �3. Limitations and Extensions
STATE TESTING �4.What to Model
STATE TESTING �4.What to Model
STATE TESTING �5. Getting the Data
STATE TESTING �6. Tools
TESTABILITY TIPS�1. A Balm for Programmers
TESTABILITY TIPS�2. How Big, How Small?���
TESTABILITY TIPS�3. Switches, Flags, and Unachievable Paths
Switches, Flags, and Unachievable Paths�(continued)
�TESTABILITY TIPS�3.Switches, Flags, and Unachievable Paths
TESTABILITY TIPS�4. Essential and Inessential Finite-State Behavior
Design Guidelines
Finite State Machine
5. If time or space is more effecting the overall system, then use shortcuts to complete the design process. It can be achieved by implicit design of FSM in the following order i.e., output encoding, input encoding, state code, state symbol product, output table, transition table and state storage.
6. If there are more than a few number of states then use hierarchical design to represent them.
7. If there are large no. of states then s/w tools and programming languages must be developed or purchased in order to implement the FSM.
8. The capability to initialize to any arbitrary state must be inbuilt together with the transition verification instrumentation. These are much easier to do with an explicit machine.
TESTABILITY TIPS�5. Design Guidelines
TESTABILITY TIPS�5. Design Guidelines
After all, doubling the speed of your implementation may mean nothing if all you’ve done is shaved 100 microseconds from a 500-millisecond process. The order in which you should make things implicit are: output encoding, input encoding, state code, state-symbol product, output table, transition table, state storage. That’s the order from least to most dangerous.
Important
UNIT 8—GRAPH MATRICES AND APPLICATIONS
To be continue……………..