Automated fixing of wrong assumptions on underdetermined specifications

Zhang, Peilun

Permalink

https://hdl.handle.net/2142/108343 Copy

Description

Title

Automated fixing of wrong assumptions on underdetermined specifications

Author(s)

Zhang, Peilun

Issue Date

2020-05-12

Director of Research (if dissertation) or Advisor (if thesis)

• Marinov, Darko
• Stodden, Victoria

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Software testing
• Regression testing
• Flaky test

Abstract

Software specifications assist in the implementation of software by stating expected software behavior. Many software specifications are deterministic, i.e., the software produces the same output for the same input. However, some specifications are underdetermined, meaning that the software may produce different outputs given the same input. Underdetermined specifications are not uncommon because they can offer some advantages over deterministic ones. For instance, underdetermined specifications can allow for optimization as developers can be more flexible when conducting speed optimization. We encounter potential problems when deterministic implementations produce different outputs. For example, even though the Java standard library does not specify the order of elements returned by method getDeclaredFields, prevailing implementations, like Oracle JDK 1.8, return fields in the order as they are listed in the class file (which is itself the order in which they are in the source file when using the standard javac compiler). There is no reason to expect the implementation will not change because the specifications allow flexibility, and popular vendors have historically changed the implementations of several widely used library methods. Unfortunately, software library users may write code that relies on a specific implementation rather than on the specification, e.g., assuming mistakenly that the order of elements cannot change in the future. If users write software tests that involve methods with underdetermined specifications, those tests can therefore produce unexpectedly non-deterministic outputs, meaning that tests can intermittently fail or pass without changing the production and test code (but changing the library code). Prior work proposed the NonDex approach to proactively detect such wrong assumptions in the production and test code. The goal of this thesis is to propose automated code changes that help resolve these issues by either making the output deterministic or making the test assertion order-agnostic. We present a novel approach, called DexFix, to fix wrong assumptions on underdetermined software specifications in an automated way. To demonstrate these efforts, we run the NonDex tool on 200 open-source Java projects and detect 275 tests that fail due to wrong assumptions. We find that the majority of failures are based on HashMap/HashSet class iterations and the getDeclaredFields method. We provide several new automated fix strategies that can fix these violations in both the production and test code, which are implemented in the DexFix tool. Our experiments show that DexFix proposes fixes for 101 tests from our 275 tests. We have reported fixes for 84 tests to the developers as GitHub pull requests: 57 have been merged, with only 2 rejected, and the remaining are pending.

Graduation Semester

2020-05

Type of Resource

Thesis

Permalink

http://hdl.handle.net/2142/108343

Copyright and License Information

Copyright 2020 Peilun Zhang

Owning Collections