Skip to content

Atomicity detection and regression test generation through Feedback driven random test generation

Jump to bottom
Geoff-Laptop edited this page Apr 18, 2016 · 28 revisions

-- Geoff Groos, Vivekumar Patel, Rafael Bradley

Abstract

Writing concurrency tests is enormously difficult: aside from the lack of expressiveness around parallelism and concurrency in popular testing frameworks, finding and laying-out the setup required to push a program into a state where it may violate atomicity rules is difficult. This makes a completely automated detection and generation-of-tests scheme for such a problem very attractive. We explore combining two existing frameworks, one test-generation software, Randoop, and another atomicity exploration software, Intruder, in an attempt to create a single cohesive concurrency-testing scheme, requiring only the binaries of the component under test. We show that with this approach one can discover problems in their classes.

Introduction

Writing tests that assert on the correct use of locks, monitors, immutable objects and thread-confinement is enormously difficult.

Below are two tests against the same component:

  • The first is a test that attempts to assert that a particular piece of functionality works. Notice the brevity.
  • The second is a test that attempts to assert that that same code works given a specific --previously problematic-- interleaving of two methods. Notice the length and increased complexity of the code.
  /////////////////////////////////////////////////
  // Test 1
  
  @Test
  public void followed_by_running_state_determineIfOptimizationContinues_should_recurse_once_and_return_true(){
     //setup
     OptimizerSynchronizationMarshaller marshaller = makeMarshaller();
     when(stateMachine.getState()).thenReturn(State.Pending, State.Running);
  
     //act
     boolean shouldContinue = marshaller.determineIfOptimizationContinues();
  
     //assert
     assertThat(shouldContinue).isTrue();
     assertThat(marshaller.acknowledgements).containsExactly(pendingState);
     verify(stateMachine, twice()).getState();
  }
  
  ////////////////////////////////////////////////
  // Test 2
  
  /**
   * This is a test to assert that the scheme handles contention between the optimizer and the HMI thread
   * in the Start-Order state well. In this state, whether we transfer back to Idle or on to Running
   * is determined by a 'race'
   * (first order to be recieved -- more specifically the first one to lock the state machine)
   * between these two threads. This test asserts that, in one scenario, the locks work out correctly.
   */
  @Test(timeout = 1000)
  public void when_in_state_StartPending_and_a_StopOrder_happens_immediately_before_the_optimizer_tries_to_ack_should_become_idle() throws InterruptedException {
      //setup
      marshaller = makeMarshaller();
      marshaller.getStateMachine().currentState = StartPending;
  
      CountDownLatch stopOrderShouldContinueSignal = new CountDownLatch(1);
      CountDownLatch stopOrderIsReadyToContinueSignal = new CountDownLatch(1);
      CountDownLatch optimizerIsChecking = new CountDownLatch(1);
  
      LinqingList<Transfer> reportedTransfers = new LinqingList<>();
  
      marshaller.getStateMachine().addTransferListener((oldState, xfer, newState) -> {
  
          reportedTransfers.add(xfer);
  
          if(xfer == Transfer.StopOrder){
              //blocks us while we're in the middle of transferring, a vary precarious spot!
              stopOrderIsReadyToContinueSignal.countDown();
              ExceptionUtilities.failOnException(stopOrderShouldContinueSignal::await);
          }
      });
  
      Runnable hmiWorkload = () -> {
          marshaller.issueOrderAndAwaitAcknowledgement(Transfer.StopOrder);
      };
  
      Runnable optimizerWorkload = () -> {
          optimizerIsChecking.countDown();
          boolean shouldContinue = marshaller.determineIfOptimizationContinues();
          assertThat(shouldContinue).isFalse();
      };
  
      //act I : get HMI thread ordering change-back to stop
      Thread fauxHMIThread = syncingUtilities.asynchronously("fauxHMIThread", ThreadTag.HMI, hmiWorkload).get();
      stopOrderIsReadyToContinueSignal.await();
  
      //act II : get optimizer asking if it should continue while HMI thread is transferring states
      Thread fauxOptimizer = syncingUtilities.asynchronously("fauxOptimizer", ThreadTag.Optimizer, optimizerWorkload).get();
      optimizerIsChecking.await();
      syncingUtilities.sleepUnlessInterruptedFor(CheckDelay); //let optimizer *attempt* to continue
      Thread.State optimizerStateAfterChecking = fauxOptimizer.getState();
  
      //act III : let the HMI thread finish its transfer
      stopOrderShouldContinueSignal.countDown();
      fauxHMIThread.join();
      fauxOptimizer.join();
  
      //assert
      assertThat(marshaller.getState()).isEqualTo(Idle);
      assertThat(reportedTransfers).containsExactly(StopOrder);
      assertThat(optimizerStateAfterChecking).isEqualTo(Thread.State.BLOCKED);
      eventBus.shouldNotHaveBeenAskedToPost(OptimizationRunGroupHaltedEvent.class); //remember this test is pending -> stopped
  }
}

Such tests require a significant amount of time to write and consist of more complex constructs than even the code they're trying to test. Such difficulty and complexity has lead to a number of researchers investiating the possibility of leveraging dynamic code analysis to programmatically find the errors the above test is seeking, given a minimal driver.

Enter Intruder [Samak & Ramanathan], a tool that attempts to augment a traditional functional testing suite with atomicity violation detection and a system to generate tests that push a particular class into a state wherein it is likely to encounter a failure pretaining to the atomicity of its data. This tool dynamically analysis an existing set of functional tests, inspecting those tests access patterns in an attempt to find atomicity violations. Such a tool enables substantially better testing of the concurrency properties of a given class, but can require an extensive set of existing functional tests to be effective. Further, functional tests have their own set of biases and may not accurately reflect the actual use of the class in production, meaning using existing test suites may not enable Intruder to reveal all concurrency problems in a class.

Thus it would be very desirable to [Randoop]

Our goal is to use Randoop as a front end functional-test-generation scheme for Intruder, so that:

  • such a tool can be run without any existing tests, given only the class or jar files of the component under test and
  • such a tool avoids the bias of existing functional tests, testing possible access patterns rather than only those thought of by the author of the functional tests.

Background

In the discussion for Intruder, the authors mentioned future work in using test generation schemes to drive intruder.

Obviously, the quality of the multi-threaded tests is dependent on the input sequential seed testsuite. For example, if the code pertaining to an atomicity violation is not covered by the sequential test, our approach will be unable to synthesize a multithreaded test. Apart from developing a manual sequential seed testsuite as described above, we can also generate these testsuites using automatic test generators [including randoop].

We decided to explore the use of Randoop with Intruder. Unfortunately we found that the way they use Randoop was both not documented and not obvious; at best its inclusion in their project was as a build-time switch, something that we dont have access to since we can only work with their included binaries.

Given this, we wanted to see what would be required to create an end-to-end atomicity detection and test-generation scheme, given only the binaries for

Randoop

[randoops goal; reasonably wide adoption]

Intruder

[intruder -- mention that we didn't run down the quality of the atomicity violations themselves. Ultimately we took their number of 'violations' as final even if they didn't result in a bug.] One of the key insites of the intruder project is that given a set of tests that directly and minimally reproduce the access patterns for a particular object under test, many of the complexities associated with detecting atomicity problems from scratch disappear.

Implementation

Our initial strategy was to simply execute randoop on the libraries from [Intruder table 5], and pipe the results from randoop into intruder

for testFramework in $intruder_table5
  randoopTests = randoop --input $testFramework
  adaptedTests = adapter --input $randoopTests
  compiledRandoopTests = javac $adaptedTests
  intruderReport = intruder --input $compiledRandoopTests
  echo $intruderReport >> summary.txt

To accomplish this, we would need to:

  • create a script to run the above code
  • write an adapter, which we named porter, to convert the output from randoop to an input
  • configured javac to handle the various depenencies at the various stages of compilation
  • find matching atomicity violations detected by randoop and the existsing functional test scheme, map violations to defects.

The above script to run is implemented in runner.sh

The single biggest technical obstacle to driving intruder with randoop generated tests was that Randoop expects the results to be driven by JUnit and Intruder expects to have a single static main entry point. Unfortunately because of the analsysis strategy of intruder we were afraid that we might see artifacts if we simply wrote a main method wrapping the JUnit API to drive the tests created by randoop. To overcome this we wrote a small java utility porter that generates a main method wrapping target junit test methods created by randoop.

The next problem would be to ensure that the targeted component for test and its dependencies were available as necessary. Unfortunately this prooved to be consistently difficult, as we couldn't find a single solution to manage dependencies for all of the target test suites.

Finally we needed to catalog the discovered violations, and map them to defects. This also prooved very difficult as we quickly realized you had to have more knowledge about the tested frameworks than any of us had to come to any educated conclusions about the results from intruder. Thus we ignored this step for the bulk of our testing instead simply focusing on the count of defects discovered in the various testing schemes.

Experiments

[import problems, library problems, build problems. Build system wet-work. Ultimately correcting broken import headers was beyond the scope of this project]

[manually running tests] Table 1:

Test Original Randoop
intruder-funcitonal-test-1 0 0
intruder-funcitonal-test-2 1949, 1, 1 ERROR while running intruder
intruder-funcitonal-test-3 0, 0
intruder-funcitonal-test-4 1838, 1, 3 2321, 2, 5
intruder-funcitonal-test-5 0 0
intruder-funcitonal-test-6 2216, 1, 1 2791, 1, 1
intruder-funcitonal-test-7 2504, 1, 1 Randoop Unable to Generate Test
intruder-funcitonal-test-8 2633, 1, 1 3242, 1, 0
intruder-funcitonal-test-9 0 0
intruder-funcitonal-test-10 0 0
intruder-funcitonal-test-11 0 0
intruder-funcitonal-test-12 0 0
intruder-funcitonal-test-13 0 0
Colt, DynamicBin1D 159744, 9, 27 97559, 8, 19
Batik, CompositeGraphicsNode 35959, 7, 47 21217, 2, 2
Batik, CompositeGraphicsNode 35959, 7, 47 21441, 10, 7

[code coverage figures?]

Conclusion

[randoop + Intruder does generate results]

[randoop's coverage strategy doesn't necessarily map to atomicity discovery. Inherently it finds some, possibly the most common, violations but it does not find all of them.]

[Combining systems like this requires a huge amount of build-system wet-work]

Resulting set of guidelines

The bugs intruder detected related to failure in the scope of the locks and monitors acquired by components under test. In the Motivation section for Indruder, Figure 1 [intruder] requires the use of the mutable collection variables that are not sufficiently synchronized. This can be solved with a more elaborate use of locks or use of immutable data structures.

[others?]

References

[proposal: https://l.facebook.com/l.php?u=https%3A%2F%2Fcdn.fbsbx.com%2Fhphotos-xfa1%2Fv%2Ft59.2708-21%2F12726113_10153429612116046_1992673929_n.docx%2FProposal.docx%3Foh%3D2d09b7192c51c06c4a49e0c281492cf5%26oe%3D57168EBE%26dl%3D1&h=WAQH8u-0Q]

[intruder: http://drona.csa.iisc.ernet.in/~muralikrishna/publications/fse15.pdf]

[randoop: http://homes.cs.washington.edu/~mernst/pubs/feedback-testgen-icse2007.pdf]

Clone this wiki locally