Tasks that depend on other tasks to be complete should not be executed in the same bounded thread pool. A bounded thread pool is one that has a fixed size.
A form taskof thatdeadlock submitscalled another_thread taskstarvation todeadlock_ aarises singlewhen threaded {{Executor}} remains blocked untilall the threads executing in the resultspool are receivedblocked whereason thetasks secondthat taskare maywaiting have dependencies on the first taskqueue. ThisA constitutesblocking a deadlock. Another form of deadlock called threadoperation within a sub-task can also lead to unbounded queue growth. \[[Goetz 06|AA. Java References#Goetz 06]\]
Thread starvation deadlock can arise whenif a task spawns several other tasks in its own thread pool and waits for them to complete. Because of the limited thread pool size, only a fixed number of tasks can execute to completion at a particular time. InIf thisthe case,pool neitheris taskso cansmall finishthat executingall whentasks therenot arequeued noend availableup slotswaiting onfor the thread pool's work queue to accommodate the sub-tasks.
h2. Noncompliant Code Examplecompletion of tasks that are queued, a thread starvation deadlock results.
This noncompliantissue codeis exampledeceptive suffersbecause fromthe aprogram _threadmay starvation deadlock_ issue. It consists of class {{ValidationService}} that performs various input validation tasks such as checking whether a user-supplied field exists in a back-end database. The {{fieldAggregator()}} method accepts a variable number of {{String}} arguments and creates a task corresponding to each argument to gain some speedup. The task performs input validation using class {{ValidateInput}}. The class {{ValidateInput}} in turn, attempts to sanitize the input by creating a sub-task for each request using class {{SanitizeInput}}. All tasks are executed in the same thread pool. The methodappear to function correctly when fewer threads are needed. In some cases, the issue can be mitigated by choosing a larger pool size. However, there is often no easy way to determine a suitable pool size.
A more mundane deadlock can arise if two tasks on a thread pool each require the completion of the other task before completion.
h2. Noncompliant Code Example
This noncompliant code example suffers from thread starvation deadlock. It consists of class {{ValidationService}} which performs various input validation tasks such as checking whether a user-supplied field exists in a back-end database. The {{fieldAggregator()}} blocksmethod untilaccepts alla thevariable tasksnumber have finished executing. When all results are available, it aggregates the processed inputs as a {{StringBuilder}} that is returned to its caller.
{code:bgColor=#FFCCCC}
final class ValidationService {
private final ExecutorService pool;
public ValidationService(int poolSize) {
pool = Executors.newFixedThreadPool(poolSize);
}
public void shutdown() {
pool.shutdown();
}
public StringBuilder fieldAggregator(String... inputs)
throws InterruptedException, ExecutionException {
StringBuilder sb = new StringBuilder();
Future<String>[] results = new Future[inputs.length]; // Stores the results
for(int i = 0; i < inputs.length; i++) { // Submits the tasks to thread pool
results[i] = pool.submit(new ValidateInput<String>(inputs[i], pool));
}
for(int i = 0; i of {{String}} arguments and creates a task corresponding to each argument to gain some speedup. The task performs input validation using class {{ValidateInput}}. The class {{ValidateInput}} in turn, attempts to sanitize the input by creating a sub-task for each request using class {{SanitizeInput}}. All tasks are executed in the same thread pool. The method {{fieldAggregator()}} blocks until all the tasks have finished executing. When all results are available, it aggregates the processed inputs as a {{StringBuilder}} that is returned to its caller.
{code:bgColor=#FFCCCC}
public final class ValidationService {
private final ExecutorService pool;
public ValidationService(int poolSize) {
pool = Executors.newFixedThreadPool(poolSize);
}
public void shutdown() {
pool.shutdown();
}
public StringBuilder fieldAggregator(String... inputs)
throws InterruptedException, ExecutionException {
StringBuilder sb = new StringBuilder();
Future<String>[] results = new Future[inputs.length]; // Stores the results
for(int i = 0; i < inputs.length; i++) { // AggregatesSubmits the results tasks to thread pool
sb.append(results[i].get( = pool.submit(new ValidateInput<String>(inputs[i], pool));
}
return sb;
}
}
public final class ValidateInput<V> implements Callable<V> {
private final String input;
private final ExecutorService pool;
ValidateInput(String input, ExecutorService pool) {
this.input = input;
this.pool = poolfor(int i = 0; i < inputs.length; i++) { // Aggregates the results
sb.append(results[i].get());
}
return sb;
}
}
public final @Overrideclass publicValidateInput<V> Vimplements call() throws Exception Callable<V> {
private final // If validation fails, throw an exception here
Future<String> future = pool.submit(new SanitizeInput<String>(input)); // Sub-task
return (V)future.get()V input;
private final ExecutorService pool;
ValidateInput(V input, ExecutorService pool) {
this.input = input;
this.pool = pool;
}
}
@Override public finalV classcall() SanitizeInput<V>throws implementsException Callable<V> {
private // finalIf String input;
SanitizeInput(String input) {
validation fails, throw an exception here
Future<V> this.inputfuture = pool.submit(new SanitizeInput<V>(input));
}
// Sub-task
@Override public V callreturn (V)future.get();
throws Exception {
// Sanitize input and return
return (V)input;
}
}
{code}
{mc}
// Hidden main() method
public static void main(String[] args) throws InterruptedException, ExecutionException {
ValidationService vs = new ValidationService(5);
System.out.println(vs. }
}
public final class SanitizeInput<V> implements Callable<V> {
private final V input;
SanitizeInput(V input) {
this.input = input;
}
@Override public V call() throws Exception {
// Sanitize input and return
return (V)input;
}
}
{code}
{mc}
// Hidden main() method
public static void main(String[] args) throws InterruptedException, ExecutionException {
ValidationService vs = new ValidationService(5);
System.out.println(vs.fieldAggregator("field1", "field2","field3","field4", "field5","field6"));
vs.shutdown();
}
{mc}
Assume that the caller sets the thread pool size as 6. When it calls {{ValidationService.fieldAggregator()}} is invoked with six arguments that are required to be validated, six tasks are submitted to the thread pool. Six more sub-tasks corresponding to {{SanitizeInput}} must also execute before these threads can return their results. However, this is not possible because the queue is full with all threads blocked.
This issuesituation iscan deceptivealso becauseoccur thewhen programusing maysingle appearthreaded toExecutors, functionfor correctlyexample, when fewerthe argumentscaller arecreates supplied. Choosing a bigger pool size appears to solve the problem, however there is no easy way to determine a suitable size.
This situation can also occur when using single threaded Executors, for example, when the caller creates several sub-tasks and waits for the results. A thread starvation deadlock arises when all the threads executing in the pool are blocked on tasks that are waiting on the queue. A blocking operation within a sub-task can also lead to unbounded queue growth. \[[Goetz 06|AA. Java References#Goetz 06]\]
h2. Compliant Solution
This compliant solution refactors all three classes so that the tasks corresponding to {{SanitizeInput}} are not executed in a thread pool. Consequently, the tasks are independent of each other. An alternative is to use a different thread pool at each level, though in this example, another thread pool is unnecessary.
{code:bgColor=#ccccff}
class ValidationService {
// ...
public StringBuilder fieldAggregator(String... inputs)
throws InterruptedException, ExecutionException {
// ...
for (int i = 0; i < inputs.length; i++) {
results[i] = pool.submit(new ValidateInput<String>(inputs[i])); // Don't pass-in thread pool
}
// ...
}
}
public final class ValidateInput<V> implements Callable<V> { // Does not use same thread pool
private final String input;
ValidateInput(String input) {
this.input = input;
}
@Override public V call() throws Exception {
// If validation fails, throw an exception here
return (V)SanitizeInput.sanitizeString(input);
}
}
public final class SanitizeInput { // No longer a Callable task
private SanitizeInput() { }
public static String sanitizeString(String input) {
// Sanitize input and return
return input;
}
}
{code}
Always submit independent tasks to the {{Executor}}. Thread starvation issues can be mitigated by choosing a large pool size, however, the limitations of the application when using this approach should be clearly documented.
Note that operations that have further constraints, such as the total number of database connections or total {{ResultSets}} open at a particular time, impose an upper bound on the thread pool size as each thread continues to block until the resource becomes available. The other rules of fair concurrency, such as not running time consuming tasks, also apply. When this is not possible, expecting to obtain real time result guarantees from the execution of tasks is conceivably, an unreasonable target.
Sometimes, a {{private static}} {{ThreadLocal}} variable is used per thread to maintain local state. When using thread pools, {{ThreadLocal}} variables should be used only if their lifetime is shorter than that of the corresponding task \[[Goetz 06|AA. Java References#Goetz 06]\]. Moreover, such variables should not be used as a communication mechanism between tasks. several sub-tasks and waits for the results.
h2. Compliant Solution (no interdependent threads)
This compliant solution refactors the {{ValidateInput<V>}} class so that the tasks corresponding to {{SanitizeInput}} are not executed in distinct threads in the thread pool. Consequently, the tasks are independent of each other, and no thread in the pool must wait for another thread to complete.
{code:bgColor=#ccccff}
public final class ValidateInput<V> implements Callable<V> {
// ...
@Override public V call() throws Exception {
return (V) new SanitizeInput(input).call();
}
}
{code}
Always submit independent tasks to the {{Executor}}. Thread starvation issues can be mitigated by choosing a large pool size, however, the limitations of the application when using this approach should be clearly documented.
Note that operations that have further constraints, such as the total number of database connections or total {{ResultSets}} open at a particular time, impose an upper bound on the thread pool size as each thread continues to block until the resource becomes available. The other rules of fair concurrency, such as not running time consuming tasks, also apply. When this is not possible, expecting to obtain real time result guarantees from the execution of tasks is conceivably, an unreasonable target.
Sometimes, a {{private static}} {{ThreadLocal}} variable is used per thread to maintain local state. When using thread pools, {{ThreadLocal}} variables should be used only if their lifetime is shorter than that of the corresponding task \[[Goetz 06|AA. Java References#Goetz 06]\]. Moreover, such variables should not be used as a communication mechanism between tasks.
h2. Compliant Solution (Unbounded thread pool)
This compliant solution uses a cached thread pool, which will create enough threads to satisfy the demenads of the program and prevent deadlock.
{code:bgColor=#ccccff}
public final class ValidationService {
private final ExecutorService pool;
public ValidationService(int poolSize) {
pool = Executors.newCachedThreadPool(poolSize);
}
// ...
}
{code}
The {{Executors.newCachedThreadPool()}} method does the following: \[[API 06|AA. Java References#API 06]\]
{quote}
Creates a thread pool that creates new threads as needed, but will reuse previously constructed threads when they are available. These pools will typically improve the performance of programs that execute many short-lived asynchronous tasks. Calls to execute will reuse previously constructed threads if available. If no existing thread is available, a new thread will be created and added to the pool. Threads that have not been used for sixty seconds are terminated and removed from the cache. Thus, a pool that remains idle for long enough will not consume any resources.
{quote}
h2. Noncompliant Code Example
This noncompliant code example (based on \[[Gafter 06|AA. Java References#Gafter 06]\]) shows a {{BrowserManager}} class that has several methods that use a fork-join mechanism, that is, they start threads and wait for them to finish. The methods are called in the sequence {{perUser()}}, {{perProfile}} and {{perTab()}}. The method {{methodInvoker()}} spawns several instances of the specified runnable depending on the value of the variable {{numberOfTimes}}. A fixed sized thread pool is used to execute the enumerations of tasks created at different levels.
{code:bgColor=#FFCCCC}
public final class BrowserManager {
private final ExecutorService pool = Executors.newFixedThreadPool(10);
private final int numberOfTimes;
private static volatileAtomicInteger int count = new AtomicInteger(0);
public BrowserManager(int n) {
this.numberOfTimes = n;
}
public void perUser() {
methodInvoker(numberOfTimes, "perProfile");
pool.shutdown();
}
public void perProfile() {
methodInvoker(numberOfTimes, "perTab");
}
public void perTab() {
methodInvoker(numberOfTimes, "doSomething");
}
public void doSomething() {
System.out.println(++count(count.getAndIncrement());
}
public void methodInvoker(int n, final String method) {
final BrowserManager fm = this;
RunnableCallable<Object> runcallable = new RunnableCallable<Object>() {
public voidObject runcall() {
throws try Exception {
Method meth = fm.getClass().getMethod(method);
return meth.invoke(fm);
}
catch (Throwable t) {
};
Collection< Callable< Object>> collection // Forward to exception reporter= Collections.nCopies( n, callable);
try {
}
Collection< Future< Object>> futures }= pool.invokeAll(collection);
};
catch (InterruptedException
e) { Collection<Callable<Object>> collection = new ArrayList<Callable<Object>>();
for(int i =// 0;Forward ito <handler n; i++) {
collectionThread.addcurrentThread(Executors).callableinterrupt(run));; // Reset interrupted status
}
// Collection<Future<Object>>... futures
= null;
try}
public static void main(String[] args) {
BrowserManager manager futures= =new pool.invokeAllBrowserManager(collection5);
} catch (InterruptedException e) {
// Forward to handler
Thread.currentThread().interrupt(); // Reset interrupted status
}
// ...
}
public static void main(String[] args) {
BrowserManager manager = new BrowserManager(5);
manager.perUser();
}
}
{code}
Contrary to what is expected, this program does not print the total count, that is, the number of times {{doSomething()}} is invoked. This is because it is susceptible to a thread starvation deadlock because the size of the thread pool (10) does not allow either thread from {{perTab()}} to invoke the {{doSomething()}} method. The output of the program varies for different values of {{numberOfTimes}} and the thread pool size. Note that different threads are allowed to invoke {{doSomething()}} in different orders; we are concerned only with the maximum value of {{count}} to determine how many times the method executed.
h2. Compliant Solution
This compliant solution selects and schedules tasks for execution, and consequently, avoids the thread starvation deadlock. Every level (worker) must have a double ended queue where all sub-tasks are queued \[[Goetz 06|AA. Java References#Goetz 06]\]. Each level removes the most recently generated sub-task from the queue so that it can process it. When there are no more threads left to process, the current level runs the least-recently created sub-task of another level by picking and removing it from that level's queue (work stealing).
This compliant solution sets the {{CallerRuns}} policy on a {{ThreadPoolExecutor}}, and uses a synchronous queue \[[Gafter 06|AA. Java References#Gafter 06]\].manager.perUser();
}
}
{code}
Contrary to what is expected, this program does not print the total count, that is, the number of times {{doSomething()}} is invoked. This is because it is susceptible to a thread starvation deadlock because the size of the thread pool (10) does not allow either thread from {{perTab()}} to invoke the {{doSomething()}} method. The output of the program varies for different values of {{numberOfTimes}} and the thread pool size. Note that different threads are allowed to invoke {{doSomething()}} in different orders; we are concerned only with the maximum value of {{count}} to determine how many times the method executed.
h2. Compliant Solution ({{CallerRunsPolicy}})
This compliant solution selects and schedules tasks for execution, and consequently, avoids the thread starvation deadlock. Every level (worker) must have a double ended queue where all sub-tasks are queued \[[Goetz 06|AA. Java References#Goetz 06]\]. Each level removes the most recently generated sub-task from the queue so that it can process it. When there are no more threads left to process, the current level runs the least-recently created sub-task of another level by picking and removing it from that level's queue (work stealing).
This compliant solution sets the {{CallerRunsPolicy}} on a {{ThreadPoolExecutor}}, and uses a synchronous queue \[[Gafter 06|AA. Java References#Gafter 06]\]. The policy dictates that if the thread pool runs out of available threads, any subsequent tasks are run in the current thread. This solution also uses a custom {{ThreadPoolExecutor}}.
{code:bgColor=#ccccff}
public final class BrowserManager {
private final static ThreadPoolExecutor pool =
new ThreadPoolExecutor(0, 10, 60L, TimeUnit.SECONDS,
new SynchronousQueue<Runnable>());
private final int numberOfTimes;
private static volatileAtomicInteger int count = new AtomicInteger(0);
static {
pool.setRejectedExecutionHandler(
new ThreadPoolExecutor.CallerRunsPolicy());
}
// ...
}
{code}
According to the Java API \[[API 06|AA. Java References#API 06]\], class {{java.util.concurrent.ThreadPoolExecutor.CallerRunsPolicy}} documentation:
{quote}
A handler for rejected tasks that runs the rejected task directly in the calling thread of the {{execute}} method, unless the executor has been shut down, in which case the task is discarded.
{quote}
The caller runs policy allows graceful degradation of service when faced with many requests by distributing the workload across the work queue, the underlying abstraction (such as the queue of a TCP/IP connection) and the caller.
This compliant solution is subject to the vagaries of the thread scheduler which may not optimally schedule the tasks, however, it avoids the thread starvation deadlock.
h2. Risk Assessment
Executing interdependent tasks in a thread pool can lead to denial of service.
|| Rule || Severity || Likelihood || Remediation Cost || Priority || Level ||
| CON29- J | low | probable | medium | {color:green}{*}P4{*}{color} | {color:green}{*}L3{*}{color} |
h3. Automated Detection
TODO
h3. Related Vulnerabilities
Search for vulnerabilities resulting from the violation of this rule on the [CERT website|https://www.kb.cert.org/vulnotes/bymetric?searchview&query=FIELD+KEYWORDS+contains+FIO38-J].
h2. References
\[[API 06|AA. Java References#API 06]\]
\[[Gafter 06|AA. Java References#Gafter 06]\] [A Thread Pool Puzzler|http://gafter.blogspot.com/2006/11/thread-pool-puzzler.html]
\[[Goetz 06|AA. Java References#Goetz 06]\] 5.3.3 Deques and work stealing
----
[!The CERT Sun Microsystems Secure Coding Standard for Java^button_arrow_left.png!|FIO36-J. Do not create multiple buffered wrappers on an InputStream] [!The CERT Sun Microsystems Secure Coding Standard for Java^button_arrow_up.png!|09. Input Output (FIO)] [!The CERT Sun Microsystems Secure Coding Standard for Java^button_arrow_right.png!|09. Input Output (FIO)]
|
