TLDR;
This video introduces the use of graphs in software testing, focusing on how to model software artifacts as graphs and design test cases based on these models. It recaps basic graph terminologies, discusses the history and applications of graph theory, and explains key concepts such as vertices, edges, directed and undirected graphs, initial and final vertices, and paths. The video also covers reachability, subgraphs, and the use of graph algorithms like breadth-first search (BFS) and depth-first search (DFS) for test case design. It concludes by defining test paths, feasible and infeasible test paths, and introduces structural and data flow coverage criteria.
- Introduces graphs as models for software artifacts.
- Explains basic graph terminologies and concepts.
- Discusses reachability, test paths, and coverage criteria.
Introduction to Graphs in Software Testing [0:13]
The video begins by introducing the concept of modelling software artifacts as graphs, which is one of the four structures to be considered for test case design algorithms. These structures include graphs, logical expressions, sets, and the underlying grammar of a software programming language. The focus will be on test case algorithms that use graphs.
Basic Graph Terminology [0:47]
The presenter recaps basic graph terminologies relevant to test case design. Graph theory is an old subject, with its origins traced back to Euler's work in 1736. Graphs have applications in computer science, physics, chemistry, biology, and sociology, where they are used to model social networks. In this course, graphs will be used as models of software artifacts to design test cases.
What is a Graph? [2:19]
A graph consists of nodes (or vertices) and edges (or arcs/lines). An undirected graph has unordered pairs of nodes, while a directed graph has ordered pairs, indicating direction. Edges can also take a vertex to itself, forming a self-loop. Graphs can be finite (with a finite number of vertices) or infinite, but the course will focus on finite graphs for modelling software artifacts.
Vertex Degrees and Graph Features [5:26]
The degree of a vertex is the number of edges connected to it. In directed graphs, the in-degree is the number of edges coming into a vertex, and the out-degree is the number of edges going out of it. Graphs can have special designated vertices: initial vertices (where computation begins) and final vertices (where computation ends). Software artifacts are typically deterministic, so graph models usually have only one initial state but can have multiple final states. Initial vertices are marked with an incoming line, while final vertices are marked with concentric circles.
Graphs as Models of Software Artifacts [11:08]
Graphs are a popular structure in testing and static program analysis tools. They can represent control flow graphs, data flow graphs, call graphs, UML state machines, use case diagrams, and activity diagrams. These graphs often have extra annotations or labels associated with vertices and edges. The goal is to design test cases that cover the graph in some way, based on coverage criteria.
Code Fragments and Control Flow Graphs [13:26]
The lecture uses code fragments to illustrate how to create graph models. For example, an if statement can be represented as a graph with nodes for the initial state, the then branch, the else branch, and the final state. Edges are labelled with predicates that determine when a branch is taken. These graphs have initial vertices and edges labelled with guards or predicates.
Paths in Graphs [18:05]
A path in a graph is a finite sequence of vertices such that each pair of successive vertices is connected by an edge. The length of a path is the number of edges in it. A subpath is a subsequence of vertices in the path. Paths are important for designing test cases to reach specific statements or nodes in the graph. A vertex is reachable if there is a path from one of the initial vertices to that vertex. Similarly, an edge is reachable if there is a path from an initial vertex to the beginning vertex of that edge, and then the edge is used to reach the end vertex.
Subgraphs and Reachability Algorithms [21:43]
A subgraph consists of a subset of vertices and edges from the original graph. A subgraph is reachable if any of its vertices are reachable from the initial vertex of the main graph. Algorithms like breadth-first search (BFS) and depth-first search (DFS) are used to compute paths and reachability.
Test Paths and Feasibility [23:30]
A test path begins at an initial vertex and ends at a final vertex. Test paths that can be executed by test cases are called feasible test paths, while those that cannot (e.g., reaching dead code) are infeasible test paths. A test path visits a vertex or edge if it occurs along the path. It tours a path if that path is a subpath of the test path.
Tests and Test Paths Example [26:24]
An example is given using a graph that models a switch case statement. A test case with input a = 0 and b = 1 executes the path U-V-W-X, while a test case with a = 3 and b = 1 executes the path U-X. A set of test cases can have a set of test paths, which is the union of all test paths executed by each test case.
Reachability and Test Requirements [29:08]
Reachability in the context of test paths considers conditions associated with edges. Infeasible test paths correspond to unreachable vertices or edges. Graphs are used for test case design by developing a model of a software artifact, which can include annotations like initial and final vertices, labels of statements, and predicates. Test requirements describe properties of a test path, and test criteria are rules that define these requirements.
Coverage Criteria [31:58]
A set of test requirements satisfies a coverage criteria if the test cases meet all the test paths that satisfy the requirement. Two kinds of coverage criteria are structural coverage (based on vertices and edges) and data flow coverage (based on variables and their values). The next module will focus on structural coverage criteria and algorithms for test case design.