Short Tutorial on Testing of Finite State Machines

Testing, Optimization, and GamesMihalis YannakakisColumbia UniversityThe Software Reliability ProblemSystems are becoming larger, more complex,distributed,…⇒ harder to create, get them right, test them …• Large part of the cost of software development goes to testingProblem: Improve cost, time, reliabilityFocus: Behavior/Control of SystemsReactive/Event-driven Systems– Switching Software– Communication Protocols– Controllers–….Model: State Machines of various typesFinite State Machine for PhoneStates: Idle, Dial tone, ….Inputs: off-hook, on-hook, digit, …Outputs: sound dial tone, loud beep, play message,….TestingTest SystemTest GeneratorSpec.scenarios(eg. Model,CriteriaProperty)Does the System satisfy the specification?(conform to the model ? satisfy the property?)Different Views of Testing• Testing as an Optimization problemOptimize the use of testing resources to achieve maximum fault coverage• Testing as a GameTester vs. System Who wins? Best strategy?• Testing as a learning problemOutline• Testing framework, issues• Conformance Testing – Deterministic FSM’s– Nondeterministic FSM’s• Testing Properties• Optimum Coverage problems– FSM’s, graph models– Extended FSM’s– Hierarchical FSM’sFinite State Machines2as1baab bs5bbaas3s4Moore machine•States: s1, …., s5•Inputs: a, b•Outputs: red, green - function of the state•Transitions: for every state and inputDeterministic FSM: one transition for every ...