According to the Java API documentation \[ [API 2006|AA. Bibliography#API 06]\] for the {{2014] for the Wiki Markup 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-threaded and multithreaded programs. Concurrent modification in single-threaded programs is usually a symptom 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. Unspecified Undefined behavior can result results in either case. Many implementations throw a ConcurrentModificationException
when they detect concurrent modification.unmigrated-wiki-markup
According to the Java API documentation \[ [API 2006|AA. Bibliography#API 06]\] for {{ConcurrentModificationException}}2014] for ConcurrentModificationException
:
It ... 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. SomeIterator
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. ConsequentlyTherefore, 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 insufficient to stop side effects 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. "\[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|AA. Bibliography#Goetz 06]\]. 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
ornext
throwsConcurrentModificationException
. 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 a Sun Developer Network SDN 20082011 bug report 6687277) uses the Collection
ArrayList
's remove()
method to remove an element from an ArrayList
while iterating over the ArrayList
. The resulting behavior is unspecified.
Code Block | ||
---|---|---|
| ||
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 from the underlying Collection
. Its behavior is fully specified, so it may be safely invoked while iterating over a collection.
Code Block | ||
---|---|---|
| ||
// ... 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
using the code shown below. Additionally, the doSomething()
method could also modify the collection during iteration.
Code Block | ||
---|---|---|
| ||
List<Widget> widgetList = new ArrayList<Widget>(); pubicpublic 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.
Code Block | ||
---|---|---|
| ||
List<Widget> widgetList = Collections.synchronizedList(new ArrayList<Widget>()); pubicpublic void widgetOperation() { synchronized (widgetList) { // Client-side locking for (Widget w : widgetList) { doSomething(w); } } } |
This approach needs to must be implemented correctly to avoid starvation, deadlock , and scalability issues \[ [Goetz 2006|AA. Bibliography#Goetz 06]\2006a]. Wiki Markup
Compliant Solution (Deep Copying)
This compliant solution creates a deep copy of the mutable widgetList
before iterating over it. :
Code Block | ||
---|---|---|
| ||
List<Widget> widgetList = new ArrayList<Widget>(); pubicpublic 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|AA. Bibliography#Goetz 06]\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 where 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.
Code Block | ||
---|---|---|
| ||
List<Widget> widgetList = new CopyOnWriteArrayList<Widget>(); pubicpublic void widgetOperation() { for (Widget w : widgetList) { doSomething(w); } } |
...
MSC13-EX1: The Iterator.remove()
method can be used to modify the underlying collection when an iteration is in progress.
Risk Assessment
Modifying a Collection
while iterating over it can lead to nondeterministic results in undefined behavior.
Rule | Severity | Likelihood | Remediation Cost | Priority | Level |
---|
MSC06-J |
Low |
Probable |
Medium | P4 | L3 |
Automated Detection
The Coverity Prevent Version 5.0 INVALIDATE_ITERATOR checker can detect the instance Some static analysis tools can detect cases where an iterator is being used after the source container of the interator iterator is modified.
Tool |
---|
Related Vulnerabilities
Bibliography
<ac:structured-macro ac:name="unmigrated-wiki-markup" ac:schema-version="1" ac:macro-id="e9b050f9-e987-4d68-9d73-29814720baab"><ac:plain-text-body><![CDATA[ | [[API 2006 | AA. Bibliography#API 06]] | Class [ConcurrentModificationException | http://java.sun.com/j2se/1.5.0/docs/api/java/util/ConcurrentModificationException.html] | ]]></ac:plain-text-body></ac:structured-macro> |
<ac:structured-macro ac:name="unmigrated-wiki-markup" ac:schema-version="1" ac:macro-id="9998af1d-764a-45fd-9134-3cce07aa3246"><ac:plain-text-body><![CDATA[ | [[SDN 2008 | AA. Bibliography#SDN 08]] | [Sun Bug database, Bug ID:6687277 | http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6687277] | ]]></ac:plain-text-body></ac:structured-macro> |
<ac:structured-macro ac:name="unmigrated-wiki-markup" ac:schema-version="1" ac:macro-id="91642563-6c63-47e6-aa67-c2876527963c"><ac:plain-text-body><![CDATA[ | [[Goetz 2006 | AA. Bibliography#Goetz 06]] | 5.1.2. Iterators and Concurrentmodificationexception | ]]></ac:plain-text-body></ac:structured-macro> |
Version | Checker | Description | |||||||
---|---|---|---|---|---|---|---|---|---|
Parasoft Jtest |
| CERT.MSC06.ITMOD | Do not modify collection while iterating over it | ||||||
PVS-Studio |
| V6053 |
Related Vulnerabilities
The Apache Harmony bug HARMONY-6236 documents an ArrayList
breaking when given concurrent collections as input.
Bibliography
...
MSC11-J. Do not assume infinite heap space 49. Miscellaneous (MSC) MSC14-J. Finish every set of statements associated with a case label with a break statement