- Forward


Software Verification
An Introduction to Code Reviews and Testing


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Review
Back SMYC Forward
  • Validation:
    • The process of determining if a product (or its specification) satisfies stakeholders' needs and desires ("Are we building the right product?")
  • Verification:
    • The process of determining if a product (or its specification) satisfies those needs and desires properly ("Are we building the product right?")
Terminology
Back SMYC Forward
  • Defect:
    • Any undesirable aspect of a product
  • Failure:
    • A deviation between a product's actual behavior and intended behavior (e.g., a feature that is missing or incorrect)
  • Fault:
    • A defect that could (or does) give rise to a failure
  • Trigger Condition:
    • A condition that cause a fault to result in a failure
  • Symptom:
    • A characteristic of a failure (that helps you recognize that a failure has occurred)
Terminology (cont.)
Back SMYC Forward
  • A Missing Term:
    • "Bug"
  • Why Is It Omitted?
    • People do not use the term "bug" consistently
  • Implications:
    • We will use the term "debugging" but will not use the term "bug" (except casually)
Terminology (cont.)
Back SMYC Forward
     // An example in pseudocode

     a = getNextInt();
     b = getNextInt();
     c = a/b;
     print(c);
  
  • Fault?
    Not checking the value of b and not providing a default value for b or c
    Expand
  • Trigger Condition?
    b having the value 0
    Expand
  • Symptom?
    Depending on the language, the symptom might be termination (e.g., because of a divide by 0 exception) or an infinite/undefined/NaN value
    Expand
  • Failure?
    The program does not produce the correct output
    Expand
Terminology (cont.)
Back SMYC Forward

Nerd Humor

/imgs
(Courtesy of xkcd)
Types of Faults
Back SMYC Forward
  • Algorithmic: A block of code does not generate the proper output for a given input
    • Precision: The computation is not performed to the desired accuracy
    • Checking: The inputs are not validated before the computation is performed
    • Stress/Overload: The problem occurs when data structures are filled past their capacity
    • Assignment: Fault in variable/data structure initialization
  • Throughput/Performance: A block of code does not perform at the required speed
    • Timing/Coordination: Involves shared resources
  • Recovery: A block of code does not respond to another fault appropriately
Code Analysis
Back SMYC Forward
  • Code Reviews:
    • The source code is manually compared to the specifications (in a heavyweight process) or acceptance criteria (in an agile process)
  • Static Analysis:
    • The automated review of a program (or a part of a program) "before" it is executed (using the source code or the compiled/partially-compiled code)
  • Dynamic Analysis:
    • The review of a program (or part of a program) while it is running/executing
Code Reviews
Back SMYC Forward
  • Desk Checking:
    • The programmer reads through the program (and traces the execution) themself
  • Code Walkthrough:
    • The programmer gives their code to a review team and leads an informal discussion
  • Code Inspection:
    • A review team checks the code against a prepared list of concerns
Facilitating Code Reviews
Back SMYC Forward
  • In the Source Code:
    • Include comments that refer to the specifications/acceptance criteria
  • External Documents:
    • Keep a checklist that tracks which specifications/acceptance criteria have been satisfied
Examples of Static Analysis
Back SMYC Forward
  • Style Checking:
    • Syntactically correct but stylistically inappropriate
  • Construct Checking:
    • "Suspicious" constructs (e.g., variables used but not initialized, division, unused variables, constant logical expressions, etc...)
    • Non-portable constructs
    • Memory allocation inconsistencies
  • Software Metrics:
    • Thousand Lines of Code (KLOC)
    • Halstead Complexity (calculated from the number of operators and operands)
Examples of Dynamic Analysis
Back SMYC Forward
  • Development/Construction Testing:
    • Determining if a program is correct by executing it
  • Performance Analysis (a.k.a. Profiling):
    • Determining the space (i.e., memory) requirements and time requirements of a program
Development/Construction Testing - The Stages
Back SMYC Forward
  • Unit Testing (or Module/Component Testing):
    • A component is tested on its own (in isolation from any other components)
  • Integration Testing:
    • Components are tested in combination
  • System Testing:
    • The product is tested in its entirety, that is, all of the components that comprise the (current increment of the) product are tested in combination
Development/Construction Testing - The Participants
Back SMYC Forward
  • Unit Testing (or Module/Component Testing):
    • Typically must be performed by "programmers"
  • Integration Testing:
    • Typically must be performed by "programmers"
  • System Testing:
    • Can be performed by "testers" (either in-house or potential users)
Testing - Terminology
Back SMYC Forward
  • Test/Test Case/Test Point:
    • A particular choice of inputs (and expected output)
  • Test Suite:
    • A collection of tests
  • Test Harness/Test Framework:
    • A way to write, organize, and run repeatable tests
Testing - Approaches
Back SMYC Forward
  • Black Box (or Closed Box):
    • The tester has information about the form of the inputs and the outputs, but not about the "internals" of the component being tested
  • White Box (or Clear/Open Box):
    • The tester knows the internal details of the component being tested
Testing - Clear-Box Unit Testing
Back SMYC Forward
  • Statement Coverage:
    • Make sure every statement is executed
  • Branch (a.k.a., Decision) Coverage:
    • Make sure every "branch" (resulting from conditionals) is executed
  • Condition Coverage:
    • Make sure both values in every Boolean expression (with \(N\) sub-expressions in a single conditional) is covered (Note: There are \(2*N\) conditions.)
    • (Unfortunately, this is what EclEmma/JaCoCo calls branch coverage!)
  • Multiple Condition Coverage:
    • Make sure every possible combination of every Boolean expression (with \(N\) sub-expressions in a single conditional) is covered (Note: In the worst case, there are \(2^N\) multiple conditions.)
  • Path Coverage:
    • Make sure every path through the code is executed
Testing - Coverage (cont.)
Back SMYC Forward
   // An example in pseudocode

   int calculate(int x, int y)
   {
       int        a, b;

       a = 1;                 // S1
       if (x > y)             // S2
          a = 2;              // S3
       x++;                   // S4
       b = y * a;             // S5
       if (y <= 0)            // S6
         b++;                 // S7
       return b;              // S8
    }
  
coverage-example
Testing - Coverage (cont.)
Back SMYC Forward
   // An example in pseudocode

   int calculate(int x, int y)
   {
       int        a, b;

       a = 1;                 // S1
       if (x > y)             // S2
          a = 2;              // S3
       x++;                   // S4
       b = y * a;             // S5
       if (y <= 0)            // S6
         b++;                 // S7
       return b;              // S8
    }
  
  • Covering Every Statement:
    • calculate(5, -2) (S1-S2-S3-S4-S5-S6-S7-S8)
  • Covering Every Branch (S3 and Not S3, S7 and Not S7):
    • calculate( 5, 2) (S1-S2-S3-S4-S5-S6-S8)
    • calculate(-2, -1) (S1-S2-S4-S5-S6-S7-S8)
  • Covering Every Path (S3 then Not S7, Not S3 then Not S7, S3 then S7, Not S3 then S7):
    • calculate( 5, 2) (S1-S2-S3-S4-S5-S6-S8)
    • calculate(-2, 5) (S1-S2-S4-S5-S6-S8)
    • calculate(-1,-2) (S1-S2-S3-S4-S5-S6-S7-S8)
    • calculate(-2,-1) (S1-S2-S4-S5-S6-S7-S8)
Testing - Why Multiple Condition Coverage is Difficult in Practice
Back SMYC Forward
  • The Worst Case:
    • Since each simple Boolean expression takes on two possible values it follows that compound expressions have \(2^N\) multiple conditions
    • Example: (x > 0) && (y > 0) has 4 conditions
  • In Reality:
    • There may be fewer conditions, but this is difficult to determine using static analysis tools
    • Example: (x > 0) && (x < 100) really only has three multiple conditions
Testing - Black-Box Unit Testing
Back SMYC Forward
  • An Obvious Approach to Consider:
    • Supply the unit with all possible inputs (after all, it can be done in a loop and computers are fast)
  • Some Realities:
    • The number of test cases can be very large!
    • How do you check the results?
Testing - Black-Box Unit Testing (cont.)
Back SMYC Forward
  • Random Testing:
    • Generate test cases randomly
  • Heuristic Testing:
    • Generate test cases using "rules of thumb" (e.g., boundary value analysis)
  • Specification-Based Testing:
    • If they are available, generate test cases based on the specifications.
Testing - Black-Box Unit Testing (cont.)
Back SMYC Forward
  • Value Heuristics:
    • Extreme values are thought to be the most likely to cause a failure (e.g., include a test case with a large positive value, a small positive value, 0, a large negative number, a small negative number)
    • Include type mismatches (e.g., characters for integers)
  • Array Heuristics:
    • Include a small array, large array, 0-length array, 1-length array
    • Include unsorted, sorted ascending, and sorted descending arrays
    • Include arrays with one value (e.g., all negative, all positive, all 0)
Testing - Black-Box Unit Testing (cont.)
Back SMYC Forward
  • File Name Heuristics:
    • Include multiple files with the same prefix.
    • Include multiple files with the same suffix (i.e., file type).
    • Include files that reverse the prefix and suffix.
  • String Heuristics:
    • Include strings that vary only in case (e.g., all upper case, all lower case, mixed case)
    • Include zero-length strings
    • Include long strings
    • Include short strings
    • Include strings that consist of one repeated character
    • Include strings that are in reverse order
    • Include strings that swap underscores and dashes
    • Include strings that swap ones and lower case ls
    • Include strings that swap zeros and Os
Black Box Testing: Enumerated Types
Back SMYC Forward
  • Exhaustive Testing:
    • If possible, test the attributes of all of the instances
  • A Warning:
    • Don't copy from the code to the tests, you'll just copy any errors (which is why this should be considered "black box")
Testing - Equivalence Classes
Back SMYC Forward
  • Definition:
    • A set of tests cases in which each element triggers the same failure
  • Importance:
    • If one can identify an equivalence class then there is no reason to include more than one test from the set
Testing - Integration Testing Strategies
Back SMYC Forward
  • Bottom Up:
    • Test all of the lowest level components first
    • Add components that use tested components
  • Top Down:
    • Test the top level component first (using stubs)
    • Add components called by the tested component(s)
  • Big Bang:
    • Test all components in isolation
    • Test the entire system
Testing - System Testing
Back SMYC Forward
  • Alpha Testing:
    • Scripted - the tester follows a well-defined set of steps (so that the test is repeatable) and records the failures
    • Open Ended - the tester uses the product in a "free form" fashion and records the failures
  • Beta Testing:
    • Open Ended - the user often reports their experiences using a bug-tracking system
From Testing to Debugging
Back SMYC Forward
  • Output of a Failed Test:
    • A symptom and one of the trigger conditions that gives rise to the symptom
  • Debugging:
    • Using the trigger condition to identify and correct the fault
Outcomes of Debugging
Back SMYC Forward
  • What Can Happen?
    • Fault corrected and no new fault introduced
    • Fault corrected and new fault introduced
    • Fault not corrected and no new fault introduced
    • Fault not corrected and new fault introduced
  • Real World Data:
    • As many as 30% of changes result in one of the three bad outcomes
    • Bad outcomes occur on average 10% of the time
    • Faults introduced during debugging are more difficult to identify and remove
Outcomes of Debugging (cont.)
Back SMYC Forward
  • Implications:
    • Carefully test fixes
    • Re-run old tests after fixing
  • Regression Testing:
    • The process of re-running all existing tests
There's Always More to Learn
Back -