Week 1

Imagine a world where a single line of code can cost millions of dollars or even human lives. That isn't a dystopian
future; it is the reality of the software-driven world we live in today. From the finance apps on your phone to the control
systems of airplanes, software is ubiquitous. Because we rely on it so heavily, the quality of that software is non-
negotiable.

The Cost of Failure

History is filled with cautionary tales that illustrate why testing is not just a "nice-to-have," but a critical necessity.

• The 36-Second Flight: In 1996, the Ariane 5 rocket exploded just 36 seconds after launch. The cause? A
software exception where a 64-bit floating-point number was dangerously converted into a 16-bit integer.
• The Silent Killer: The Therac-25 medical accelerator, designed to treat tumors, tragically killed six patients
due to a radiation overdose. The culprit was a race condition in the control software.
• The Expensive Math Error: Intel once lost an estimated $475 million because of a defective Pentium
chip that couldn't divide floating-point numbers correctly.

The "Rule of Ten"

There is a golden rule in software engineering: Timing is everything. If you catch a bug during
the Requirements phase, it might cost $6 to fix. If that same bug slips through to Post-Deployment, the cost could
skyrocket to $100,000 or more. This is why testing shouldn't be saved for the end; it must be a continuous heartbeat
throughout the project.

Software doesn't just appear; it evolves through a Software Development Life Cycle (SDLC). Think of this as the
"life story" of an application, from its conception to its retirement.

The Standard Phases

1. Planning: We identify what the market needs and if it's feasible.

2. Requirements Definition: We write down exactly what the software must do (Functional, Hardware, and
Quality requirements).
3. Design & Architecture: We draw the blueprints. This defines modules, database connections, and how pieces
fit together.
4. Development: The actual coding happens here.
5. Testing: We hunt for defects until the product meets its requirements.
6. Maintenance: The work isn't done after launch; we must fix bugs and add features over time.

different Ways to Tell the Story (Models)

• The Waterfall Model: The traditional, step-by-step approach. You finish one phase before starting the next.
• The V-Model: This model emphasizes Verification and Validation. Picture a "V" shape where every
development step on the left (like Requirements) is directly mirrored by a testing step on the right (like
Acceptance Testing).
• Agile: The modern favorite. Instead of one long cycle, Agile breaks the project into tiny, repeating loops
called iterations. It is fast, adaptive, and focuses on quick delivery.

To understand testing, we must agree on the vocabulary. There are subtle but vital distinctions in the terms we use.

Validation vs. Verification

These two sound similar, but ask different questions:

• Validation: "Are we building the right product?" (Does this software actually solve the user's problem?)
1
 • Verification: "Are we building the product right?" (Does the software match the technical requirements we
wrote down?)
• Note: Most technical testing focuses on Verification.

The Anatomy of a Bug

When we say something "went wrong," we break it down into a chain reaction:

1. Fault: The static defect in the code (e.g., a typo or wrong logic). It lives in the file, waiting.
2. Error: The incorrect internal state that happens when the code runs the Fault.
3. Failure: The external crash or wrong output that the user actually sees.

The Evolution of a Tester

How a tester thinks determines their effectiveness. We measure this in Maturity Levels:

• Level 0: "Testing is just debugging." (Novice thinking).

• Level 1: "I test to show the software works." (Impossible, because you can't prove perfection).
• Level 2: "I test to show the software doesn't work." (Better, but can make developers hate you).
• Level 3: "I test to reduce risk." (The professional mindset: We work together to make the product safer).

How do we actually go about testing? We have different "lenses" and "levels."

The Two Lenses

• Black-Box Testing: Imagine the software is a sealed black box. You don't care how the gears turn inside; you
only care that if you put "A" in, you get "B" out. (Used in System Testing).
• White-Box Testing: You tear the box open and inspect the gears. You look at the internal code structure. (Used
in Unit Testing).

The Levels of Defense

1. Unit Testing: Checking the smallest individual bricks (functions/methods). Done by developers.
2. Integration Testing: Checking if the bricks hold together when cemented into a wall (modules).
3. System Testing: Checking the entire house (the full application).
4. Acceptance Testing: The homeowner walks through to see if they want to buy it (Customer validation).

Maintenance Testing

• Regression Testing: This is done after you modify or fix code. The idea is to ensure that your new fix didn't
break something else that was previously working. It is crucial during the maintenance phase.

Manual testing is slow and prone to human error. To keep up with modern speed, we use Test Automation—writing
code to test our code.

The Anatomy of an Automated Test

A computer needs precise instructions to run a test. We structure every test case with four parts:

1. Prefix Values (Setup): Getting the software ready. (e.g., "Open the calculator app").
2. Test Case Values: The actual input. (e.g., "Type 2 + 2").
3. Verification Values: The expected result. (e.g., "Expect 4").
4. Postfix Values (Teardown): Cleaning up. (e.g., "Close the app").

Meet JUnit
2
JUnit is the standard tool (framework) for automating Java tests. It acts as a referee for your code.

• It uses Annotations to control the flow:

o @Test: "Hey JUnit, this method is a test!"
o @BeforeEach: "Run this setup code before every single test."
o @AfterEach: "Run this cleanup code after every single test."
• It uses Assertions to judge the result:
o assertEquals(expected, actual): The moment of truth. If the calculator says "5" but you expected
"4", JUnit throws a red flag and fails the test.

By combining these tools, we ensure that our software is robust, reliable, and ready for the real world.

Week 2
To rigorously test software, we often need to draw a map of it. In computer science, this map is called a Graph.

The Anatomy of a Graph

A graph $G = (V, E)$ is simple:

• $V$ (Vertices/Nodes): These are the locations. In software, they might represent statements, methods, or
states.
• $E$ (Edges): These are the roads connecting the locations. They represent the flow of control or data.
• Directed vs. Undirected: On a one-way street (Directed Graph), order matters ($u \to v$). On a two-way street
(Undirected Graph), the connection is mutual.

The Map Representations

How do we store this map in a computer?

1. Adjacency Matrix: A giant grid (2D array). Good for "dense" cities with many roads, but wastes memory if
the map is empty.
2. Adjacency Lists: A list for each location showing where you can go next. This is memory-efficient for "sparse"
maps and is the standard for most testing tools.

Once we have a map, we need algorithms to explore it. These are essential for determining Reachability—can we
actually get from the start of the program to that specific line of code?

1. Breadth First Search (BFS): The Ripple

Imagine dropping a stone in a pond. The ripples expand outward in perfect circles. This is BFS.

• It uses a Queue (First-In, First-Out).

• It explores neighbors layer by layer (Distance 1, then Distance 2...).
• Superpower: It finds the Shortest Path from the start to any node.
• Color Coding: It "paints" nodes White (undiscovered), Blue (in the queue), and Black (finished).

2. Depth First Search (DFS): The Maze Runner

Imagine exploring a maze. You run down a path until you hit a dead end, then you backtrack to the last intersection
and try a different path. This is DFS.

• It uses a Stack (Last-In, First-Out) or Recursion.

3
 • Time Stamps: It records when a node is first seen (Discovery time, d) and when we are done with it (Finish
time, f).
• Parenthesis Theorem: The lifespan of a node in DFS is perfectly nested. If Node u discovers Node v, then v's
entire processing time happens inside u's time.

DFS Edge Classification

DFS reveals the hidden structure of the graph by classifying edges:

• Tree Edges: The main paths we discovered.

• Back Edges: Roads that lead back to an ancestor (these create loops!).
• Forward Edges: Shortcuts to a descendant.
• Cross Edges: Roads between branches that aren't directly related.

Now that we have the map, how much of it do we need to drive on to say we are "done" testing? These rules are
called Coverage Criteria.

Test Requirements (TR)

Before we start, we define Test Requirements (TR). Think of these as the specific "To-Do List" items generated by
the rules below. For example, if the rule is "Node Coverage," the TR is the set of all nodes $\{1, 2, 3...\}$. If you visit
all items in the TR set, you have satisfied the criteria.

The Basics

• Node Coverage: Your test cases must visit every single city (statement).
• Edge Coverage: Your test cases must drive on every single road (branch). This is slightly stronger than Node
Coverage.
• Edge-Pair Coverage: You must drive every combination of two consecutive roads.

The Loop Problem

Ideally, we would want Complete Path Coverage (driving every possible route). But if your map has a Loop, the
number of paths is infinite. You can drive around the loop 1 time, 2 times, 500 times... you can never test them all.

The Solution: Prime Paths

To solve the infinite loop problem, we use Prime Paths.

• Simple Path: A path with no internal loops (you don't cross your own track).
• Prime Path: A Simple Path that is as long as possible—you can't extend it any further without repeating a
node.
• The Strategy: By testing all Prime Paths, we visit all nodes and edges, and we test loops "just enough"
(skipping them, entering them, and iterating them) without getting stuck in infinity.

Round Trip Coverage

Another way to handle loops is Round Trip Coverage:

• Simple Round Trip: Keeps at least one loop path for each reachable node that starts/ends a loop.
• Complete Round Trip: Keeps all loop paths.

Visiting vs. Touring

There is a subtle difference in how we verify tests:

4
 • Visit: A test path visits a node if it just passes through it.
• Tour: A test path tours a subpath if that entire specific sequence exists within the test path.

Handling Impossible Roads

Sometimes, the rules say "Drive this Prime Path," but the map logic says "You can't turn left here." This is an Infeasible
Test Requirement. To handle this, we allow flexibility:

• Sidetrips: You can leave the required path briefly (like stopping for gas) and come back to the same spot, as
long as you eventually finish the tour.
• Detours: You can leave the path and rejoin it at a later point (skipping a section).
• Best Effort: The goal is to satisfy as many requirements as possible without breaking the laws of physics (or
logic).

Week 3
If testing is the art of navigation, we first need a good map of the actual code. We call this map a Control Flow Graph
(CFG). It translates messy source code into a clean, traversable structure.

The Building Blocks

To build a CFG, we don't map every single semicolon. We group code into Basic Blocks:

• Basic Block: A chunk of code with one entry and one exit. If the first line runs, all the lines inside run. No
branching allowed inside a block.
• The Nodes: Each Basic Block becomes a single Node in our graph.
• The Edges: These represent the jumps—where the code could go next (e.g., the 'True' and 'False' branches of
an ifstatement).

Mapping Complex Structures

Different code structures create different map patterns:

• If/Else: Splits the path into two branches that usually rejoin later.
• Loops (For/While): Create circles (cycles) in the graph. We often add "dummy nodes" to cleanly represent the
loop's start or end conditions.
• Switch-Case: A hub with many spokes. Watch out for cases without break statements—they "fall through" to
the next case, creating extra edges!
• Exceptions: Hidden wormholes. A try-catch block creates invisible edges from the try block directly to
the catch block (and finally block), bypassing normal logic.

So far, we've only looked at control (which line runs next). Now, we look at data (what values are we carrying?). This
is Data Flow Analysis. We trace the life of a variable from its birth to its usage.

Definitions and Uses

• Definition (Def): A location where a value is stored in memory.

o Example: x = 42; or read(x);
• Use: A location where that value is accessed/read.
o C-Use (Computational): Used in calculations or output. (e.g., y = x + 1; or print(x);)
o P-Use (Predicate): Used to make a decision. (e.g., if (x > 0) ...)
o Note: A P-Use has two outcomes (True/False), so it affects the flow of the graph.

The Journey of a Value

5
We want to verify that every time we assign a value (Def), it actually gets used correctly.

• du-pair: A specific pair of locations: (Where x is defined, Where x is used).

• Def-Clear Path: A path from a Definition to a Use where the variable is not redefined.
o Analogy: If you mail a letter (Def) to your friend (Use), a "Def-Clear Path" means the letter arrives
without someone else opening it and swapping the message (Redefining it) along the way.

We can create test rules based specifically on these data journeys. These are Data Flow Coverage Criteria.

The Three Tiers of Data Coverage

1. All-Defs Coverage (The Minimum):

o For every definition of a variable, you must test at least one path to at least one use.
o Philosophy: "I wrote this value; did it get used somewhere?"
2. All-Uses Coverage (The Standard):
o For every definition, you must reach all possible uses.
o If x is defined in line 1 and used in line 10 AND line 20, you must test paths to both.
o Philosophy: "I wrote this value; did everyone who needs it get it?"
3. All-du-Paths Coverage (The Perfectionist):
o For every definition and every use, you must trace every possible path between them (that is simple and
def-clear).
o Philosophy: "I need to test every single route the data could possibly take to get to its destination."

Best Effort Touring

Just like with structural coverage, sometimes a specific data path is impossible to execute (infeasible). We use Best
Effort Touring, allowing for "def-clear side trips" (wandering off path but not changing the variable) to make the test
possible.

We now have many ways to test code. How do they compare? Some criteria are stricter than others. If you satisfy a
strict one, you automatically satisfy the weaker ones. This is called Subsumption.

The Power Ranking (Strongest to Weakest)

1. Complete Path Coverage: (Impossible for loops).

2. Prime Path Coverage: (Very strong structural coverage).
3. All-du-Paths Coverage: (Very strong data coverage).
4. All-Uses Coverage: (Strong data coverage).
5. Edge-Pair / All-Defs / Edge / Node Coverage: (Weaker criteria).

Key Takeaway: Prime Path Coverage is generally superior to All-du-Paths Coverage because every simple data path
is also a simple structural path. If you test all Prime Paths, you have likely tested all data paths too.

Week 4
After we have tested individual pieces of code (Unit Testing), we must stick them together. This phase is Integration
Testing. Its goal is not to check the logic inside the modules, but to check the Interfaces—the connections between
them.

The Interfaces

Modules talk to each other in three main ways:

1. Procedure Call: Method A calls Method B.

2. Shared Memory: Both A and B read/write to the same global variable or database.
6
 3. Message Passing: A sends a data packet to B (common in web services).

Why do they fail? Interfaces are fragile. You might pass parameters in the wrong order, assume the wrong data type, or
create "Race Conditions" where two modules fight over the same memory at the same time.

The Scaffolding (Stubs and Drivers)

You often can't test a module in isolation because it relies on other missing parts. We use fake code to fill the gaps:

• Stubs: Fake "Callees." If Module A calls Module B (which isn't built yet), we replace B with a Stub that just
returns a simple "OK."
• Drivers: Fake "Callers." If we want to test Module B, but the main program isn't built, we write a Driver script
that just calls B to see if it works.

Integration Strategies

• Top-Down: Start with the main menu and work down. Uses Stubs for lower levels.
• Bottom-Up: Start with the utility functions and work up. Uses Drivers to trigger them.
• Sandwich: Do both at once (meet in the middle).
• Big Bang: Wait until everything is finished, glue it all together, and pray. (Not recommended).

We can also use graphs to model the design of the system.

• Call Graphs: Nodes are modules, edges are calls.

• Coupling Variables: These are variables passed between modules (parameters, return values, globals).

Design Data Flow

Just like in code, we track data across the boundary:

• Last-def: The last place a variable is defined in the Caller before it is handed off.
• First-use: The first place the variable is used in the Callee.
• Coupling Coverage: We want to ensure that every Last-def reaches every First-use across the interface.

Sometimes, the logic isn't about variables, but about Order (Sequencing Constraints).

• Example: You must open() a file before you write() to it, and you must open() it before you close() it.
• Violating these constraints creates bugs. We test this by generating paths that specifically check if these rules
are obeyed.

Finite State Machines (FSMs)

For complex behavior, we use Finite State Machines.

• Nodes = States: (e.g., "Door Open", "Door Closed").

• Edges = Transitions: (e.g., "Button Pressed").
• We can apply all our coverage criteria (Node, Edge, Edge-Pair) to FSMs to ensure we have tested every state
and every transition.

Before modern graph theory took over, testers used "Classical" terms. They map directly to what we've learned:

• Statement Coverage = Node Coverage.

• Branch Coverage = Edge Coverage.
• Loop Coverage = Prime Path Coverage.

7
Cyclomatic Complexity

A famous metric by McCabe to measure how complex a program is.

$$M = E - N + 2P$$

(Edges - Nodes + 2).

This number tells you the number of Linearly Independent Paths through the code. Ideally, if your complexity is 5,
you need at least 5 test cases to cover the "Basis Paths."

Week 5
Software decisions are ruled by Logic. Every if statement is a gatekeeper that decides where the program goes next.
To test effectively, we must understand the language of these gates: Propositional Logic.

The Building Blocks

• Propositions: Statements that are strictly True or False. (e.g., "The user is logged in," or "x > 5").
• Connectives: The glue that holds propositions together:
o $\land$ (AND): Both must be true.
o $\lor$ (OR): At least one must be true.
o $\neg$ (NOT): The opposite.
o $\rightarrow$ (IMPLIES): If A, then B.
o $\leftrightarrow$ (IFF): A if and only if B (Equivalent).
• Truth Tables: The ultimate map of logic. By listing every possible combination of True/False inputs, we see
exactly how a logic formula behaves.

The Problem with Satisfaction

We want to know if a specific scenario is even possible.

• Satisfiability (SAT): Is there any set of inputs that makes this formula True?
• Validity: Is the formula always True, no matter the inputs? (A Tautology).
• Challenge: For complex software with hundreds of variables, finding these "satisfying assignments" (Test
Cases) is a hard problem (NP-complete). We often rely on tools called SAT Solvers to help us.

In software testing, we analyze logic at two levels:

1. Predicate ($p$): The entire logical expression. (e.g., (a > b) || C || f(z)).

2. Clause ($c$): The smallest individual building blocks inside the predicate. (e.g., a > b, C, f(z)). Clauses
contain no logical operators (like AND/OR).

Determination: Making a Clause "Count"

When testing, we don't just want to know if the result is True. We want to know if a specific clause is working.

• Major Clause ($c_i$): The specific clause we are currently testing.

• Minor Clauses: All the other clauses in the predicate.
• Determination: We say a Major Clause determines the Predicate if flipping the Major Clause's
value forces the Predicate's result to flip too.
o Example: If $p = A \land B$, and $B$ is True, then $A$ determines $p$. (If $A$ is True, $p$ is True.
If $A$is False, $p$ is False).
o Formula: To find the exact conditions where clause $c$ determines predicate $p$, we compute: $p_c =
p_{c=true} \oplus p_{c=false}$. (where $\oplus$ is Exclusive OR).
8
Just like with graphs, we have levels of thoroughness for testing logic.

1. The Simple Approaches

• Predicate Coverage (PC): Run tests where the whole predicate evaluates to True, and where it evaluates to
False. (Weak—misses internal logic).
• Clause Coverage (CC): Run tests where every individual clause is True at least once, and False at least once.
(Weak—doesn't guarantee the predicate result flips).
• Combinatorial Coverage (CoC): Test every single row of the Truth Table ($2^n$ combinations). (Thorough,
but impossible for large formulas).

2. Active Clause Coverage (ACC) - "The Smart Approach"

We want to check if the Major Clause actually controls the outcome. We force the Major Clause to determine the
predicate.

• General ACC (GACC): The Major Clause determines the predicate, but the Minor Clauses can change values
freely between tests.
• Correlated ACC (CACC): The Major Clause determines the predicate, and we ensure the full predicate result
is True in one test and False in the other. (This is the industry standard!).
• Restricted ACC (RACC): The Major Clause determines the predicate, and the Minor Clauses must
stay exactly the same between tests. (Strict and often infeasible).

3. Inactive Clause Coverage (ICC)

Sometimes we want to ensure a clause doesn't affect the outcome (e.g., a safety override switch shouldn't matter during
normal operation). This tests the negative case.

Applying pure logic to real code is tricky because of Internal Variables.

• Example: You want to test if (Temp > Threshold). You can't just set Temp directly. You have to call
functions (e.g., setWeather()) that indirectly change Temp.

The RIPR Model in Logic

1. Reachability: We must execute code that reaches the if statement.

2. Infection: We must find inputs that trigger the specific logic fault.
3. Propagation: The bad logic result must cause a visible failure later in the program.

• Thermostat Example: To test if the heater turns on, we must manipulate CurrentTemp, Threshold,
and Override settings via the API to force the logic gate ((Temp < Threshold) || Override) to behave the
way we want.

Week 6
Logic isn't just for code; it lives in Specifications and Finite State Machines (FSMs) too.

Specifications: The Logic of Requirements

Requirements often come in English, but we must translate them into logic to test them rigorously.

• Pre-conditions: Conditions that must be true before a function runs (e.g., month >= 1 && month <= 12).
• CNF & DNF: We often convert these requirements into standard forms:
o Conjunctive Normal Form (CNF): ANDs of ORs (e.g., (A or B) and (C or D)).

9
 o Disjunctive Normal Form (DNF): ORs of ANDs (e.g., (A and B) or (C and D)).
o Testing Strategy: For CNF, to test a clause, we make all other clauses in the AND group TRUE (so they
don't block us). For DNF, we make other OR groups FALSE.

Logic in FSMs (Finite State Machines)

In an FSM, the Transitions (arrows between states) are guarded by logic.

• Example: A subway door FSM moves from "Closed" to "Open" only if Speed == 0 AND EmergencyStop ==
False.
• The Strategy: We treat each transition guard as a Predicate. We apply our coverage criteria (like CACC) to
these guards to ensure every condition that allows or blocks a state change is tested.

Sometimes, a logical predicate in the code is just too messy or "expensive" to test directly. We might try to rewrite the
code to make it simpler. This is Predicate Transformation.

The Idea

We break a complex if statement into nested ifs.

• Original: if (A && B) { DoSomething(); }

• Transformed: if (A) { if (B) { DoSomething(); } }

The Problem

While this looks simpler, it introduces new problems:

1. Readability: Nested logic is harder for humans to read.

2. Coverage Mismatch: Satisfying "Predicate Coverage" on the new, transformed code is NOT the same as
satisfying "Active Clause Coverage" on the original code. You might actually lose test thoroughness by
rewriting it!

• Verdict: Usually, it's better to test the original complex predicate than to mangle the code just to make testing
"easier."

We've talked about "Satisfiability"—finding inputs that make a formula True. For huge programs, humans can't do this.
We use SMT Solvers (Satisfiability Modulo Theories).

SAT vs. SMT

• SAT Solvers: Work with pure Boolean logic (True/False). They are fast but dumb about numbers.
• SMT Solvers: Are smarter. They understand "Theories" like Arithmetic, Arrays, and Strings.
o Example: A SAT solver sees x > 5 as just a variable A. An SMT solver understands that if x=6, then x
> 5 is True.

How We Use Them

We use SMT solvers (like Z3 or CVC4) to automatically generate test cases.

1. We translate our code's logic path into a mathematical formula.

2. We ask the SMT solver: "Is there an input x that makes this path execute?"
3. The solver returns x = 42.
4. We use 42 as our test case input. This is the magic behind modern automated testing tools (Concolic Testing,
Symbolic Execution).

10
Week 7
Between the extremes of simple "Testing" (checking one input) and "Program Proving" (mathematically proving it
works for all inputs), there lies a powerful technique called Symbolic Execution.

The Core Concept

Normal execution runs a program with concrete data (e.g., x = 5). Symbolic execution runs the program
with symbols(e.g., x = α) representing arbitrary values. This allows us to reason about all possible inputs
simultaneously.

The Mechanics of Symbolic Execution

To make this work, we maintain two special data structures during execution:

1. Symbolic State ($\sigma$): A map connecting program variables to symbolic expressions.

o Example: If input a is $\alpha_1$ and b is $\alpha_2$, and we run x = a + b, the symbolic state updates
to $\sigma(x) = \alpha_1 + \alpha_2$.
2. Path Constraint (PC): A logical formula (quantifier-free, first-order logic) that accumulates the constraints
needed to reach the current point in the code.
o Start: PC = true (No constraints yet).
o Branching: When the code hits a conditional if (e) then S1 else S2:
§ To explore the Then branch (S1), we update $PC = PC \wedge \sigma(e)$.
§ To explore the Else branch (S2), we update $PC = PC \wedge \neg\sigma(e)$.

Example: The "Sum" Program

Consider this code:

1. x = a + b;
2. y = b + c;
3. z = x + y - b;
4. return z;

If inputs a, b, c are symbolic values $\alpha_1, \alpha_2, \alpha_3$:

• Line 1: $\sigma(x) = \alpha_1 + \alpha_2$

• Line 2: $\sigma(y) = \alpha_2 + \alpha_3$
• Line 3: $\sigma(z) = (\alpha_1 + \alpha_2) + (\alpha_2 + \alpha_3) - \alpha_2 = \alpha_1 + \alpha_2 + \alpha_3$
• Result: The function returns the sum of all three inputs. We proved this for any input without running a million
tests.

Handling Disadvantages

While powerful, Symbolic Execution has major flaws:

• Path Explosion: Loops create infinite trees of execution paths.

• Solver Limits: If the code uses a complex function (like cryptographic hashing) or external system calls, the
Constraint Solver might fail to find a solution (the "Satisfiability Problem").

To overcome the limits of pure Symbolic Execution, modern tools use Concolic Testing. The name is a portmanteau
of Concrete and Symbolic.

The Strategy

11
We run the program Concretely (with real numbers) and Symbolically (with formulas) side-by-side.

1. Generate Random Input: Start with x = 22, y = 7.

2. Execute: Run the code. The concrete values let us pass through complex functions (hash maps, libraries) that
would choke a symbolic solver.
3. Record: As we run, we record the symbolic constraints for the path we actually took.
4. Steer: To explore a new path, we pick the last decision point (e.g., "We took the else branch"). We negate the
symbolic constraint for that branch (PC_new = ... \wedge \neg LastCondition).
5. Solve: We ask an SMT solver to find new inputs that satisfy PC_new.
6. Repeat: We use these new inputs to run the program again, forcing it down the new path.

DART is a specific, influential framework designed to automate unit testing using Concolic principles. It specifically
targets C programs.

The Three Pillars of DART

1. Interface Extraction: DART automatically parses source code to find all external inputs (function arguments,
external variables). It handles complex C types like pointers, structs, and arrays.
2. Test Driver Generation: It automatically writes a "Test Driver"—a wrapper program that mimics the
environment and feeds random inputs to the function under test.
o Deep Initialization: random_init() recursively allocates memory for pointers and fills structs with
random data.
3. Directed Search: This is the dynamic analysis engine.
o It maintains a stack of branch decisions.
o It detects when random testing is "stuck" in a specific path.
o It uses symbolic constraints to calculate the exact inputs needed to flip a specific branch (e.g.,
"Find x such that f(x) == x + 10 triggers an error").

Robustness Features

DART is designed for the real world:

• Completeness Flags: It tracks if the search is exhaustive (all_linear, all_locs_definite). If these flags
remain 1, DART can mathematically prove that all feasible paths were explored.
• External Functions: If the code calls a library function (e.g., sin()), DART treats it as a black box returning
a random value, ensuring the test doesn't crash just because it can't analyze the library code.

Week 8
We have spent weeks looking inside the code (White-Box). Now, we treat the software as a "Black Box." We don't
care how it works, only what it does. This is Functional Testing.

Core Concept

A program is just a mathematical function: $y = P(x)$.

• Input ($x$): The data we feed it.

• Output ($y$): The result we get back.
• Goal: Verify that $P(x)$ matches the Requirements Specification.

The Problem of Infinity

Most input domains are effectively infinite (e.g., "Enter any integer"). We cannot test every value. We must choose a
smart subset of inputs that are most likely to find bugs.

12
The input domain is too big, so we divide it into Partitions (or Equivalence Classes).

• The Logic: If inputs A and B are in the same partition, the program should treat them exactly the same way.
If Apasses, B will probably pass. If A fails, B will probably fail.
• The Strategy: Pick just one representative value from each partition to test.

Example: Income Tax

Rule: "0-10k is 0% tax. 10k-50k is 10% tax. >50k is 20% tax."

• Partitions:
1. $[0, 10,000]$
2. $[10,001, 50,000]$
3. $[50,001, \infty)$
4. (Invalid) $< 0$
• Test Cases: We select one value from each: 5000, 25000, 100000, and -100. (4 tests instead of billions).

Programmers make mistakes at the "edges" of logic (e.g., writing > instead of >=). Boundary Value Analysis targets
these edges.

The Strategy

Instead of picking a random value inside the partition, we pick values on and just next to the boundary.

• Example (Range 1 to 10):

o ECP choice: 5 (Safe middle).
o BVA choices: 0, 1, 2 (Lower edge) AND 9, 10, 11 (Upper edge).
o Why: 0 and 11 test invalid inputs just outside the fence. 1 and 10 test the valid edge. 2 and 9 test "just
inside."

How do we systematically create these partitions? We look at the input parameters.

Two Approaches

1. Interface-Based: Look at each parameter in isolation.

o Parameter List: Is it null? Is it empty? Is it full?
o Parameter x: Is it null?
o Weakness: Misses interactions between parameters.
2. Functionality-Based: Look at the behavior of the whole system.
o Characteristic: "Element exists in List."
o Partitions: True, False.
o Strength: Better tests, but harder to design.

Combinations Strategies (Handling Multiple Inputs)

If you have 3 parameters with 5 partitions each, testing all combinations is $5 \times 5 \times 5 = 125$ tests. That gets
expensive fast.

• All Combinations (ACoC): Test everything ($125$ tests).

• Each Choice (ECC): Ensure every value is used at least once. (Weak).
• Pair-Wise (PWC): Ensure every pair of values is tested together. (Very efficient and finds most bugs).
• Base Choice (BCC): Pick a "normal/base" test case. Then vary one parameter at a time.

When business rules get complex (many conditions interacting), plain text requirements are confusing. Decision
Tables organize logic clearly.

13
Structure

• Conditions: The inputs (e.g., "Is Senior Citizen?", "Is Tuesday?").

• Rules: The combinations of Yes/No answers.
• Actions: The result (e.g., "Give Discount").

Conditions Rule 1 Rule 2 Rule 3

Senior Citizen? Y N N
Tuesday? - Y N
Action: Discount Yes Yes No

Testing Strategy: Each column (Rule) becomes one Test Case. This ensures no combination of business rules is
overlooked.

Week 9
So far, we have tested software based on its logic (graphs, predicates) and its function (inputs/outputs). Now, we look
at its Syntax. Every software artifact—whether it's source code, a design model, or an input file—follows a strict
grammar. Syntax-based testing uses this grammar to generate test cases.

The Levels of Syntax

Programming languages typically have three levels of syntax:

1. Lexical Level: How characters form words (tokens). Defined by Regular Expressions.
2. Phrase Level: How words form sentences (statements). Defined by Context-Free Grammars (BNF).
3. Context Level: How sentences make sense (type checking, scope). Defined by Context-Sensitive Grammars.

Grammar-Based Coverage Criteria

We can define coverage based on the grammar itself:

• Terminal Symbol Coverage (TSC): Have we used every keyword and operator (e.g., while, if, +) at least
once?
• Production Coverage (PC): Have we used every rule in the grammar (every production) at least once?
• Derivation Coverage (DC): Have we generated every possible string the grammar can produce? (Usually
impossible as it's infinite).

The most powerful application of syntax-based testing is Mutation Testing. Instead of using the grammar to
generate valid strings, we use it to generate invalid but "almost correct" strings to test our test suite.

The Core Concept

1. Ground String: The original, correct program $P$.

2. Mutant: A copy of the program $P'$ with one small syntactic change (a "mutation").
o Example: Change a + b to a - b.
3. Killing the Mutant: A test case "kills" a mutant if it passes on the original program but fails on the mutant (or
produces different output).
o Goal: Kill all non-equivalent mutants. If your tests kill 100% of mutants, your tests are extremely robust.

Types of Mutants

• Stillborn: Syntactically invalid (doesn't compile). These are useless.

14
 • Trivial: Killed by almost any test case.
• Equivalent: Functionally identical to the original program. Impossible to kill.
o Example: Changing for (int i=0; i<10; i++) to for (int i=0; i!=10; i++).
• Dead: A valid mutant that was successfully killed by a test case.

Strong vs. Weak Mutation

• Strong Mutation: The fault must propagate all the way to the final output (the user sees the error).
• Weak Mutation: The internal state must be incorrect immediately after the mutated statement (Infection), but
we don't require it to propagate to the final output. This is easier to check but less rigorous.

We generate mutants using specific rules called Mutation Operators. These are designed to mimic common
programmer errors.

Source Code Mutation Operators

These apply to the body of the code:

1. AOR (Arithmetic Operator Replacement): Replace + with -, *, /, %.

2. ROR (Relational Operator Replacement): Replace > with >=, <, <=, ==, !=, True, False.
3. COR (Conditional Operator Replacement): Replace && with ||.
4. ABS (Absolute Value Insertion): Replace x with abs(x) or -abs(x).
5. UOI (Unary Operator Insertion): Insert ++, --, !, ~.
6. SVR (Scalar Variable Replacement): Replace variable x with variable y (of compatible type).
7. Bomb Statement: Replace a statement with a function that crashes immediately (tests reachability).

Integration Mutation Operators

These apply to the interfaces between modules (method calls):

1. IPVR (Integration Parameter Variable Replacement): Replace a parameter in a call with another variable
(e.g., sum(a, b) $\to$ sum(a, x)).
2. IUOI (Integration Unary Operator Insertion): Add operators to arguments (e.g., sum(a, b) $\to$ sum(a,
-b)).
3. IPEX (Integration Parameter Exchange): Swap arguments (e.g., max(a, b) $\to$ max(b, a)).
4. IMCD (Integration Method Call Deletion): Delete the method call entirely.

Object-Oriented Mutation Operators

These target OO features like inheritance and polymorphism:

1. AMC (Access Modifier Change): Change public to private.

2. HVD (Hiding Variable Deletion): Remove a variable in a subclass to force it to use the parent's variable.
3. OMD (Overriding Method Deletion): Remove an overridden method so the parent's version is called.
4. ATC (Actual Type Change): Change new ArrayList() to new LinkedList().

Mutation testing is often considered the "strongest" coverage criterion.

Subsumption

• Mutation vs. Graph Coverage:

o If you kill all "Bomb" mutants (statement deletion), you achieve Node Coverage.
o If you kill all "Predicate" mutants (replacing if (p) with if (True) and if (False)), you
achieve Edge Coverage.
• Mutation vs. Logic Coverage:
15
 o Mutation generally subsumes Clause Coverage and Predicate Coverage.
o It also subsumes General Active Clause Coverage (GACC).
o However: It does not usually subsume Combinatorial Coverage or CACC/RACC, because those require
specific pairs of tests, whereas mutation just requires one test per mutant.

The Cost

The main drawback of mutation testing is cost. A large program can generate thousands of mutants. Running the full
test suite against every single mutant is computationally expensive.

Week 10
Object-oriented (OO) software introduces specific testing challenges because it shifts complexity from the algorithms
to the connections between components.

Key OO Features Affecting Testing

1. Abstraction: Classes hide data. We need to test the interface, not just the internals.
2. Inheritance: Classes reuse code from parents. Testing a parent class doesn't guarantee the child class works
(because of overriding).
3. Polymorphism: A variable declared as type Animal might actually hold a Dog or Cat at runtime. We must
test allpossible dynamic bindings.

The 4 Levels of Class Testing

Testing isn't just "Unit vs. System" anymore. For classes, we have levels:

1. Intra-method: Testing individual methods in isolation (Standard Unit Testing).

2. Inter-method: Testing how methods within the same class interact (e.g., push() then pop()).
3. Intra-class: Testing the class as a whole state machine.
4. Inter-class: Testing interactions between different classes (Integration).

Visualizing execution flow in OO systems is hard. The execution can "bounce" up and down the inheritance hierarchy.
The Yo-Yo Graph helps us see this.

Structure of the Graph

• Nodes: Methods (New, Inherited, and Overridden) for each class in the hierarchy.
• Edges: Method calls.
• The "Yo-Yo" Effect:
o You call d() in the Child.
o Child inherits d() from Parent. (Bounce Up).
o Parent's d() calls print().
o Child overrides print(). (Bounce Down).
o Execution jumps between levels, making it hard to track data flow anomalies.

OO features introduce specific types of bugs (faults) that procedural code doesn't have.

1. State Definition Anomaly (SDA)

• Scenario: A child class overrides a method (e.g., calc()) but fails to define a variable (e.g., total) that the
parent's version defined.
• Result: Other methods expecting total to be set will fail when called on the child object.

16
2. State Definition Inconsistency (SDIH)

• Scenario: A child class introduces a local variable with the same name as an inherited variable (Variable
Shadowing/Hiding).
• Result: The child method accidentally updates the local version, leaving the object's state (the inherited variable)
undefined or stale.

3. State Visibility Anomaly (SVA)

• Scenario: A child class overrides a method and tries to access a variable that is private in the parent.
• Result: This is usually a compile-time error, but can be subtle if scope changes during evolution.

4. Inconsistent Type Use (ITU)

• Scenario: An object is used as a Base type, then cast to a Child type, then back.
• Result: If the Child relies on state that the Base methods don't maintain, the object becomes corrupt.

Testing how classes talk to each other (Coupling) is trickier with Polymorphism.

Coupling Sequence

A sequence of calls involving two methods:

1. Antecedent ($m$): Defines a variable.

2. Consequent ($n$): Uses that variable.
3. Context ($f$): The method that calls both $m$ and $n$ on a shared object $o$.

The Polymorphic Challenge

If $o$ is polymorphic (e.g., declared as Shape but could be Circle or Square), we don't know which version
of $m$ and $n$will run until runtime.

• Polymorphic Call Set: The set of all possible methods that could execute for a given call.

OO Coverage Criteria

To test this thoroughly, we define new criteria:

1. All-Coupling-Sequences (ACS): Test every coupling sequence ($m$ then $n$) at least once.
2. All-Poly-Classes (APC): Test the sequence for every possible type the object can bind to (e.g., test
with Circle AND Square).
3. All-Coupling-Defs-Uses (ACDU): Ensure every definition of a coupling variable reaches every use.
4. All-Poly-Coupling-Defs-and-Uses (APDU): The strongest. For every polymorphic type, ensure every def
reaches every use.

We extend Mutation Testing to catch OO-specific bugs.

• AMC (Access Modifier Change): Change private to public (tests encapsulation).

• HVD (Hiding Variable Deletion): Delete a variable in the child to see if the parent's variable is picked up
(tests shadowing).
• OMD (Overriding Method Deletion): Delete an overridden method to force the parent's version to run.
• PCD (Parent Constructor Deletion): Delete the super() call in a constructor.
• ATC (Actual Type Change): Change new Child() to new Parent() to test polymorphism.

17
Week 11
Testing web apps is unique because of their architecture. They are distributed (Client vs. Server), stateless (HTTP), and
heterogeneous (HTML, JS, Java, PHP, Databases mixed together).

Key Characteristics

1. Separation: UI is on the client (Browser), Logic is on the Server.

2. Statelessness: The server doesn't remember you between clicks. We must hack state using Cookies and Session
objects.
3. Loose Coupling: Components interact via messages over the internet, making integration testing critical.

Levels of Testing

• Static Testing: Checking HTML for dead links and validation errors.
• Dynamic Client-Side: Testing the browser interface and inputs.
• Dynamic Server-Side: Testing the backend logic (Servlets, PHP, etc.).

The browser is the first line of defense, often validating inputs (e.g., "Age must be > 18"). But a malicious user can
bypass this. Bypass Testing checks if the server is robust enough to handle invalid inputs even if the client tries to stop
them.

How it Works

1. Capture: Save the HTML page to your local machine.

2. Modify: Edit the HTML to remove validation scripts (e.g., delete maxlength="3" or remove
the onsubmit="check()"script).
3. Inject: Add invalid data (e.g., a 500-character username, or SQL injection strings).
4. Submit: Send this "poisoned" form to the server.

• Goal: The server should gracefully reject the data, not crash or get corrupted.

User-Session Data Testing

Instead of manually inventing test cases, we can record real users.

1. Capture: Log every request a real user makes (URL, parameters, clicks).
2. Replay: Use a tool to re-send these requests to the server to see if it still behaves correctly.

• Benefit: This creates realistic test suites based on actual usage patterns.

Testing the server is white-box testing. But Control Flow Graphs (CFGs) are too low-level for web pages. We
use Atomic Sections instead.

What is an Atomic Section?

An Atomic Section is a chunk of HTML/Code that is either all sent to the client or none of it is. It's the smallest unit
of web output.

• Example: A JSP page might have:

o P1: Header HTML.
o P2: Database loop (prints table rows).
o P3: Footer HTML.
• We model the page as a sequence: P1 -> P2* -> P3.

18
Component Interaction Model (CIM)

The CIM is a graph where nodes are these Atomic Sections.

• We analyze the server code (e.g., a Servlet) to identify these sections.

• We build a graph showing how execution flows between them (Sequence, Selection, Iteration, Aggregation).
• Coverage: We try to cover all paths through this CIM graph to ensure the web page is generated correctly in all
scenarios.

Application Transition Graph (ATG)

The ATG is a "Zoomed Out" view.

• Nodes: Entire Web Pages (or Components like Servlets).

• Edges: Transitions (Links, Form Submissions, Redirects).
• Testing: We traverse the ATG to ensure we can reach every page and that navigation flows correctly (e.g.,
Login -> Home -> Logout).

Week 12
Once you fix a bug or add a new feature, how do you know you haven't broken something else? Regression Testing is
the process of re-testing the software to ensure that changes haven't introduced new errors.

The Process

1. Select: You don't always have to run every test. You select a subset of tests that are relevant to the changes
made.
2. Test Modified Code: Run the tests on the new version ($P'$).
3. Create New Tests: If the new feature ($P'$) has new logic, write new tests for it.
4. Maintain: Update the old test suite. Remove obsolete tests (e.g., if a feature was deleted) and add the new ones.

Test Selection Techniques

Running all tests ("Retest-All") is safe but slow. We use smarter techniques:

• Minimization: Select the smallest set of tests that cover the modified code. (Fast, but risky).
• Data-Flow Techniques: Select tests that exercise "def-use pairs" that were modified.
• Safe Techniques: Guarantee that you select every test that could possibly reveal a fault in the modified code
(e.g., selecting all tests that reach the modified statement).

Traditionally, we code first and test later. Test Driven Development (TDD) flips this.

The TDD Cycle (Red-Green-Refactor)

1. Red: Write a test case for a small piece of functionality before there is any code. It will fail (compile error or
assertion error).
2. Green: Write just enough code to make that specific test pass. Don't worry about quality yet.
3. Refactor: Clean up the code. Remove duplication, improve structure. Ensure the test still passes.

• Repeat: Do this for every tiny requirement (User Story).

Pros and Cons

19
 • Pros: You build a high-coverage test suite automatically. Debugging is minimal because you catch errors
instantly.
• Cons: It feels slow at first. It requires discipline. It is hard to apply to legacy code or complex GUIs.

Functional testing checks what the system does. Non-Functional Testing checks how well it does it.

The "-ilities"

• Performance: Can it handle the load?

o Load Testing: Testing under expected normal load.
o Stress Testing: Testing under extreme load (breaking point).
o Soak Testing: Running for a long time to find memory leaks.
o Spike Testing: Sudden bursts of users.
• Security: Confidentiality, Integrity, Availability. Testing for unauthorized access, encryption failures, and
backdoors.
• Scalability: Can it grow? (e.g., adding more servers).
• Interoperability: Does it work with other systems (Browsers, OS, 3rd party APIs)?

How do we know if the software is "good"? We measure it using Software Metrics.

Categories of Metrics

1. Product Metrics: Measure the code itself.

o Examples: Lines of Code (KLOC), Cyclomatic Complexity, Depth of Inheritance Tree.
2. Process Metrics: Measure the development activity.
o Examples: Defect Removal Effectiveness (DRE), Defect Density (Bugs per KLOC).
3. Project Metrics: Measure the team and schedule.
o Examples: Cost, Team size, Productivity.

Key Quality Indicators

• Defect Density: High density usually means poor quality code.

• Mean Time To Failure (MTTF): How long does it run before crashing? Critical for safety systems.
• Backlog Management Index (BMI): Are we fixing bugs faster than they are arriving? (If BMI < 100%, the
backlog is growing).

20