L4

Question 1

Korat

Answer 1

whitebox, systematic testing tool for linked data structures

Question 2

Randoop

Answer 2

feedback-directed random testing for classes and libraries

creates new test guided by feedback from previous tests

Question 3

problem with automated testing

Answer 3

• inf tests
• even a finite subset can be huge
• need to be concise (avoid illegal and redundant tests) and diverse (give good coverage)

Question 4

small test case hypothesis

Answer 4

• if there is any test that cause the program to fail, there is small such test.

Question 5

how to generate inputs

Answer 5

• use the types
• class declaration shows what values can fill each field
• enumerate all possible deviation deviations from a fix set of objects

Question 6

Korat algorithm

Answer 6

• generates all possible input up to user-defined k
• discards inputs where pre-condition is false
• runs the program on remaining inputs
• check results using post-condition

Question 7

The total number of candidate vectors/shapes for a at-most 3 node binary tree in Korat?

Answer 7

7 fields, 4 choices each -> 4^7, but we are only interested in 9 of them

Question 8

The total number of candidate vectors/shapes for an at-most k node binary tree in Korat?

Answer 8

(k+1)^(2k+1)

Question 9

steps Korat follows

Answer 9

• initiate candidate vectors (all null)
• expand the last field accessed by the pre-condition
• backtrack if all possibilities for a field are exhausted

Question 10

Korat’s strength

Answer 10

• when we can enumerate all possibilities

- for linked data structures, small, easily specified procedures, unit testing

Question 11

Korat’s weakness

Answer 11

• when enumeration is weak

- only as good as the pre and post conditions

Question 12

Randoop’s recipe

Answer 12

randomly create new test guided by feedback from previously created tests

• build new sequences incrementally
• as soon as a sequence is created, execute it
• use results to guide test generation toward sequences that create new obj states

Question 13

Randoop’s input

Answer 13

• classes under test
• time limit
• set of contract

Question 14

condition for violating test cases to exist in the output of Randoop

Answer 14

• no contract should be violated up the the end of the sequence
• the final assertion should fail

Question 15

Randoop’s algorithm

Answer 15

Create new sequence:

• randomly picks a method m returning T
• for each Ti, pick Si from components that construct object Vi
• assemble n randomly picked sequences to create Snew

Classify new sequence: discard/ output as test/ add to components

Question 16

illegal sequence

Answer 16

• sequences that crash before the contract is checked

- violates some precondition during execution

Question 17

redundant sequences

Answer 17

• randoop maintains a set of all objects created in execution of each sequence
• new seq is redundant if obj created in its execution belongs to the above set.
• could also use more sophisticated state equivalent methods

Question 18

use type information to guide test generation is a characteristic of

Answer 18

both Korat and Randoop

Question 19

each test is fully independent of the past tests is a characteristic of

Answer 19

neither

Question 20

generate test deterministically is a characteristic of

Answer 20

Korat

Question 21

suited to test method seq is a characteristic of

Answer 21

Randoop

Question 22

Avoid generating redundant test is a characteristic of

Answer 22

both Korat and Randoop

Question 23

if a list function works for lists of length 0 to 3, what conclusion can we draw?

Answer 23

it probably works for all lists

Question 24

korat’s precondition technique

Answer 24

• add code to observe its actions
• record fields accessed by the pre-condition
• if the pre-condition doesn’t access a field, it doesn’t depend on the field.

Question 25

korat’s enumerating tests

Answer 25

• shapes are enumerated by associated vectors
  + initial: all field null
  + next shape generated by expanding last field accessed in pre-condition & backtracking if all possibilities for a field are exhausted

Question 26

key idea for enumerating tests

Answer 26

• never expand parts of input not examined by pre-condition

- cleverly checks for and discard shapes isomorphic to previously generated shapes

Question 27

Randoop stands for

Answer 27

Random tester for object-oriented programs

Question 28

problem with uniform random testing

Answer 28

creates too many illegal and redundant tests

Question 29

Randoop’s output

Answer 29

contact-violating test cases

Question 30

randoop redundant sequence technique’s drawbacks

Answer 30

• might miss bugs that can only be trigger by extending a sequence
• might also mistakenly redeem redundant sequences as not redundant

Question 31

why didn’t automated test generation become popular earlier?

Answer 31

• earlier program languages has weak type systems while automated test generation relies heavily on type information.
• contemporary languages fit better for test generation