Foundations of Software Testing Learning Objectives Errors
Contents
1. node is labeled with the state it represents Each directed O Qx X gt Y is an output function edge in a state diagram connects two states Each edge is labeled i o where i denotes an input symbol that belongs to the input In some variants of FSM more than one state could be alphabet X and o denotes an output symbol that belongs to the specified as an initial state Also sometimes it is output alphabet O iis also known as the input portion of the convenient to add FG Q as a set of final or accepting edge and o its output portion states while specifying an FSM Aditya P Mathur 2005 Aditya P Mathur 2005 Properties of FSM Properties of FSM Equivalence Completely specified An FSM M is said to be completely V equivalence Let M X Y Q m p T O1 and M X Y specified if from each state in M there exists a transition for Q M T O2 be two FSMs Let V denote a set of non each input symbol empty strings over the input alphabet X i e VE X Strongly connected An FSM M 1s considered strongly Let q and qj i j be the states of machines M and M connected if for each pair of states q q there exists an input respectively q and qj are considered V equivalent if O q sequence that takes M from state q to qj s O q s for all s in V Aditya P Mathur 2005 Aditya P Mathur 2005 p Properties of FSM Distinguishable Stated differently states q and qj are considered V equivalent if M and M whe2. observes the behavior In the second step one analyzes the observed behavior to check if it is correct or not Both these steps could be quite complex for large commercial programs The entity that performs the task of checking the correctness of the observed behavior is known as an oracle Aditya P Mathur 2005 Oracle Programs Oracles can also be programs designed to check the behavior of other programs For example one might use a matrix multiplication program to check if a matrix inversion program has produced the correct output In this case the matrix inversion program inverts a given matrix A and generates B as the output matrix Aditya P Mathur 2005 Oracle Construction Construction of automated oracles such as the one to check a matrix multiplication program or a sort program requires the determination of input output relationship In general the construction of automated oracles is a complex undertaking Aditya P Mathur 2005 Testing and verification contd Testing is not a perfect technique in that a program might contain errors despite the success of a set of tests Verification might appear to be perfect technique as it promises to verify that a program is free from errors However the person who verified a program might have made mistake in the verification process there might be an incorrect assumption on the input conditions incorrect assumptions might be made regarding the co
3. Foundations of Software Testing Chapter 1 Preliminaries Aditya P Mathur Purdue University These slides are copyrighted They are for use with the Foundations of Software Testing book by Aditya Mathur Please use the slides but do not remove the copyright notice Last update September 3 2007 Learning Objectives Errors Testing debugging test process CFG correctness reliability oracles Finite state machines Testing techniques Aditya P Mathur 2005 Errors Errors are a part of our daily life Humans make errors in their thoughts actions and in the products that might result from their actions Errors occur wherever humans are involved in taking actions and making decisions These fundamental facts of human existence make testing an essential Aditya P Mathur 2005 activity Error faults failures Errors Examples 4 O ee il Spoken He has a garage for repairing foreign cars Heard He has a garage for repairing falling cars Incorrect antibiotic prescribed Incorrect note played Incorrect algorithm for matrix inversion Operator fails to recognize that a relief valve is stuck open Operator used correct operator gt Identifier used newline correct identifier nextline Expression used a A b V c correct expression A 6 Vv c Data conversion from 64 bit floating point to 16 bit integer not protected resulting in a software exception Spoken waple maln
4. arate lines with a carriage return typed in after each number The requirement as stated above fails to provide an answer to this question Aditya P Mathur 2005 Aditya P Mathur 2005 Input domain Input space Input domain Continued Modified Requirement 2 It is required to write a program that inputs a sequence of integers and outputs the integers in this sequence sorted in either ascending or descending order The order of the output sequence is determined by an input request character which should be A when an ascending sequence is desired and D otherwise The set of all possible inputs to a program P is known as the input domain or input space of P Using Requirement 1 above we find the input domain of max to be the set of all pairs of integers where each element in the pair integers is in the range 32 768 till 32 767 While providing input to the program the request character is input first followed by the sequence of integers to be sorted the sequence is terminated with a period Aditya P Mathur 2005 Aditya P Mathur 2005 Input domain Continued Based on the above modified requirement the input domain for sort is a set of pairs The first element of the pair is a character The second element of the pair is a sequence of zero or more integers ending with a period Aditya P Mathur 2005 Correctness vs Reliability Though correctness of a program is desirable it is almost never the o
5. ase Aditya P Mathur 2005 J C4 Artifact under test Characteristics Application component Client and server Compiler Design Code Database system OO software Operating system Real time software Requirements Software Web service Aditya P Mathur 2005 Technique Unit testing Integration testing System testing Regression testing Beta testing Technique Component testing Client server testing Compiler testing Design testing Code testing Transaction flow testing OO testing Operating system testing Real time testing Requirement testing Software testing Web service testing C3 Goal of specific testing activity Goal Advertised features Security Invalid inputs Vulnerabilities Errors in GUI Operational correctness Reliability assessment Resistance to penetration System performance Customer acceptability Business compatibility Peripherals compatibility Aditya P Mathur 2005 Technique Functional testing Security testing Robustness testing Vulnerability testing GUI testing Operational testing Reliability testing Penetration testing Performance testing Acceptance testing Compatibility testing Configuration testing Example Capture plaback Event sequence graphs Complete Interaction Sequence Transactional flow Stress testing Interface testing Installation testing 21
6. bjective of testing To establish correctness via testing would imply testing a program on all elements in the input domain In most cases that are encountered in practice this is impossible to accomplish Thus correctness is established via mathematical proofs of programs Aditya P Mathur 2005 Valid Invalid Inputs The modified requirement for sort mentions that the request characters can be A and D but fails to answer the question What if the user types a different character When using sort it is certainly possible for the user to type a character other than A and D Any character other than A and D is considered as invalid input to sort The requirement for sort does not specify what action it should take when an invalid input is encountered Aditya P Mathur 2005 Correctness and Testing While correctness attempts to establish that the program is error free testing attempts to find if there are any errors in it Thus testing does not demonstrate that a program is error free Testing debugging and the error removal processes together increase our confidence in the correct functioning of the program under test Aditya P Mathur 2005 4 Software reliability two definitions 4 Operational profile Software reliability ANSI IEEE Std 729 1983 is the An operational profile is a numerical description of how a probability of failure free operation of software over a program is used
7. ere exist techniques for usability testing Psychology plays an important role in the design of techniques for usability testing Performance refers to the time the application takes to perform a requested task It is considered as a non functional requirement It is specified in terms such as This task must be performed at the rate of X units of activity in one second on a machine running at speed Y having Z gigabytes of memory Aditya P Mathur 2005 Requirements behavior correctness Requirements leading to two different programs Requirement 1 It is required to write a program that inputs two integers and outputs the maximum of these Requirement 2 It is required to write a program that inputs a sequence of integers and outputs the sorted version of this sequence Aditya P Mathur 2005 Requirements Incompleteness Requirements Ambiguity Suppose that program max is developed to satisfy Requirement 1 The expected output of max when the input integers are 13 and 19 can be easily determined to be 19 Requirement 2 is ambiguous It is not clear whether the input sequence is to sorted in ascending or in descending order The behavior of sort program written to satisfy this requirement will l l depend on the decision taken by the programmer while writing Suppose now that the tester wants to know if the two integers are to s rt be input to the program on one line followed by a carriage return or on two sep
8. et e A language consisting only of one string of length zero 00 11 0101 A language containing three strings Aditya P Mathur 2005 Regular expressions contd If r is a regular expression that denotes the set L then r is a regular expression that denotes the set obtained by concatenating L with itself one or more times also written as L Also r known as the Kleene closure ofr is a regular expression If r denotes the set L then r denotes the set e U L If rl and r2 are regular expressions that denote respectively sets L1 and L2 then rl r2 is also a regular expression that denotes the set LI UL2 Aditya P Mathur 2005 Regular expressions Given a finite alphabet X the following are regular expressions over X If a belongs to X then a is a regular expression that denotes the set fa Let rl and r2 be two regular expressions over the alphabet X that denote respectively sets L1 and L2 Then r1 r2 is a regular expression that denotes the set L1 L2 Aditya P Mathur 2005 16 Embedded systems Many real life devices have computers embedded in them For example an automobile has several embedded computers to perform various tasks engine control being one example Another example is a computer inside a toy for processing inputs and generating audible and visual responses Such devices are also known as embedded systems An embedded system can be as simple as a child s musical keyboa
9. given time interval and under given conditions Consider a sort program which on any given execution allows any one of two types of input sequences Sample operational profiles for sort follow Software reliability is the probability of failure free operation of software in its intended environment Aditya P Mathur 2005 Aditya P Mathur 2005 4 Operational profile 4 Operational profile Operational profile 1 Operational profile 2 Sequence Probability l i i Sequence Probability Numbers only 0 9 Numbers only 0 1 Alphanumeric strings 0 1 Alphanumeric strings 0 9 Aditya P Mathur 2005 Aditya P Mathur 2005 Testing and debugging Testing is the process of determining if a program has any errors When testing reveals an error the process used to determine the cause of this error and to remove it is known as debugging Aditya P Mathur 2005 A test debug cycle Test plan A test cycle is often guided by a test plan Example The sort program is to be tested to meet the requirements given earlier Specifically the following needs to be done e Execute sort on at least two input sequences one with A and the other with D as request characters Aditya P Mathur 2005 Aditya P Mathur 2005 Test plan contd Execute the program on an empty input sequence Test the program for robustness against erroneous inputs such as R typed in as the request character All failures
10. is and n are nodes belonging to N and 0 lt i lt k if ej n n and e n n then n ny j Aditya P Mathur 2005 12 Paths sample paths through the exponentiation flow graph Two feasible and complete paths p Start 1 2 4 5 6 5 7 9 End p Start 1 3 4 5 6 5 7 9 End Specified unambiguously using edges p17 Start 1 1 2 2 4 4 3 5 6 6 5 5 7 7 9 9 End Bold edges complete path Dashed edges subpath Aditya P Mathur 2005 4 Number of paths There can be many distinct paths through a program A program with no condition contains exactly one path that begins at node Start and terminates at node End Each additional condition in the program can increases the number of distinct paths by at least one Depending on their location conditions can have a multiplicative effect on the number of paths Aditya P Mathur 2005 4 Paths feasible paths A path p through a flow graph for program P is considered feasible if there exists at least one test case which when input to P causes p to be traversed p Start 1 3 4 2 9 6 gt I 8 a End p Start 1 1 2 4 5 5 6 5 4 5 7 9 End Aditya P Mathur 2005 13 Test generation Any form of test generation uses a source document In the most informal of test methods the source document resides in the mind of the tester who generates tests based on a knowledge
11. le then they are said to be k equivalent Aditya P Mathur 2005 Aditya P Mathur 2005 Example Completely specified machine d ADD num d d ERROR d INIT num d OUT num d ERROR Aditya P Mathur 2005 Types of testing One possible classification is based on the following four classifiers C1 Source of test generation C2 Lifecycle phase in which testing takes place C3 Goal of a specific testing activity C4 Characteristics of the artifact under test Aditya P Mathur 2005 C1 Source of test generation Sees Artifact Requirements informal Requirements and code Formal model Graphical or mathematical specification Aditya P Mathur 2005 Component interface Technique Black box White box Black box and White box Model based Specification Interface testing Example Ad hoc testing Boundary value analysis Category partition Classification trees Cause effect graphs Equivalence partitioning Partition testing Predicate testing Random testing Adequacy assessment Coverage testing Data flow testing Domain testing Mutation testing Path testing Structural testing Test minimization using coverage Statechart testing FSM testing Pairwise testing Syntax testing Interface mutation Pairwise testing 20 C2 Lifecycle phase in which testing takes place Phase Coding Integration System integration Maintenance Post system pre rele
12. mponents that interface with the program and SO on Verified and published programs have been shown Aditya P Mathur 2005 to be incorrect Testing and verification Program verification aims at proving the correctness of programs by showing that it contains no errors This is very different from testing that aims at uncovering errors in a program Program verification and testing are best considered as complementary techniques In practice one can shed program verification but not testing Aditya P Mathur 2005 10 Program representation Basic blocks A basic block in program P is a sequence of consecutive statements with a single entry and a single exit point Thus a block has unique entry and exit points Control always enters a basic block at its entry point and exits from its exit point There is no possibility of exit or a halt at any point inside the basic block except at its exit point The entry and exit points of a basic block coincide when the block contains only one statement Aditya P Mathur 2005 Basic blocks Example contd Basic blocks Entry point Exit point 1 5 OMAN oath WN Aditya P Mathur 2005 Basic blocks Example Example Computing x raised to y begin int x y power float z while power 0 Z Z X input x y power power 1 if y lt 0 power y if y lt 0 else z 1 z output z end power y 1 Aditya P Mathur 2005 Control Flo
13. n excited in states q and qj respectively yield identical output sequences States q and qj are said to be equivalent if O q r O q r for any set V If q and qj are not equivalent then they are said to be distinguishable Thus machines M and M could be the same machine This definition of equivalence also applies to states within a machine 4 Properties of FSM Machine Equivalence Machine equivalence Machines M and M are said to be equivalent if a for each state o in M1 there exists a state o in M such that o and o are equivalent and b for each state o in M there exists a state o in M such that o and o are equivalent Machines that are not equivalent are considered distinguishable Minimal machine An FSM M is considered minimal if the number of states in M is less than or equal to any other FSM equivalent to M Aditya P Mathur 2005 Aditya P Mathur 2005 Properties of FSM k equivalence 4 Properties of FSM k equivalence 4 contd k equivalence Let M X Y Q m T O1 and M X Y Q aay Tos O be two FSMs States that are not k equivalent are considered k distinguishable States qi Q and qje Q are considered k equivalent if when excited by any input of length k yield identical output sequences It is also easy to see that if two states are k distinguishable for any k gt 0 then they are also distinguishable for any n k If M and M are not k distinguishab
14. ng over the alphabet 0 1 Also dog cat dog dog lion is a String over the alphabet dog cat horse lion We will use lower case letters such as p q r to denote strings The length of a string is the number of symbols in that string Given a string s we denote its length by s Thus 1011 4 and dog cat dog 3 A string of length 0 also known as an empty string is denoted by e Note that denotes an empty String Aditya P Mathur 2005 Alphabet A collection of symbols is known as an alphabet We use an upper case letter such as X and Y to denote alphabets Though alphabets can be infinite we are concerned only with finite alphabets For example X 0 1 is an alphabet consisting of two symbols 0 and 1 Another alphabet is Y dog cat horse lion that consists of four symbols dog cat horse and lion Aditya P Mathur 2005 String concatenation Let s1 and s2 be two strings over alphabet X We write s1 s2 to denote the concatenation of strings s1 and s2 For example given the alphabet X 0 1 and two strings 011 and 101 over X we obtain 011 101 011101 It is easy to see that S1 s2 s1 s2 Also for any string s we have s s and s s Aditya P Mathur 2005 15 Languages A set L of strings over an alphabet X is known as a language A language can be finite or infinite The following sets are finite languages over the binary alphabet 0 1 The empty s
15. of the requirements In most commercial environments the process is a bit more formal The tests are generated using a mix of formal and informal methods directly from the requirements document serving as the source In more advanced test processes requirements serve as a source for the development of formal models Aditya P Mathur 2005 Test generation strategies Summary es algorithm algorithm Test generation algorithm algorithm Test generation algorithm Aditya P Mathur 2005 Test generation strategies Model based require that a subset of the requirements be modeled using a formal notation usually graphical Models Finite State Machines Timed automata Petri nets etc Specification based require that a subset of the requirements be modeled using a formal mathematical notation Examples B Z and Larch Code based generate tests directly from the code Aditya P Mathur 2005 14 Strings Strings play an important role in testing A string serves as a test input Examples 1011 AaBc Hello world A collection of strings also forms a language For example a set of all strings consisting of zeros and ones is the language of binary numbers In this section we provide a brief introduction to strings and languages Aditya P Mathur 2005 Strings over an Alphabet A string over an alphabet X is any sequence of zero or more symbols that belong to X For example 0110 is a stri
16. of the test program should be recorded in a suitable file using the Company Failure Report Form Aditya P Mathur 2005 Program behavior Can be specified in several ways plain natural language a state diagram formal mathematical specification etc A state diagram specifies program states and how the program changes its state on an input sequence inputs Aditya P Mathur 2005 Test case data A test case is a pair consisting of test data to be input to the program and the expected output The test data is a set of values one for each input variable A test set is a collection of zero or more test cases Sample test case for sort Test data lt A 12 29 32 gt Expected output 29 12 32 Aditya P Mathur 2005 Program behavior Example Consider a menu Monn Bar Tools Windows driven application Pulled down ep menu Aditya P Mathur 2005 4 Program behavior Example contd pon ER ae on file mouse parae menu t Sy t User selects t Open Da b State ary Diagram User releases the mouse t task initiated by the user rae nate the ne current directory s application state invisible in a S window gt Aditya P Mathur 2005 Oracle Example Program under test Observed Does the observed behavior match the expected behavior Yes or No with an explanation Aditya P Mathur 2005 Behavior observation and analysis In the first step one
17. rd or as complex as the flight controller in an aircraft In any case an embedded system contains one or more computers for processing inputs Aditya P Mathur 2005 FSM Actions with state transitions Machine to convert a sequence of decimal digits to an integer d ADD num d Ce Ca O d INIT num d a Notice ADD INIT ADD OUT actions b INIT Initialize num ADD Add to num OUT Output num Aditya P Mathur 2005 Specifying embedded systems An embedded computer often receives inputs from its environment and responds with appropriate actions While doing so it moves from one state to another The response of an embedded system to its inputs depends on its current state It is this behavior of an embedded system in response to inputs that is often modeled by a finite state machine FSM Aditya P Mathur 2005 FSM Formal definition An FSM is a quintuple X Y Q qo O where X is a finite set of input symbols also known as the input alphabet Y is a finite set of output symbols also known as the output alphabet Q is a finite set states Aditya P Mathur 2005 17 FSM Formal definition contd State diagram representation of FSM A state diagram is a directed graph that contains nodes representing states and edges representing state transitions and output functions qo in Q is the initial state Qx X Qisanext state or state transition function and Each
18. ut intent maple walnut Spoken We need a new refrigerator intent We need a new wash ing machine Incorrect call by the referee in a tennis match Written What kind of pans did you use Intent What kind of pants did you use Tester may make a mistake In observing the behavior Yes Program behaves as No Program does not behave desired as desired A failure has occured Aditya P Mathur 2005 Aditya P Mathur 2005 Software quality Static quality attributes structured maintainable testable code as well as the availability of correct and complete documentation Dynamic quality attributes software reliability correctness completeness consistency usability and performance Aditya P Mathur 2005 Software quality contd Completeness refers to the availability of all features listed in the requirements or in the user manual An incomplete software is one that does not fully implement all features required Consistency refers to adherence to a common set of conventions and assumptions For example all buttons in the user interface might follow a common color coding convention An example of inconsistency would be when a database application displays the date of birth of a person in the database in different formats ignoring user preference Aditya P Mathur 2005 Software quality contd Usability refers to the ease with which an application can be used This is an area in itself and th
19. w Graph CFG A control flow graph or flow graph G is defined as a finite set N of nodes and a finite set E of edges An edge i j in E connects two nodes n and njin N We often write G N E to denote a flow graph G with nodes given by N and edges by E Aditya P Mathur 2005 11 4 Control Flow Graph CFG In a flow graph of a program each basic block becomes a node and edges are used to indicate the flow of control between blocks Blocks and nodes are labeled such that block b corresponds to node n An edge i j connecting basic blocks b and b implies that control can go from block b to block b We also assume that there is a node labeled Start in N that has no incoming edge and another node labeled End also in N that has no outgoing edge Aditya P Mathur 2005 4 CFG Example Same CFG with statements removed N Start 1 2 3 4 5 6 7 8 9 End E Start 1 1 2 1 3 2 4 3 4 4 5 5 6 6 5 5 7 7 8 759 End Aditya P Mathur 2005 4 CFG Example N Start 1 2 3 4 5 6 7 8 9 End E Start 1 1 2 1 3 2 4 3 4 4 5 5 6 6 5 abe 5 7 7 8 7 9 a End power powert Aditya P Mathur 2005 4 Paths Consider a flow graph G N E A sequence of k edges k gt 0 e l e 2 e_k denotes a path of length k through the flow graph if the following sequence condition holds Given that Tips tas l
Download Pdf Manuals
Related Search