Detecting Assumptions on Deterministic Implementations of Non-deterministic Specifications

Detecting Assumptions on Deterministic Implementations of Non-deterministic Specifications August Shi, Alex Gyori, Owolabi Legunsen, Darko Marinov 4/12/2016 ICST 2016 Chicago, Illinois CCF-1012759, CCF-1409423, CCF-1421503, CCF-1439957

Example Code and Test /** This class makes no guarantees as to the order of the map */ public classjava.util.HashMap public class Book { String author; String title; public Book(String author, String title) { this.author = author; this.title = title; } publicString getStringRep() { JSONObject j = new JSONObject(); // JSONObject extends java.util.HashMap j.put("author", this.author); j.put("title", this.title); return j.toString(); } } // toString() iterates through entries publicclass BookTest { @Test publicvoid testGetStringRep() { Book b = new Book("A", "T"); assertEquals("{\"author\":\"A\",\"title\":\"T\"}", b.getStringRep()); } } 2

Non-deterministic Specifications A specification (spec) that allows multiple implementations with different outputs for a given input Good: Allow freedom of implementation Although specs are non-deterministic, underlying implementations are often deterministic Bad: Code that Assumes a Deterministic Implementation of a Non- deterministic Specification (ADINS) Such code can behave unexpectedly when run using a different underlying implementation that still satisfies the spec Such code can be a cause of flaky tests 3

NonDex (Non-Deterministic Explorer) A simple technique for detecting ADINS code Library outputs calls Test Method with Non-deterministic Spec outputs calls Method with Deterministic Spec 4

NonDex (Non-Deterministic Explorer) A simple technique for detecting ADINS code Library NonDex Model Implementation 1 NonDex outputs calls Implementation 2 Test Implementation n outputs calls Method with Deterministic Spec 5

NonDex (Non-Deterministic Explorer) A simple technique for detecting ADINS code Explore: Implementation 1 Implementation n Library NonDex Model Implementation 1 NonDex outputs calls Implementation 2 Test Implementation n outputs calls Method with Deterministic Spec 6

Finding Non-deterministic Specs Searched Java Standard Library for method specs that are non-deterministic 1. Searched JavaDocs for these keywords: order , deterministic , not specified 2. Searched for methods that return an array Examined JavaDocs for all found methods Identified 31 method specs that are non-deterministic 7

Some Non-deterministic Specs java.util.Set.iterator(): Returns an iterator over the elements in this set. The elements are returned in no particular order java.util.HashMap.entrySet(): Returns a Setview of the mappings contained in this map This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time. java.lang.Class.getDeclaredMethods(): Returns an array containing Method objects reflecting all the declared methods of the class The elements in the returned array are not sorted and are not in any particular order. 8

NonDex Models for Specs Class Permute: method returns array/collection whose order is not specified Methods Category java.lang.Object hashCode Random java.util.HashMap* keySet, values, entrySet Permute java.util.ConcurrentHashMap* NonDex model explores different permutations of elements keySet, values, entrySet, keys, elements Permute java.io.File list, listFiles, listRoots Permute java.lang.Class getClasses, getDeclaredMethods, Permute java.lang.reflect.Method getParameterAnnotations Permute java.lang.reflect.Field getDeclaredAnnotations Permute java.text.DateFormatSymbols getAvailableLocales, getZoneStrings Permute, Extend java.text.BreakIterator getAvailableLocales Permute java.text.DecimalFormatSymbols getAvailableLocales Permute java.text.NumberFormat getAvailableLocales Permute java.text.DateFormat getAvailableLocales Permute * Non-determinism is actually in internal iterator, exposed to outside by these methods 9

Different Levels of Non-determinism Some assumptions of determinism may be acceptable For example, if two calls of iterator() are made on the same, unmodified Set, should the iteration orders be the same? We introduce four levels for NonDex to Permute ONE: assumes deterministic implementation, but shuffles once, potentially different than underlying implementation EQ: shuffles differently only when objects are not equal ID: shuffles differently only when object address is different, or object has been modified FULL: shuffles differently with every call 10

01. Set<Integer> s = new HashSet<Integer>(); 02. s.add(1); s.add(2); 03. Integer[] a = s.toArray(); 04. // assertArrayEquals(a, newInteger[]{1, 2}); // FULL, ID, EQ, ONE can fail 05. 06. // assertArrayEquals(a, s.toArray()); // FULL can fail 07. 08. s.contains(1); 09. // assertArrayEquals(a, s.toArray()); // FULL can fail 10. 11. s.add(3); s.remove(3); 12. // assertArrayEquals(a, s.toArray()); // FULL, ID can fail 13. 14. Set<Integer> t = new HashSet<Integer>(); 15. t.add(1); t.add(2); 16. // assertArrayEquals(a, t.toArray()); // FULL, ID can fail 17. 18. Set<Integer> u = new HashSet<Integer>(); 19. u.add(3); u.add(4); 20. Integer[] b = u.toArray(); 21. // assertEquals(a[0] < a[1], b[0] < b[1]); // FULL, ID, EQ can fail 11

NonDex Model Exploration In our prototype, NonDex models use seeds to control which implementations to use Models use seeds for different java.util.Random calls that represent the different implementations We execute code with NonDex multiple times, each using different seeds, to explore different behaviors 12

Research Questions How many flaky tests are due to ADINS code? In open-source projects? In student submissions? How many seeds should be used to likely find all flaky tests due to ADINS code? How often are developers making acceptable assumptions about non-determinism? 13

Experimental Setup Tool (also called NonDex) is implemented for OpenJDK 8 Models implemented by modifying code in OpenJDK 8 Use modified NonDex JVM in place of the OpenJDK 8 JVM Evaluation projects: 195 open-source GitHub projects that build with Maven First run each project s tests with 10 different seeds If a test with different behavior is found, run project s tests with 100 different seeds 72 student submissions from Software Engineering I course Run each student submission s tests with 100 different seeds 14

Open-source Project Results FULL ID EQ ONE Flaky Tests Detected 60 54 54 54 Total Seeds Detecting 4362/6000 3744/6000 3643/6000 3590/6000 Min Seeds Detecting 8 0 0 0 Max Seeds Detecting 100 100 100 100 15

Subset of Flaky Tests Detected Project TestClass#TestName FULL ID EQ ONE reflectasm FieldAccessTest#testIndexSetAndGet 48 0 0 0 joda-time TestDateTimeZone#testGetShortName 35 53 53 53 oryx TextUtilsTest#testJSONMap 51 52 60 53 visualee JPAExaminerTest#testFindAndSetAttributes 8 5 5 6 commons-cli OptionGroupTest#testToString 42 0 0 0 commons-lang MultilineRecursiveToStringStyleTest#boolArray Probability of not detecting in 10 runs is (1 100)10 = 0.434 Greater than 0.5 chance of detecting 100 100 100 100 easy-batch PrinterTest#testPrettyPrinting 69 73 54 53 8 scribe-java MapUtilsTest#shouldPrettyPrintMap 97 94 97 97 geoserver-manager GSLLayerEncoder21Test#testMetadata 84 81 71 100 handlebars.java TagTypeTest#collectSectionAndVars 100 100 100 100 jscep DefaultCertStoreInspectorTest#example 92 94 59 53 junit MethodSorterTest#testJvmMethodSorter 100 0 0 0 org-json TestSuite#testJSONStringerObject 79 77 83 84 slf4j EventLoggerTest#testEventLogger 100 0 0 0 CollectionTests#testBasicSets 100 96 91 84 wsdoc 16

Example Flaky Test (from commons-cli) publicclass OptionGroupTest { publicvoid testToString() { OptionGroup g1 = new OptionGroup(); g1.addOption(new Option(null, "foo", false, "Foo")); g1.addOption(new Option(null, "bar", false, "Bar")); if (!"[--bar Bar, --foo Foo]".equals(g1.toString())) { assertEquals("[--foo Foo, --bar Bar]", g1.toString()); } ...}} publicclass OptionGroup ... { Map om = new HashMap(); public OptionGroup addOption(Option option) { om.put(option.getKey(), option); returnthis;} publicString toString() { StringBuilder buff = newStringBuilder(); Iterator iter = getOptions().iterator(); buff.append("["); while (iter.hasNext()) { /* ... populate buff with the values in iter ... */ } return buff.toString();}} 17

Student Submission Results FULL ID EQ ONE Flaky Tests Found 110 88 34 34 Total Seeds Detected 8159/11000 6785/11000 2031/11000 1827/11000 Min Seeds Detected 37 0 0 0 Max Seeds Detected 100 100 81 78 Flaky tests mostly due to asserting result of method call is exactly equal to some String (similar beginning example) We also used Java PathFinder (JPF) to do systematic exploration Replace java.util.Random calls with JPF choice points Using JPF choice points did not detect any more flaky tests than using java.util.Random (with 100 seeds) 18

Conclusion Non-deterministic specs give freedom to implementers, but code that assumes deterministic implementations (ADINS) leads to undesirable behavior We develop a technique NonDex to detect ADINS code We detected 60 flaky tests in open-source projects, and 110 flaky tests in student submissions We plan to further research how to better detect, debug, and repair ADINS code We plan on releasing NonDex, but are currently having issues with OpenJDK/Oracle licensing August Shi: awshi2@illinois.edu 19

BACKUP 20

class HashMap { ... class HashIterator { ... /* Rename hasNext() -> original_hasNext() */ /* Rename nextNode() -> original_nextNode() */ Iterator<Node> NonDex_iter; HashIterator() { ... List<Node> original = new ArrayList<>(); while (original_hasNext()) original.add(original_nextNode()); NonDex.shuffle(original, (NonDex.level == ID) ? System.identityHashCode(HashMap.this) + modCount : (NonDex.level == EQ) ? HashMap.this.hashCode() : 0); NonDex_iter = original.iterator(); } publicfinalboolean hasNext() { return NonDex_iter.hasNext(); } final Node nextNode() { if (modCount != expectedModCount) thrownew ConcurrentModificationException(); current = NonDex_iter.next(); returncurrent; } } } 21

class NonDex { staticintlevel; // FULL, ID, EQ, or ONE intseed = ...; static Random full = new Random(seed); publicstatic List shuffle(List l, int v) { int size = l.size(); Random rand = (level == FULL) ? full : // Full (level == ID) ? new Random(seed + v) : // Same object (level == EQ) ? new Random(seed + v) : // Equal object (level == ONE) ? new Random(seed); // Once for (int i = 0; i < size - 1; i++) { int s = rand.getNext(i, size); if (s == i) continue; T obj = l.get(i); l.set(i, l.get(s)); l.set(s, obj); } return l; } } 22

Example Flaky Test (from scribe-java) publicclass MapUtilsTest { @Testpublicvoid shouldPrettyPrintMap() { Map map = new HashMap<>(); map.put(1, "one"); map.put(2, "two"); map.put(3, "three"); map.put(4, "four"); assertEquals( "{ 1 -> one , 2 -> two , 3 -> three , 4 -> four }", MapUtils.toString(map)); } } publicclass MapUtils { publicstaticString toString(Map map) { ... StringBuilder result = newStringBuilder(); for (Map.Entry entry : map.entrySet()) { result.append(String.format(", %s -> %s ", entry.getKey().toString(), entry.getValue().toString())); } return "{" + result.substring(1) + "}"; } } 23