MSC13-J. Do not modify the underlying collection when an iteration is in progress

According to the Java API documentation [[API 2006]] for 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.

Such behavior may be observed in both single and multithreaded programs. In single threaded programs, this usually happens when an element is removed when the iteration is in progress. In a multithreaded program, it is possible that one thread iterates over a collection while another concurrently modifies it. This can result in unspecified behavior. Many implementations throw a ConcurrentModificationException when such a condition is detected.

According to the Java API documentation [[API 2006]] 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. Consequently, it would be wrong to write a program that depended on this exception for its correctness: ConcurrentModificationException should be used only to detect bugs.

Do not rely on ConcurrentModificationException to stop any side effects resulting from modifying an underlying Collection while iterating over it. The fail-fast behavior may occur after processing an arbitrary number of elements. "[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" [[Goetz 2006]].

Notably, the enhanced for loop (for-each idiom) internally uses an Iterator.

Noncompliant Code Example (Single-Threaded)

This noncompliant code example (based on a bug report 6687277) removes an element from an ArrayList using the Collection's remove() method. This is done while iterating over the Collection. 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 from the underlying Collection the last element returned by the iterator. Its behavior is fully specified.

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

Noncompliant Code Example (Multithreaded)

This noncompliant code example is insecure in a multithreaded environment because it is possible for a thread to modify the widgetList while it is being iterated. Moreover, even the doSomething() method may modify the collection while an iteration is in progress.

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

pubic 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>());

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

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

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>();

pubic 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 2006]]. 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.

Exceptions

MSC13-EX1: The Iterator.remove() method can be used to modify the underlying collection when an iteration is in progress. This is also shown in the compliant solution.

Risk Assessment

Modifying a Collection while iterating over it can lead to nondeterministic behavior.

Automated Detection

The Coverity Prevent Version 5.0 INVALIDATE_ITERATOR checker can detect the instance where an iterator is being used after the source container of the interator is modified.

Related Vulnerabilities

HARMONY-6236

Bibliography

[[API 2006]] Class ConcurrentModificationException
[[SDN 2008]] Sun Bug database, Bug ID:6687277
[[Goetz 2006]] 5.1.2. Iterators and Concurrentmodificationexception

[!The CERT Oracle Secure Coding Standard for Java^button_arrow_left.png!]      [!The CERT Oracle Secure Coding Standard for Java^button_arrow_up.png!]      [!The CERT Oracle Secure Coding Standard for Java^button_arrow_right.png!]