Invariants and partial oracles

High-level goal

The high-level goal of this two-part exercise is to learn about program invariants and partial test oracles (property-based testing and metamorphic testing).

Part 1: Invariants

Instructions

1. Team up in groups of size 2, and self-assign to a group (In-class5-Invariants groupset) on Canvas. (If you are in a Canvas group of size 1, you can still submit.) In the past, groups found a pair-programming set up (in person or using screen-sharing for remote work) to be beneficial.

2. Familiarize yourself with the Daikon invariant detector

3. Run Daikon on a data structure example of your choice (other than the Stack example used in class). You may choose to run Daikon for any supported programming language (see installation instructions). (The example demoed in class used Daikon 5.7.2 and a Java 8 JDK.)

Questions

1. Provide a link to the chosen data structure. For this data structure and the corresponding Daikon output, give one example for a true invariant and one example for a discovered invariant that only holds for the given test suite.

2. Briefly explain which (if any) types of invariants discovered by Daikon are generally useful for testing and/or debugging (alternatively, briefly explain which types are not useful). There are no wrong answers: the provided answer is evaluated based on its justification not the expressed believe.

3. For a software system that you are familiar with, briefly explain that system and state at least two types of invariants of interest (useful for testing and/or debugging). Briefly explain whether and how these invariants can be dynamically discovered.

Part 2: Testing with partial oracles

This part has two variants (a and b). You may complete just one of them or both.

Instructions

Variant a

1. Clone an open-source repository of your choice for a non-trivial software system that is amenable to metamorphic testing. The software system may be written in any programming language, but it must provide a build system for compilation and testing.

2. For the chosen software system, design two metamorphic relations (MRs):

   • The two MRs must hold for arbitrary, well-formed inputs.
   • For at least one MR, the output relation must not be the identity function.

3. Implement your two MRs as test-case generators, which take an initial test case as input and produce a follow-up test case as output.

4. Based on the designed MRs, automatically generate a few test cases and execute them. (For the initial test cases, you may rely on random input generation, any existing test cases, or manually created test cases.)

5. Optional: Assess the efficacy of the designed MRs using mutation analysis. That is, mutate the software system and compute the mutant-detection rate for the test cases generated by the MRs. (Mutation-analysis frameworks are available for many languages, including Java, C#, JavaScript, and Python.)

Variant b

1. Choose a non-trivial online software system for classification (e.g., text, images, code, etc.).

2. For the chosen software system, design three metamorphic relations (MRs):

   • The three MRs must hold for arbitrary, well-formed inputs.
   • For at least two MRs, the output relation must not be the identity function.

3. Based on the designed MRs, generate a few test cases, execute the online system, and observe its output. (You may automate the test-case generation.)

Questions

4. Describe the chosen software system and justify for each of the designed MRs why it must hold for arbitrary, well-formed inputs.

5. Briefly summarize your observations about testing with MRs and state at least two characteristics of effective MRs. You may reason about the specific MRs you designed or MRs in general.

Deliverables

1. A plain-text (or PDF) file with your answers to the 5 questions above. Please list all group members.

Steps for turn-in

One team member should upload the deliverables to Canvas.