Detecting Assumptions on Deterministic Implementations of Non-deterministic Specifications

August Shi, Alex Gyori, Owolabi Legunsen, Darko Marinov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Some commonly used methods have nondeterministicspecifications, e.g., iterating through a set canreturn the elements in any order. However, non-deterministicspecifications typically have deterministic implementations, e.g.,iterating through two sets constructed in the same way mayreturn their elements in the same order. We use the termADINS code to refer to code that Assumes a DeterministicImplementation of a method with a Non-deterministic Specification. Such ADINS code can behave unexpectedly whenthe implementation changes, even if the specification remainsthe same. Further, ADINS code can lead to flaky tests-teststhat pass or fail seemingly non-deterministically. We present a simple technique, called NONDEX, for detectingflaky tests due to ADINS code. We implemented NONDEX forJava: we found 31 methods with non-deterministic specificationsin the Java Standard Library, manually built non-deterministicmodels for these methods, and used a modified Java VirtualMachine to explore various non-deterministic choices. We evaluatedNONDEX on 195 open-source projects from GitHub and 72student submissions from a programming homework assignment.NONDEX detected 60 flaky tests in 21 open-source projects and110 flaky tests in 34 student submissions.

Original languageEnglish (US)
Title of host publicationProceedings - 2016 IEEE International Conference on Software Testing, Verification and Validation, ICST 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages80-90
Number of pages11
ISBN (Electronic)9781509018260
DOIs
StatePublished - Jul 18 2016
Event9th IEEE International Conference on Software Testing, Verification and Validation, ICST 2016 - Chicago, United States
Duration: Apr 10 2016Apr 15 2016

Publication series

NameProceedings - 2016 IEEE International Conference on Software Testing, Verification and Validation, ICST 2016

Other

Other9th IEEE International Conference on Software Testing, Verification and Validation, ICST 2016
CountryUnited States
CityChicago
Period4/10/164/15/16

Keywords

  • Flaky Tests
  • Regression Testing
  • Specification

ASJC Scopus subject areas

  • Software
  • Safety, Risk, Reliability and Quality

Fingerprint Dive into the research topics of 'Detecting Assumptions on Deterministic Implementations of Non-deterministic Specifications'. Together they form a unique fingerprint.

Cite this