...
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
Collectionwhile another thread is iterating over it. In general, the results of the iteration are undefined under these circumstances. SomeIteratorimplementations (including those of all the general purpose collection implementations provided by the JRE) may choose to throw this exception if this behavior is detected.Iteratorsthat 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
ConcurrentModificationExceptionon a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness:ConcurrentModificationExceptionshould 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,
hasNextornextthrowsConcurrentModificationException. 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.
| Code Block | ||
|---|---|---|
| ||
{quote} 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|AA. Java References#API 06]\] for {{ConcurrentModificationException}}: {quote} ... 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 as 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. {quote} 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|AA. Java References#Goetz 06]\]. Notably, the enhanced {{for}} loop (for-each idiom) internally uses an {{Iterator}} {mc} consequences? {mc}. h2. Noncompliant Code Example (single-threaded) This noncompliant code example (based on a bug report [6687277|http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=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. {code:bgColor=#FFcccc} 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); } } } } {code} h2. Compliant Solution ({{ |
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.
| Code Block | ||
|---|---|---|
| ||
specified. {code:bgColor=#ccccff} // ... 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.
| Code Block | ||
|---|---|---|
| ||
{code} h2. 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. {code:bgColor=#FFcccc} List<Widget> widgetList = new ArrayList<Widget>(); pubicpublic void widgetOperation() { // May throw ConcurrentModificationException for (Widget w : widgetList) { doSomething(w); } } {code} h2. Compliant |
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 | ||
|---|---|---|
| ||
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:bgColor=#ccccff} List<Widget> widgetList = Collections.synchronizedList(new ArrayList<Widget>()); pubicpublic void widgetOperation() { synchronized (widgetList) { // Client-side locking for (Widget w : widgetList) { doSomething(w); } } {code} |
This
...
approach
...
must be
...
implemented
...
correctly
...
to
...
avoid
...
...
...
, and
...
scalability
...
issues
...
[Goetz 2006a].
Compliant Solution (Deep Copying)
This compliant solution creates a deep copy of the mutable widgetList before iterating over it:
| Code Block | ||
|---|---|---|
| ||
[Goetz 2006|AA. Java References#Goetz 06]\]. h2. Compliant Solution (deep copying) This compliant solution creates a deep copy of the mutable {{widgetList}} before iterating over it. {code:bgColor=#ccccff} 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); } } {code} |
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
...
)"
...
...
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.
| Code Block | ||
|---|---|---|
| ||
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.
| Tool | 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
...