Finite State Machines: How to Enhance Software Testing

Ensuring application reliability is a never-ending quest. Finite state machines (FSMs) offer a solution by modeling system behavior as states and transitions, a useful tool that can help software engineers understand software behavior and design effective test cases. 

This article explores the pros and cons of FSMs via simple examples. We will also make a short comparison between the usefulness and applicability of FSMs and program graphs in software testing.

What Are FSMs?

FSMs are a powerful tool used to model systems that exhibit distinct states and transitions between those states. They are our visual roadmaps for a system's behavior. Here's a breakdown of their core principles:

• An FSM is a directed graph where nodes represent states and edges represent transitions between states.
• Transitions are triggered by events, and actions might occur upon entering or leaving a state.
• Labels on transitions specify the events that trigger them and the actions that occur during the transition.
• FSMs are a simple and visual way to represent systems that react differently to various events.

Let's explore Python code for a simple vending machine and demonstrate how an FSM aids in designing effective test cases.

class VendingMachine:
  def __init__(self):
    self.state = "idle"
    self.inserted_amount = 0
    self.product_selected = None

  def insert_coin(self, amount):
    if self.state == "idle":
      self.inserted_amount += amount
      print(f"Inserted ${amount}. Current amount: ${self.inserted_amount}")
    else:
      print("Machine busy, please wait.")

  def select_product(self, product):
    if self.state == "idle" and self.inserted_amount >= product.price:
      self.state = "product_selected"
      self.product_selected = product
      print(f"Selected {product.name}.")
    else:
      if self.state != "idle":
        print("Please dispense product or return coins first.")
      else:
        print(f"Insufficient funds for {product.name}.")

  def dispense_product(self):
    if self.state == "product_selected":
      print(f"Dispensing {self.selected_product.name}.")
      self.state = "idle"
      self.inserted_amount = 0
      self.product_selected = None
    else:
      print("No product selected.")

  def return_coins(self):
    if self.state == "idle" and self.inserted_amount > 0:
      print(f"Returning ${self.inserted_amount}.")
      self.inserted_amount = 0
    else:
      print("No coins to return.")

# Example products
class Product:
  def __init__(self, name, price):
    self.name = name
    self.price = price

product1 = Product("Soda", 1.00)
product2 = Product("Chips", 0.75)

# Example usage
vending_machine = VendingMachine()
vending_machine.insert_coin(1.00)
vending_machine.select_product(product1)
vending_machine.dispense_product()
vending_machine.insert_coin(0.50)
vending_machine.select_product(product2)
vending_machine.dispense_product()
vending_machine.return_coins()

The code simulates a basic vending machine with functionalities like coin insertion, product selection, dispensing, and coin return. Let's see how an FSM empowers us to create robust test cases.

FSM Design for the Vending Machine

The vending machine's FSM may have four states:

1. Idle: The initial state where the machine awaits user input
2. Coin insertion: State active when the user inserts coins
3. Product selection: State active after a product is selected with sufficient funds
4. Dispensing: State active when the product is dispensed and change (if any) is returned

Transitions and Events

• Idle -> Coin Insertion: Triggered by the insert_coin method
• Coin Insertion -> Idle: Triggered if the user tries to insert coins while not in the "idle" state (error scenario)
• Idle -> Product Selection: Triggered by the select_product method if sufficient funds are available
• Product Selection -> Idle: Triggered if the user selects a product without enough funds or attempts another action while a product is selected
• Product Selection -> Dispensing: Triggered by the dispense_product method
• Dispensing -> Idle: Final state reached after dispensing the product and returning change

Test Case Generation With FSM

By analyzing the FSM, we can design comprehensive test cases to thoroughly test the program:

1. Valid Coin Insertion and Product Selection

• Insert various coin denominations (valid and invalid amounts).
• Select products with exact, sufficient, and insufficient funds.
• Verify the machine transitions to the correct states based on inserted amounts and selections.

Example Test Case:

1. Start in "Idle" state.
2. Insert $1.00 (transition to "Coin Insertion").
3. Select "Soda" (transition to "Product Selection" if funds are sufficient, otherwise remain in "Idle").
4. Verify the message: "Selected Soda."
5. Insert $0.25 (transition to "Coin Insertion").
6. Select "Chips" (transition to "Product Selection" if the total amount is sufficient; otherwise, remain in "Product Selection").
7. Verify the message: "Dispensing Chips." or "Insufficient funds for Chips." (depending on the previous coin insertion).

Expected behavior: The machine should dispense "Chips" if the total amount is $1.25 (enough for product and change) and return the remaining $0.25. If the total amount is still insufficient, it should remain in the "Product Selection" state.

2. Edge Case Testing

• Insert coins while in "Product Selection" or "Dispensing" state (unexpected behavior).
• Try to select a product before inserting any coins.
• Attempt to dispense the product without selecting one.
• Return coins when no coins are inserted.
• Verify the machine handles these scenarios gracefully and provides appropriate messages or prevents invalid actions.

Example Test Case:

1. Start in "Idle" state.
2. Insert $1.00 (transition to "Coin Insertion").
3. Select "Soda" (transition to "Product Selection").
4. Try to insert another coin (should not allow in "Product Selection").
5. Verify the message: "Machine busy, please wait."

Expected behavior: The machine should not accept additional coins while a product is selected.

3. State Transition Testing

• Verify the program transitions between states correctly based on user actions (inserting coins, selecting products, dispensing, returning coins).
• Use the FSM as a reference to track the expected state transitions throughout different test cases.

Benefits of FSMs

FSMs provide a clear understanding of the expected system behavior for different events. They aid in defining and documenting requirements. By mapping the FSM, testers can efficiently design test cases that cover all possible transitions and ensure the system reacts appropriately to various scenarios. FSMs can help identify inconsistencies or missing logic in the early design stages. This prevents costly bugs later in the development process. They act as a bridge between technical and non-technical stakeholders, facilitating better communication and collaboration during testing. But let's see some examples:

Clear Requirements Specification

A tech startup was developing a revolutionary smart building management system. Their latest challenge was to build an app that controls a sophisticated elevator. The team, led by an enthusiastic project manager, Sofia, was facing a communication breakdown.

"The engineers keep changing the app's behavior!" Sofia exclaimed during a team meeting. "One minute it prioritizes express calls, the next it services all floors. Clients are confused, and we're behind schedule."

David, the lead software engineer, scratched his head. "We all understand the core functionality, but translating those requirements into code is proving tricky."

Aisha, the new UI/UX designer, piped up, "Maybe we need a more visual way to represent the elevator's behavior. Something everyone can understand from a glance."

Sofia pulled out a whiteboard. "What if we create an FSM for our app?"

The team huddled around as Sofia sketched a diagram. The FSM depicted the elevator's different states (Idle, Moving Up, Moving Down, Door Open) and the events (button press, floor sensor activation) that triggered transitions between them. It also defined clear outputs (door opening, floor announcement) for each state.

"This is amazing!" David exclaimed. "It clarifies the decision-making process for the elevator's control system."

Aisha smiled. "This FSM can guide the user interface design as well. We can show users the elevator's current state and expected behavior based on their input."

Over the next few days, the team refined the FSM, ensuring all user scenarios and edge cases were accounted for. They used the FSM as a reference point for coding, UI design, and even client presentations.

The results were impressive. Their app functioned flawlessly, prioritizing express calls during peak hours and servicing all floors efficiently. The clear user interface, based on the FSM, kept everyone informed of the elevator's current state.

"The FSM was a game-changer," Sofia declared during a successful client demo. "It provided a shared understanding of the system's behavior, leading to smooth development and a happy client."

The success of the app served as a testament to the power of FSMs. By providing a clear visual representation of a system's behavior, FSMs bridge communication gaps, ensure well-defined requirements, and can lead to the development of robust and user-friendly software.

Test Case Generation

Another startup was working on an AI-powered security gate for restricted areas. The gate-controlled access is based on employee ID badges and clearance levels. However, the testing phase became a frustrating maze of random scenarios.

"These bugs are popping up everywhere!" groaned Mike, the lead QA tester. "One minute the gate opens for a valid ID, the next it denies access for no reason."

Lisa, the lead developer, frowned. "We've written tons of test cases, but these glitches keep slipping through."

New to the team, Alex, a recent computer science graduate, listened intently. "Have you guys considered using an FSM?"

Mike asked, "Finite State Machine? What's that?"

Alex explained how an FSM could visually represent the app's behavior. It would show various states (Idle, Verifying ID, Access Granted, Access Denied) and the events (badge swipe, clearance check) triggering transitions.

"By mapping the FSM," Alex continued, "we can systematically design test cases that cover all possible transitions and ensure that our app reacts appropriately in each scenario."

The team decided to give it a try. Together, they sketched an FSM on a whiteboard. It detailed all possible badge swipes (valid ID, invalid ID, revoked ID) and corresponding state transitions and outputs (gate opening, access denied messages, security alerts).

Based on the FSM, Mike and Alex designed comprehensive test cases. They tested valid access for different clearance levels, attempted access with invalid badges, and even simulated revoked IDs. They also included edge cases, like simultaneous badge swipes or network disruptions during the verification process.

The results were remarkable. The FSM helped them identify and fix bugs they hadn't anticipated before. For instance, they discovered a logic error that caused the app to grant access even when the ID was revoked.

"This FSM is a lifesaver!" Mike exclaimed. "It's like a roadmap that ensures we test every possible pathway through the system."

Lisa nodded, relieved. "With these comprehensive tests, we can finally be confident about our app's reliability."

The team learned a valuable lesson: FSMs aren't just theoretical tools, but powerful allies in the software testing battleground.

Early Error Detection

Another development team was building a VoIP app. It promised crystal-clear voice calls over the internet, but the development process had become a cacophony of frustration.

"The call quality keeps dropping!" Mary, the lead developer, grimaced. "One minute the audio is clear, the next it's a mess."

Jason, the stressed project manager, pinched the bridge of his nose. "We've been fixing bugs after each test run, but it feels like a game of whack-a-mole with these audio issues."

Anna, the new UI/UX designer, suggested, "Maybe we need a more structured approach to visualizing how our VoIP app should behave.  Something that exposes potential glitches before coding begins."

Mark remembered a concept from his first-year computer science degree. "What about a Finite State Machine (FSM)?"

The team gathered around the whiteboard as Mark sketched a diagram. The FSM depicted the app's various states (Idle, Initiating Call, Connected, In-Call) and the user actions (dialing, answering, hanging up) triggering transitions. It also defined expected outputs (ringing tones, voice connection, call-ended messages) for each state.

"This is amazing!" Anna exclaimed. "By mapping out the flow, we can identify potential weaknesses in the logic before they cause audio problems down the line."

Over the next few days, the team painstakingly detailed the FSM. They identified a crucial gap in the logic early on. The initial design didn't account for varying internet connection strengths. This could explain the erratic call quality that Mary described.

With the FSM as a guide, Alex, the network engineer, refined the app's ability to adapt to different bandwidths. The app dynamically adjusted audio compression levels based on the user's internet speed. This ensured a smoother call experience even with fluctuating connections.

The FSM unveiled another potential issue: the lack of a clear "call dropped" state. This could lead to confusion for users if the connection abruptly ended without any notification. Based on this insight, the team designed an informative "call ended" message triggered by unexpected connection loss.

By launch day, the VoIP app performed flawlessly. The FSM helped them catch critical glitches in the early stages, preventing user frustration and potential churn.

Improved Communication

Another development team was building a mobile banking app. It promised cutting-edge security and user-friendly features. However, communication between the development team and stakeholders had become a financial nightmare of misunderstandings.

"Marketing wants a flashy login animation," Nick, the lead developer, sighed. "But it might conflict with the two-factor authentication process."

Joe, the project manager, rubbed his temples. "And the CEO keeps asking about facial recognition, but it's not in the current design."

John, the intern brimming with enthusiasm, chimed in, "Have you considered using a Finite State Machine (FSM) to model our app?"

John explained how an FSM could visually represent the app's flow. It would show different states (Idle, Login, Account Selection, Transaction Confirmation) with user actions (entering credentials, selecting accounts, confirming transfers) triggering transitions.

"The beauty of an FSM," John continued, "is that it provides a clear and concise picture for everyone involved. Technical and non-technical stakeholders can readily understand the app's intended behavior."

The team decided to give it a shot. Together, they sketched an FSM for the app, detailing every step of the user journey. This included the two-factor authentication process and its interaction with the login animation. It was now clear to marketing that a flashy animation might disrupt security protocols.

The FSM became a communication bridge. Joe presented it to the CEO, who easily grasped the limitations of facial recognition integration in the current design phase. The FSM helped prioritize features and ensure everyone was on the same page.

Testers also benefited immensely. The FSM served as a roadmap, guiding them through various user scenarios and potential edge cases. They could systematically test each state transition and identify inconsistencies in the app's behavior.

By launch time, the app functioned flawlessly. The FSM facilitated clear communication, leading to a well-designed and secure banking app. Stakeholders were happy, the development team was relieved, and John, the hero with his FSM knowledge, became a valuable asset to the team.

The team's key takeaway: FSMs are not just for internal development. They can bridge communication gaps and ensure smooth collaboration between technical and non-technical stakeholders throughout the software development lifecycle.

FSMs vs. Program Graphs: A Comparison

While both FSMs and program graphs are valuable tools for software testing, they differ in their scope and level of detail. To understand how both tools can be related, the following analogy may help. Assume we are exploring a city. An FSM would be like a map with labeled districts (states) and connecting roads (transitions). A program graph would be like a detailed subway map, depicting every station (code blocks), tunnels (control flow), and potential transfers (decision points).

FSMs: What They Are Suitable for Testing

• State-driven systems: User interfaces, network protocols, and apps with a clear mapping between states and events
• Functional testing: Verifying system behavior based on user inputs and expected outputs in different states
• Regression testing: Ensuring changes haven't affected existing state transitions and system functionality

FSM Weaknesses

• Limited scope: FSMs may struggle with complex systems that exhibit continuous behavior or have complex interactions between states.
• State explosion: As the system complexity increases, the number of states and transitions can grow exponentially, making the FSM cumbersome and difficult to manage.
• Limited error handling: FSMs don't explicitly represent error states or handling mechanisms, which might require separate testing approaches.

Program Graphs: What They Are Suitable for Testing

• Software with complex logic: Code with loops, branches, functions, and intricate interactions between different parts of the program
• Integration testing: Verifying how different modules or components interact with each other
• Unit testing: Focusing on specific code functions and ensuring they execute as expected under various conditions

Program Graphs' Weaknesses

• Complexity: Creating and interpreting program graphs can be challenging for testers unfamiliar with code structure and control flow.
• Abstract view: Program graphs offer a less intuitive representation for non-technical stakeholders compared to FSMs.
• State abstraction: Complex state changes might not be explicitly represented in program graphs, requiring additional effort to map them back to the system's states.

Choosing the Right Tool

• For state-based systems with clear events and transitions, FSMs are a great starting point, offering simplicity and ease of use.
• For more complex systems or those with intricate control flow logic, program graphs provide a more detailed and comprehensive view, enabling thorough testing.
• In many cases, a combination of FSMs and program graphs might be the most effective approach. FSMs can provide a high-level overview of system behavior, and program graphs can delve deeper into specific areas of code complexity.

By understanding the strengths and limitations of each approach, you can choose the best tool for your specific software testing needs.

Wrapping Up

FSMs are a useful tool for software development to represent a system's behavior. They excel at clearly defining requirements, ensuring all parties involved understand the expected functionality. FSMs also guide test case generation, making sure all possible scenarios are explored. Most importantly, FSMs help catch inconsistencies and missing logic early in the development phase, preventing costly bugs from appearing later. Understanding their pros and cons can help us improve our testing efforts. After all, we can use FSMs alone or in parallel with other tools like program graphs.