Skip to end of metadata
Go to start of metadata

According to the Java API documentation [API 2014] for the Iterator.remove() method:

The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method.

Concurrent modification in single-threaded programs is usually a result of inserting or removing an element during iteration. Multithreaded programs add the possibility that a collection may be modified by one thread while another thread iterates over the collection. Undefined behavior results in either case. Many implementations throw a ConcurrentModificationException when they detect concurrent modification.

According to the Java API documentation [API 2014] for ConcurrentModificationException:

It is not generally permissible for one thread to modify a Collection while another thread is iterating over it. In general, the results of the iteration are undefined under these circumstances. Some Iterator implementations (including those of all the general purpose collection implementations provided by the JRE) may choose to throw this exception if this behavior is detected. Iterators that do this are known as fail-fast iterators, as they fail quickly and cleanly, rather that risking arbitrary, non-deterministic behavior at an undetermined time in the future.

...

Note that fail-fast behavior cannot be guaranteed because it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast operations throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: ConcurrentModificationException should be used only to detect bugs.

Reliance on ConcurrentModificationException is inadequate to prevent undefined behavior resulting from modifying an underlying collection while simultaneously iterating over the collection. The fail-fast behavior may occur only after processing an arbitrary number of elements. In Java Concurrency in Practice [Goetz 2006a], Goetz and colleagues note:

[Fail-fast iterators] are implemented by associating a modification count with the collection: if the modification count changes during iteration, hasNext or next throws ConcurrentModificationException. However, this check is done without synchronization, so there is a risk of seeing a stale value of the modification count and therefore...that the iterator does not realize a modification has been made. This was a deliberate design tradeoff to reduce the performance impact of the concurrent modification detection code.

Note that the enhanced for loop (for-each idiom) uses an Iterator internally. Consequently, enhanced for loops can also participate in concurrent modification issues, even though they lack an obvious iterator.

Noncompliant Code Example (Single-Threaded)

This noncompliant code example (based on Sun Developer Network SDN 2011 bug report 6687277) uses the ArrayList's remove() method to remove an element from an ArrayList while iterating over the ArrayList. The resulting behavior is unspecified.

class BadIterate {
  public static void main(String[] args) {
    List<String> list = new ArrayList<String>();
    list.add("one");
    list.add("two");
        
    Iterator iter = list.iterator();
    while (iter.hasNext()) {
      String s = (String)iter.next();
      if (s.equals("one")) {
        list.remove(s);
      }
    }
  }    
}

Compliant Solution (iterator.remove())

The Iterator.remove() method removes the last element returned by the iterator from the underlying Collection. Its behavior is fully specified, so it may be safely invoked while iterating over a collection.

// ...
if (s.equals("one")) {
  iter.remove();
}
// ...

Noncompliant Code Example (Multithreaded)

Although acceptable in a single-threaded environment, this noncompliant code example is insecure in a multithreaded environment because it is possible for another thread to modify the widgetList while the current thread iterates over the widgetList. Additionally, the doSomething() method could modify the collection during iteration.

List<Widget> widgetList = new ArrayList<Widget>();

public void widgetOperation() {
  // May throw ConcurrentModificationException
  for (Widget w : widgetList) {
    doSomething(w);
  }
}

Compliant Solution (Thread-Safe Collection)

This compliant solution wraps the ArrayList in a synchronized collection so that all modifications are subject to the locking mechanism.

List<Widget> widgetList = 
    Collections.synchronizedList(new ArrayList<Widget>());

public void widgetOperation() {
  synchronized (widgetList) { // Client-side locking
    for (Widget w : widgetList) {
      doSomething(w);
    }
  }
}

This approach must be implemented correctly to avoid starvation, deadlock, and scalability issues [Goetz 2006a].

Compliant Solution (Deep Copying)

This compliant solution creates a deep copy of the mutable widgetList before iterating over it:

List<Widget> widgetList = new ArrayList<Widget>();

public void widgetOperation() {
  List<Widget> deepCopy = new ArrayList<Widget>();
  synchronized (widgetList) { // Client-side locking
    for (Object obj : widgetList) {
      deepCopy.add(obj.clone());
    }
  } 

  for (Widget w : deepCopy) {
    doSomething(w);
  }
}

Creating deep copies of the list prevents underlying changes in the original list from affecting the iteration in progress. "Since the clone is thread-confined, no other thread can modify it during iteration, eliminating the possibility of ConcurrentModificationException. (The collection still must be locked during the clone operation itself)" [Goetz 2006a]. However, this approach is often more expensive than other techniques. There is also a risk of operating on stale data, which may affect the correctness of the code.

Compliant Solution (CopyOnWriteArrayList)

The CopyOnWriteArrayList data structure implements all mutating operations by making a fresh copy of the underlying array. It is fully thread-safe and is optimized for cases in which traversal operations vastly outnumber mutations. Note that traversals of such lists always see the list in the state it had at the creation of the iterator (or enhanced for loop); subsequent modifications of the list are invisible to an ongoing traversal. Consequently, this solution is inappropriate when mutations of the list are frequent or when new values should be reflected in ongoing traversals.

List<Widget> widgetList = new CopyOnWriteArrayList<Widget>();

public void widgetOperation() {
  for (Widget w : widgetList) {
    doSomething(w);
  }
}

Risk Assessment

Modifying a Collection while iterating over it results in undefined behavior.

Rule

Severity

Likelihood

Remediation Cost

Priority

Level

MSC06-J

Low

Probable

Medium

P4

L3

Automated Detection

Some static analysis tools can detect cases where an iterator is being used after the source container of the iterator is modified.

ToolVersionCheckerDescription
Parasoft Jtest 10.3 BD.CO.ITMODImplemented

Related Vulnerabilities

The Apache Harmony bug HARMONY-6236 documents an ArrayList breaking when given concurrent collections as input.

Bibliography

 


  

6 Comments

  1. It seems that this recommendation should be moved to 11. Concurrency (CON)

    1. Good suggestion because it almost exclusively talks about concurrency in the introduction. However, the NCE does not require multiple threads. I think I should make the introduction broader and keep this guideline here.

  2. CopyOnWriteArrayList and CopyOnWriteArraySet could possibly be discussed here. The problem with them is that the iterator will work on "stale" copies of the collection if a thread modifies the collection when an iteration is in progress. However, this cannot be strictly an NCE or CS. Perhaps an NCE with an exception that these can be used if stale values are not a concern.

  3. This might belong here:

    Although expensive in terms of performance, the CopyOnWriteArrayList and CopyOnWriteArraySet classes are sometimes used to create copies of the core Collection so that iterators do not fail with a runtime exception when some data in the Collection is modified. However, any updates to the Collection are not immediately visible to other threads. Consequently, the use of these classes is limited to boosting performance in code where the writes are fewer (or non-existent) as compared to the reads [JavaThreads 04]. In most other cases they must be avoided (see MSC13-J. Do not modify the underlying collection when an iteration is in progress for details on using these classes).

  4. I fixed the example "CS (Thread-Safe Collection)" to lock the collection around the iteration, as that is still necessary to safely iterate a synchronized collection.  however, this example still does not avoid the possibility of a ConcurrentModificationException from the same thread caused by code in the doSomething() method modifying the widgetList.  this should probably be called out in the text somewhere.

  5. Findbugs has a checker PZ_DONT_REUSE_ENTRY_OBJECTS_IN_ITERATORS which warns if a Map.Entry object is preserved while iterating over a Map. The Map.Entry javadoc clearly forbids this.
    Can we generalize this rule to warn against stale objects like Map.Entry during iteration?

    ED: Also the Findbugs checker DMI_ENTRY_SETS_MAY_REUSE_ENTRY_OBJECTS