Proposed Vulnerability Description on Concurrency

Contributed by Steve Michell
30 September 2008

6.Y Concurrency [CGW]

6.Y.1 Description of Application Vulnerability

Concurrency, or parallel programming, includes

Concurrency presents a significant challenge to program correctly, and has a large number of possible ways for failures to occur, quite a few known attack vectors, and many possible but undiscovered attack vectors.

Concurrency is a major challenge because the analysis of concurrent programs is so difficult. In the general case there are exceedingly large numbers (numbers in the ranges of 10**100 for even small programs) of possible interleavings of parallel portions. Static analysis of the general cases is impossible because the complexities are so very high and because such analysis requires modelling the complete program at once - an NP Hard problem. Dynamic analysis of the general cases is fruitless because a concurrent program will never behave in exactly the same way twice, even with identical inputs.

The previous discussion should not lead one to dispair, because there are ways of taming concurrency, and there are various paradigms that are known to be analyzable.

Research is ongoing into more paradigms, such as variations of non-terminating programs on single cpus using the Ravenscar Tasking Profile.

The fact is, however, that we must work with concurrency in more general settings, and most do not satisfy the constraints listed above. Most concurrent programs are cyclic or non terminating, handle events from an OS or interrupts from hardware, work with multiple different levels of urgency (often called priority) between components, have concurrency behaviours that are coupled to data being processed, and have interesting data couplings between tasks.

Most real time systems are effectively concurrent systems, but must account for time, mixed urgencies and the consequences of failure to complete necessary computations.

It is not known if attacks based on knowledge of concurrency of a system can be more sophisticated than denials of service based on deadlock or livelock.

For safety-related systems, the sheer number of possible failure modes and unacceptable interactions create almost intolerable complexity. Many such systems handle these by using exclusively time-based cyclic systems, eliminating interrupts, and extensive of dedicated cpus. Some usage of very restrictive concurrency paradigms such as Ravenscar and similar microkernels has been seen.

6.Y.2 Cross References

6.Y.3 Mechanism of Failure

The basic classifications of concurrency related failures are:

6.Y.4 Applicable Language Characteristics

6.Y.5 Avoiding the Vulnerability or Mitigating its Effects

6.Y.6 Implications for Standardization

6.Y. 7 Bibliography