| Wiki Markup |
|---|
According to the Java API documentation \[[API 2006|AA. Bibliography#API 06]\] 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. Concurrent modification in single threaded programs is usually a symptom of removing an element during iteration. Multithreaded programs add the possibility that a collection may be modified by one thread while another thread is iterating over the collection. Unspecified behavior can result in either case. Many implementations throw a ConcurrentModificationException when they detect concurrent modification.
| Wiki Markup |
|---|
According to the Java API documentation \[[API 2006|AA. Bibliography#API 06]\] 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.
| Wiki Markup |
|---|
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]\]. |
...
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
...
bug
...
report
...
6687277) uses the Collection's remove() method to remove an element from an ArrayList while iterating over the ArrayList. The resulting behavior is unspecified.
| Code Block | ||
|---|---|---|
| ||
|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
...
from
...
the
...
underlying
...
Collection
...
the
...
last
...
element
...
returned
...
by
...
the
...
iterator.
...
Its
...
behavior
...
is
...
fully
...
specified.
| Code Block | ||||
|---|---|---|---|---|
| =
| |||
} // ... if(s.equals("one")) { iter.remove(); } // ... {code} h2. Noncompliant Code Example |
Noncompliant Code Example (Multithreaded)
...
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 | ||
|---|---|---|
| ||
}} 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>(); pubic void widgetOperation() { // May throw ConcurrentModificationException for (Widget w : widgetList) { doSomething(w); } } {code} h2. Compliant Solution |
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 | ||
|---|---|---|
| ||
{code:bgColor=#ccccff} List<Widget> widgetList = Collections.synchronizedList(new ArrayList<Widget>()); pubic void widgetOperation() { for (Widget w : widgetList) { doSomething(w); } } {code} |
| Wiki Markup |
|---|
This approach needs to be implemented correctly to avoid starvation, deadlock and scalability issues \[[Goetz 2006|AA. Bibliography#Goetz 06]\]. |
...
Compliant
...
Solution
...
(Deep
...
Copying)
...
This
...
compliant
...
solution
...
creates
...
a
...
deep
...
copy
...
of
...
the
...
mutable
...
widgetList
...
before
...
iterating
...
over
...
it.
| Code Block | ||
|---|---|---|
| ||
{code:bgColor=#ccccff} 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); } } {code} |
| Wiki Markup |
|---|
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]\]. 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 traversal operations vastly outnumber mutations.
| Code Block | ||
|---|---|---|
| ||
List<Widget> widgetList = new CopyOnWriteArrayList<Widget>(); pubic void widgetOperation() { for (Widget w : widgetList) { h2. Exceptions * doSomething(w); } } |
Exceptions
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 behavior.
Guideline | Severity | Likelihood | Remediation Cost | Priority | Level |
|---|---|---|---|---|---|
MSC13-J | low | probable | medium | P4 | L3 |
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
Bibliography
| Wiki Markup |
|---|
\[[API 2006|AA. Bibliography#API 06]\] Class [ConcurrentModificationException|http://java.sun.com/j2se/1.5.0/docs/api/java/util/ConcurrentModificationException.html]
\[[SDN 2008|AA. Bibliography#SDN 08]\] [Sun Bug database, Bug ID:6687277|http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6687277]
\[[Goetz 2006|AA. Bibliography#Goetz 06]\] 5.1.2. Iterators and Concurrentmodificationexception |
...
...
...
...
...
...
...
Enumerations 49. Miscellaneous (MSC) MSC14-J.
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...