According to the Java API documentation \[[API 2006|AA. Bibliography#API 06]\] for {{Iterator.remove()}} method:
{quote}
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.
{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. Bibliography#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 asbecause 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. Bibliography#Goetz 06]\].
Notably, the enhanced {{for}} loop (for-each idiom) internally uses an {{Iterator}}. {mc} consequences? {mc}.
h2. Noncompliant Code Example (singleSingle-threadedThreaded)
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 ({{iterator.remove()}})
The {{Iterator.remove()}} method removes from the underlying {{Collection}} the last element returned by the iterator. Its behavior is fully specified.
{code:bgColor=#ccccff}
// ...
if(s.equals("one")) {
iter.remove();
}
// ...
{code}
h2. Noncompliant Code Example (multithreadedMultithreaded)
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>();
pubic void widgetOperation() {
// May throw ConcurrentModificationException
for (Widget w : widgetList) {
doSomething(w);
}
}
{code}
h2. Compliant Solution (threadThread-safeSafe collectionCollection)
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>());
pubic void widgetOperation() {
for (Widget w : widgetList) {
doSomething(w);
}
}
{code}
This approach needs to be implemented correctly to avoid starvation, deadlock and scalability issues \[[Goetz 2006|AA. Bibliography#Goetz 06]\].
h2. Compliant Solution (deepDeep copyingCopying)
This compliant solution creates a deep copy of the mutable {{widgetList}} before iterating over it.
{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}
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.
h2. 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.
h2. Risk Assessment
Modifying a Collection while iterating over it can lead to nondeterministic behavior.
|| RuleGuideline || Severity || Likelihood || Remediation Cost || Priority || Level ||
| MSC13- J | low | probable | medium | {color:green}{*}P4{*}{color} | {color:green}{*}L3{*}{color} |
h3. 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.
h3. Related Vulnerabilities
[HARMONY-6236|http://issues.apache.org/jira/browse/HARMONY-6236]
h2. Bibliography
\[[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
----
[!The CERT Oracle Secure Coding Standard for Java^button_arrow_left.png!|MSC12-J. Prefer using Iterators over Enumerations] [!The CERT Oracle Secure Coding Standard for Java^button_arrow_up.png!|49. Miscellaneous (MSC)] [!The CERT Oracle Secure Coding Standard for Java^button_arrow_right.png!|MSC14-J. Finish every set of statements associated with a case label with a break statement]
| 