SWE 637: Graph Coverage for Design Elements

SWE 637: Graph Coverage for Design Elements

Introduction to Software Testing (2nd edition) Chapter 7.5 Graph Coverage for Specifications Paul Ammann & Jeff Offutt http://www.cs.gmu.edu/~offutt/software test/ Design Specifications A design specification describes aspects of what behavior software should exhibit A design specification may or may not reflect the implementation More accurately the implementation may not exactly reflect the spec Design specifications are often called models of the software Two types of descriptions are used in this chapter 1. Sequencing constraints on class methods 2. State behavior descriptions of software

Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 2 Sequencing Constraints Sequencing constraints are rules that impose constraints on the order in which methods may be called They can be encoded as preconditions or other specifications Section 7.4 said that classes often have methods that Class stackdo not call each other ??? public void push (Object o) public Object pop ( ) public boolean isEmpty ( ) push pop isEmpty Tests can be created for these classes as sequences of method calls

Sequencing constraints give an easy and effective way to choose which sequences to use Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 3 Sequencing Constraints Overview Sequencing constraints might be Expressed explicitly Expressed implicitly Not expressed at all Testers should derive them if they do not exist Look at existing design documents Look at requirements documents Ask the developers Last choice : Look at the implementation If they dont exist, expect to find more faults ! Share with designers before designing tests Sequencing constraints do not capture all behavior Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 4 Queue Example

public int deQueue() { // Pre: At least one element must be on the queue. public enQueue (int e) { // Post: e is on the end of the queue. Sequencing constraints are implicitly embedded in the pre and postconditions enQueue () must be called before deQueue () Does not include the requirement that we must have at least as many enQueue () calls as deQueue () calls Can be handled by state behavior techniques Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 5 File ADT Example class FileADT has three methods: open (String fName) // Opens file with name fName close () // Closes the file and makes it unavailable write (String textLine) // Writes a line of text to the file Client that uses FileADT Valid sequencing constraints on

FileADT: 1. An open (f) must be executed before every write (t) 2. An open (f) must be executed before every close () 3. A write (f) may not be executed after a close () unless there is an open (f) in between 4. A write (t) should be executed before every close () Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 1 open (f) 3 write(t2 ) 4 6 5 write (t) close () 6

Static Checking Is there a path that violates any of the sequencing constraints ? Is there a path to a write() 1 open (f) 3 write(t2 ) 4 6 5 write (t) close () Introduction to Software Testing, edition 2 (Ch 07) that does not go through an open() ? Is there a path to a close() that does not go through an open() ? Is there a path from a close() to a write()? Is there a path from an open()

to a close() that does not go [ 1, 3, 4, 6 ] ADT use through a write() ? (writeanomaly! clear path) Ammann & Offutt 7 Static Checking Consider the following graph : 1 2 open (f) 3 write (t) 4 close () 8 5 6 write (t)

7 close () [ 7, 3, 4 ] close () before write () ! Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 8 Generating Test Requirements [ 1, 3, 4, 6 ] ADT use anomaly! 1 write 2 (t) open (f) 3 4 6 5 write (t) close ()

But it is possible that the logic of the program does not allow the pair of edges [1, 3, 4] That is the loop body must be taken at least once Determining this is undecidable so static methods are not enough Use the sequencing constraints to generate test requirements The goal is to violate every sequencing constraint Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 9 Test Requirements for FileADT 1. 2. 3. 4. Apply to all programs that use FileADT

Cover every path from the start node to every node that contains a write() such that the path does not go through a node containing an open() Cover every path from the start node to every node that contains a close() such that the path does not go through a node containing an open() Cover every path from every node that contains a close() to every node that contains a write() Cover every path from every node that contains an open() to every node that contains a close() such that the path does not go through a node containing a write() If program is correct, all test requirements will be infeasible Any tests created will almost definitely find faults Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 10 Testing State Behavior A finite state machine (FSM) is a graph that describes how software variables are modified during execution Nodes : States, representing sets of values for key variables Edges : Transitions, possible switch changes in the

up state Off On switch down Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 11 Finite State MachineTwo Variables Tropical Depression Tropical Storm circulation = yes windspeed < 39mph circulation = yes windspeed = 39..73 mph Something Else circulation = no Major Hurricane Hurricane

circulation = yes windspeed >= 110 mph circulation = yes windspeed 74..109 mph Other variables may exist but not be part of state Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 12 Finite State Machines are Common FSMs can accurately model many kinds of software Embedded and control software (think electronic gadgets) Abstract data types Compilers and operating systems Web applications Creating FSMs can help find software problems Numerous languages for expressing FSMs UML statecharts Automata State tables (SCR) Petri nets Limitation : FSMs are not always practical for Introduction to Software Testing, edition 2 (Ch 07)

Ammann & Offutt 13 Annotations on FSMs FSMs can be annotated with different types of actions Actions on transitions Entry actions to nodes Exit actions on nodes Actions can express changes to variables or conditions on variables These slides use the basics: Preconditions (guards) : conditions that must be true for transitions to be taken Triggering events : changes to variables that cause transitions to be taken This is close to the UML Statecharts, but not exactly the same Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 14 Example Annotations

Closed open elevator door Open pre: elevSpeed = 0 trigger: openButton = pressed Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 15 Covering FSMs Node coverage : execute every state (state coverage) Edge coverage : execute every transition (transition coverage) Edge-pair coverage : execute every pair of transitions (transition-pair) Data flow: Nodes often do not include defs or uses of variables Defs of variables in triggers are used immediately (the next state) Defs and uses are usually computed for guards, or

states are extended FSMs typically only model a subset of the variables Generating FSMs is often harder than covering Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 16 Deriving FSMs With some projects, an FSM (such as a statechart) was created during design Tester should check to see if the FSM is still current with respect to the implementation If not, it is very helpful for the tester to derive the FSM Strategies for deriving FSMs from a program: 1. Combining control flow graphs (wrong) 2. Using the software structure (wrong) 3. Modeling state variables Example based on a digital watch Class Watch uses class Time Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt

17 Class Watch class Watch // Constant values for the button (inputs) private static final int NEXT = 0; private static final int UP = 1; private static final int DOWN = 2; // Constant values for the state private static final int TIME = 5; private static final int STOPWATCH = 6; private static final int ALARM = 7; // Primary state variable private int mode = TIME; // Three separate times, one for each state private Time watch, stopwatch, alarm; class Time ( inner class ) private int hour = 0; private int minute = 0; public void changeTime (int button) public String toString () public Watch () // Constructor public void doTransition (int button) // Handles inputs public String toString () // Converts values Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt

18 // Takes the appropriate transition when a button is pushed. public void doTransition (int button) { switch ( mode ) { case TIME: if (button == NEXT) mode = STOPWATCH; else watch.changeTime (button); break; case STOPWATCH: if (button == NEXT) mode = ALARM; else stopwatch.changeTime (button); break; case ALARM: if (button == NEXT) mode = TIME; else alarm.changeTime (button); break; default: break; } } // end doTransition() Introduction to Software Testing, edition 2 (Ch 07) // Increases or decreases the time. // Rolls around when necessary.

public void changeTime (int button) { if (button == UP) { minute += 1; if (minute >= 60) { minute = 0; hour += 1; if (hour > 12) hour = 1; } } else if (button == DOWN) { minute -= 1; if (minute < 0) { minute = 59; hour -= 1; if (hour <= 0) hour = 12; } } } // end changeTime() Ammann & Offutt 19 1. Combining Control Flow Graphs

The first instinct for inexperienced developers is to draw CFGs and link them together This is really not an FSM Several problems Methods must return to correct callsitesimplicit nondeterminism Implementation must be available before graph can be built This graph does not scale up Watch example Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 20 CFGs for Watch changeTime () doTransition () 1 1 2 2 5

3 6 7 4 8 9 3 4 10 5 6 7 8 11 12 9 13 10 12

14 Introduction to Software Testing, edition 2 (Ch 07) 11 Ammann & Offutt 21 2. Using the Software Structure A more experienced programmer may map methods to states These are really not states Problems Subjectivedifferent testers get different graphs Requires in-depth knowledge of implementation Detailed design must be present Watch example Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 22 Software Structure for Watch inMain ??? Should inChangeTime transit back to inMain???

button==UP / change hour, minute button button==NEXT / change mode button==UP or button==DOWN inDoTransition inChangeTime ??? Not clear what triggers this button==DOWN / change hour, minute Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 23 3. Modeling State Variables More mechanical State variables are usually defined early First identify all state variables, then choose which are relevant In theory, every combination of values for the state variables defines a different state

In practice, we must identify ranges, or sets of values, that are all in one state Some states may not be feasible Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 24 State Variables in Watch Constants NEXT, UP, DOWN Not relevant, TIME, STOPWATCH, ALARMreally just values Non-constant variables in class Watch int mode (values: TIME, STOPWATCH, ALARM) Time watch, stopwatch, alarm Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 25 State Variables in Time Non-constant variables in class Time int hour (values: 1..12) 12 X 60 values is 720 states int minute (values: 0 .. 59) Clearly, that is too

Combine values into ranges of similar manyvalues : hour : 1.. 11, 12 Clumsy ... Not sequential minute : 0, 1.. 59 lets combine hour and minute Four states : (1..11, 0); (12, 0); (1..11, 1.. 59); (12, 1 .. 59) Time : 12:00, 12:01..12:59, 01:00These .. 11:59 require Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt lots of thought and semantic domain knowledge of the program 26 Hierarchical FSMs One FSM is contained within the other Class Watch uses class Time How can we model two classesone

that uses another? S2 S1 S3 a b Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt c 27 Watch / Time Hierarchical FSM mode = TIME t x e n do wn up up up

up wn do h:m= 12:00 up down down mode = STOPWATCH up up up h:m= h:m= down 1:00 .. 11:59 12:01 .. 12:59 down down Introduction to Software Testing, edition 2 (Ch 07) h:m=

12:00 next up do wn do wn up mode = ALARM up up up wn do up wn do h:m= 12:00 next h:m=

h:m= down 1:00 .. 11:59 12:01 .. 12:59 up h:m= h:m= down 1:00 .. 11:59 12:01 .. 12:59 down Ammann & Offutt down 28 SummaryTradeoffs in Applying Graph Coverage Criteria to FSMs Two advantages 1. Tests can be designed before implementation 2. Analyzing FSMs is much easier than analyzing source Three disadvantages 1. Some implementation decisions are not modeled in the FSM 2. There is some variation in the results because of

the subjective nature of deriving FSMs 3. Tests have to be mapped to actual inputs to the program the names that appear in the FSM may not be the same as the names in the program Introduction to Software Testing, edition 2 (Ch 07) Ammann & Offutt 29

Recently Viewed Presentations

  • Le mariage et l&#x27;union civile

    Le mariage et l'union civile

    Le mariage et l'union civile www.contratquebec.com * www.contratquebec.com * Les effets obligatoires du mariage (régime primaire) Les droits et devoirs des époux La résidence familiale Le patrimoine familial La prestation compensatoire www.contratquebec.com * Les droits et devoirs des époux Les...
  • Diapositiva 1

    Diapositiva 1

    A) DEFINICIÓN: ¿Cómo se define? 1º Etimología 2º Paráfrasis 3º Estructura de la definición ( concepto - ubicación en una clase, propiedades del concepto ) 4º Énfasis en determinados aspectos del concepto: función, composición, propiedades, localización. 5º Inversión de la...
  • Kentucky Appalachian Regional Intermodal Airpark

    Kentucky Appalachian Regional Intermodal Airpark

    Freight Corridor Study PROJECT OVERVIEW FHWA Talking Freight Seminar December 15, 2004 Dilara Rodriguez Project Manager, CALTRANS
  • Activity 1: 1950s America Word List Key Word

    Activity 1: 1950s America Word List Key Word

    'Oh God,' said a woman, 'the niggers are in school.' group of six girls, dressed in skirts and sweaters, hair in pony tails, started to shriek and wailed. 'The niggers are in our school,' they howled hysterically ….
  • Under Pressure

    Under Pressure

    The formula is: P = F. A. P= Pressure (Pa) F= Force (N) A= Exposed Surface Area (m2) Pressure Exerted by Fluids. ... manometer. Depth gauge. A depth of 1m has the same pressure whether you're in a pool or...
  • What graduate school is about: goals and survival skills

    What graduate school is about: goals and survival skills

    SIGNEWGRAD Fall 2011 Professor Liao - 424 Smith Hall - [email protected] Gore 114, Mondays - 5:00 to 6:15PM What is SIGNEWGRAD all about? Presentation and discussion
  • Chapter 7: Access Control Lists

    Chapter 7: Access Control Lists

    Create an IPv4 or IPv6 address strategy that is hierarchical. ... Although the configuring EIGRP is simple, the underlying features and options of EIGRP are extensive and robust. OSPF supports a two-layer hierarchical design, referred to as multiarea OSPF.
  • NC LANDMARKS Carowinds  A theme park sharing a

    NC LANDMARKS Carowinds A theme park sharing a

    Battle of Guilford Courthouse - Just over an hour away near Greensboro, this massive one day battle of the Revolutionary War was a turning point to "American" victory against the British in 1781. Though the Americans "lost" the battle, the...