What are some strategies for testing large state m

Question

I inherited a large and fairly complex state machine. It has 31 possible states, all are really needed (big business process). It has the following inputs:

• Enum: Current State (so 0 -> 30)
• Enum: source (currently only 2 entries)
• Boolean: Request
• Boolean: Type
• Enum: Status (3 states)
• Enum: Handling (3 states)
• Boolean: Completed

Breaking it into separate state machines doesn't seem feasible, as each state is distinct. I wrote tests for the most common inputs, with one test per input, all inputs constant, except for the State.

[Subject("Application Process States")]
public class When_state_is_meeting2Requested : AppProcessBase
{
    Establish context = () =>
    {
        //Setup....
    };

    Because of = () => process.Load(jas, vac);

    It Current_node_should_be_meeting2Requested = () => process.CurrentNode.ShouldBeOfType<meetingRequestedNode>();
    It Can_move_to_clientDeclined = () => Check(process, process.clientDeclined);
    It Can_move_to_meeting1Arranged = () => Check(process, process.meeting1Arranged);
    It Can_move_to_meeting2Arranged = () => Check(process, process.meeting2Arranged);
    It Can_move_to_Reject = () => Check(process, process.Reject);
    It Cannot_move_to_any_other_state = () => AllOthersFalse(process);
}

No one is entirely sure what the output should be for each state and set of inputs. I have started to write tests for it. However, I'll need to write something like 4320 tests (30 * 2 * 2 * 2 * 3 * 3 * 2).

What suggestions do you have for testing state machines?

---

Edit: I am playing with all of the suggestions, and will mark an answer when I find one that works best.

Answer 1

I see the problem, but I'd definitely try splitting the logic out.

The big problem area in my eyes is:

• It has 31 possible states to be in.
• It has the following inputs:
  • Enum: Current State (so 0 -> 30)
  • Enum: source (currently only 2 entries)
  • Boolean: Request
  • Boolean: type
  • Enum: Status (3 states)
  • Enum: Handling (3 states)
  • Boolean: Completed

There is just far too much going on. The input is making the code hard to test. You've said it would be painful to split this up into more manageable areas, but it's equally if not more painful to test this much logic in on go. In your case, each unit test covers far too much ground.

This question I asked about testing large methods is similar in nature, I found my units were simply too big. You'll still end up with many tests, but they'll be smaller and more manageable, covering less ground. This can only be a good thing though.

Testing Legacy Code

Check out Pex. You claim you inherited this code, so this is not actually Test-Driven-Development. You simply want unit tests to cover each aspect. This is a good thing, as any further work will be validated. I've personally not used Pex properly yet, however I was wowed by the video I saw. Essentially it will generate unit tests based on the input, which in this case would be the finite state machine itself. It will generate test cases you will not have enough thought of. Granted this is not TDD, but in this scenario, testing legacy code, it should be ideal.

Once you have your test coverage, you can begin refactoring, or adding new features with the safety of good test coverage to ensure you don't break any existing functionality.

Answer 2

All-Pair Testing

To constraint the amount of combinations to test and to be reasonable assured you have most important combinations covered, you should take a look at all-pair testing.

the reasoning behind all-pairs testing is this: the simplest bugs in a program are generally triggered by a single input parameter. The next simplest category of bugs consists of those dependent on interactions between pairs of parameters, which can be caught with all-pairs testing.1 Bugs involving interactions between three or more parameters are progressively less common2, whilst at the same time being progressively more expensive to find by exhaustive testing, which has as its limit the exhaustive testing of all possible inputs.

Also take a look at a previous answer here (shameless plug) for additional information and links to both all-pair & pict as tool.

Example Pict model file

Given model generates 93 testcases, covering all pairs of input parameters.

#
# This is a PICT  model for testing a complex state machine at work 
#

CurrentState  :0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30
Source        :1,2
Request       :True, False
Type          :True, False
Status        :State1, State2, State3
Handling      :State1, State2, State3
Completed     :True,False

#
# One can add constraints to the model to exclude impossible 
# combinations if needed.
#
# For example:
# IF [Completed]="True" THEN CurrentState>15;
#

#
# This is the PICT output of "pict ComplexStateMachine.pict /s /r1"
#
# Combinations:    515
# Generated tests: 93

Answer 3

I can't think of any easy way to do test an FSM like this with out getting really pedantic and employing proofs, using machine learning techniques, or brute force.

Brute force: Write a something that will generate all the 4320 test cases in some declarative manner with mostly incorrect data. I would recommend putting this in a CSV file and then use something like NUnits parameteric testing to load all the test cases. Now most of these test cases will fail so you will have to update the declarative file manually to be correct and take just a sample of the test cases randomly to fix.

Machine Learning technique: You could employ some Vector machines or MDA algorithms/heuristics to try to learn on the sample you took from what we mentioned above and teach your ML program your FSM. Then run the algorithm on all the 4320 inputs and see where the two disagree.

Answer 4

You might consider investigating Model Based Testing. There are a few tools available to help with test generation in situations like this. I usually recommend MBT.

Answer 5

How many test do you think is needed to "completely" test function sum(int a, int b)? In c# it would be something like 18446744056529682436 tests... Much worse than in your case.

I would suggest following:

1. Test most possible situations, boundary conditions.
2. Test some critical parts of your SUT separately.
3. Add test cases when bugs found by QA or in production.

In this particular case the best way is to test how system switches from one state to onother. Create DSL to test state machine and implement most frequent use cases using it. For Example:

Start
  .UploadDocument("name1")
  .SendDocumentOnReviewTo("user1")
  .Review()
  .RejectWithComment("Not enough details")
  .AssertIsCompleted()

The example of creating simple tests for flows is here: http://slmoloch.blogspot.com/2009/12/design-of-selenium-tests-for-aspnet_09.html

Answer 6

Test based on the requirements. If a certain state is required to move to a certain other state whenever Completed is true, then write a test that automatically cycles through all the combinations of the other inputs (this should just be a couple for loops) to prove that the other inputs are correctly ignored. You should end up with one test for each transition arc, which I'd estimate would be somewhere on the order of 100 or 150 tests, not 4000.