[cfe-dev] [RFC] Adding Thread Role Analysis

Thu Jun 20 16:12:46 PDT 2013

As Chandler mentioned, clang already has an existing thread safety
analysis, which is based on type systems for static race detection, which I
believe you are familiar with:

  http://users.soe.ucsc.edu/~cormac/papers/pldi00.pdf
  http://users.soe.ucsc.edu/~cormac/papers/toplas06-safe-locking.pdf

The clang annotations can be found at:
http://clang.llvm.org/docs/LanguageExtensions.html

In a nutshell, the existing analysis allows a data member to be annotated
as being guarded by a particular lock.  Similarly, a function can be
annotated as requiring a particular lock to be held.  The analysis then
tracks the set of locks that are known to be held at every program point,
and issues warnings when a data member is accessed or a function is called
without holding the appropriate lock.

The existing analysis tracks locks, not threads or roles, so concepts like
the "GUI thread" cannot be directly expressed. However, it's not hard to
mimic this functionality -- the GUI thread acquires a lock named "GUI_lock"
when it starts, and releases it when its done, and all code and data that
should be GUI-only is annotated as requiring that lock.  (A lock in clang
is simply a named C++ object; it does not need to implement an actual
lock.)  Switching of roles can similarly be modeled as releasing one lock
and acquiring another.  So at first glance, it seems to me that lock-based
analysis is roughly similar to the analysis that you propose, and may in
fact be significantly stronger; the "related work" section in your paper
does not discuss the differences in much detail.

The existing clang annotations are used extensively on production code; we
have many hundreds of thousands of lines that are currently annotated and
checked.  It is not a research project.

In order to move forward, I would like to see a detailed explanation of the
differences between your proposal and what is currently implemented, and
why you feel the current annotations are insufficient.  Ideally, I would
prefer to extend the existing annotations and/or analysis to handle any
deficiencies, rather than invent a wholly new and incompatible analysis.

  -DeLesley

On Thu, Jun 20, 2013 at 2:16 PM, Chandler Carruth <chandlerc at google.com>wrote:

> You don't seem to have addressed how this interacts with the *existing*
> thread safety analysis in Clang. I think you'll need to do that. I've CC-ed
> folks in the Clang community already working on these things. =]
>
>
> On Thu, Jun 20, 2013 at 2:03 PM, Aaron Ballman <aaron at aaronballman.com>wrote:
>
>> Hello!
>>
>> We at CERT are interested in adding thread role analysis support (also
>> known as thread coloring) to clang.  This email is meant to briefly
>> introduce the subject and then open up to the community for comments.
>>
>> Thread role analysis (or TRA), allows programmers to express their
>> thread usage policies in source code using simple and concise
>> annotations.  A static analyzer can check whether the expressed
>> policies and the as-written code are consistent, ensuring that the
>> annotated contract remains effective.
>>
>> We've worked extensively with--and have demonstrated the utility
>> of--TRA for Java, including analyzing and finding significant problems
>> in dozens of fielded applications ranging from toy applets to
>> multi-million LOC commercial applications.  As part of that prior work
>> we demonstrated:
>> * Required annotation density (for Java) of ~6 annotations per KLOC
>> (and a design that should permit reducing this to <1 annotation per
>> KLOC)
>> * Composability of the analysis
>> * Adoptability by working programmers
>> * Capability to analyze large programs (>150KLOC in a single chunk;
>> multi-million LOC in multiple chunks)
>> * The annotation language and analysis suffice for analyzing a wide
>> variety of real programs
>>
>> Publications regarding our previous work with TRA for Java include:
>> * PPoPP'10 paper (best short introduction) --
>>
>> http://www.fluid.cs.cmu.edu:8080/Fluid/fluid-publications/p233-sutherland.pdf
>> * Ph.D. Dissertation (all the gory details, but LONG) --
>> http://reports-archive.adm.cs.cmu.edu/anon/isr2008/abstracts/08-112.html
>> * Blog post -- http://blog.sei.cmu.edu/post.cfm/thread-role-analysis
>>
>> Thread usage policies describe what kinds of threads ("thread roles")
>> are permitted to invoke particular functions or methods.  TRA can be
>> used to enforce a wide variety of policies including (but not limited
>> to):
>> * Single-thread-only (e.g., use of threads is forbidden)
>> * Restricting use of GUI methods to the GUI event thread
>> * Ensuring that threads engaged in reader-writer locking restrict
>> themselves to calls that are consistent with their role -- e.g.,
>> readers never attempt to write and outside threads neither read nor
>> write.
>> * Ensuring that llvm Function passes never invoke llvm Module passes
>> (note that this would require C++ support; initial phases of this
>> project involve C only)
>>
>> When combined with a sufficiently-powerful effects analysis, TRA can
>> also be applied to data objects. In this mode, it can be used to
>> either (1) prove thread confinement of data (which then need not be
>> locked), or (2) identify data that is potentially shared across
>> threads (and consequently requires concurrency control of some sort).
>> However, we are not aware of a suitable effects analysis for C or C++,
>> and consequently have no current plans to address this capability.
>>
>> In principle, TRA can be performed entirely one translation-unit at a
>> time. However, this approach requires unrealistic numbers of
>> user-written annotations.  Past research has demonstrated that TRA is
>> most effective (in terms of bang for the end-user's effort) when
>> performed over large groups of translation units. In this mode, we
>> require annotations on the interfaces between groups of TUs, and infer
>> annotations within each group.  The potential for using Modules (or
>> something similar) should be obvious. Note that the cost of the
>> analysis is O(n) in program size in the typical case.
>>
>> We realize that this RFC doesn't touch on implementation details (we
>> wanted to spare you the wall of text).  However, we're happy to
>> discuss our envisioned implementation strategy if you have any
>> questions.  We propose to proceed by giving small RFCs on
>> implementation details which may require us to introduce new concepts,
>> but otherwise go with post-commit reviews for the majority of the
>> work.
>>
>> Our implementation strategy from 50,000 feet:
>> * Start by supporting C (only).
>> * Begin adding C++ support in US Govt. FY14 (starting Oct. 1, 2013)
>> * Add new declaration attributes
>> * Add new statement attributes and round out the statement attribute
>> subsystem
>> * Emit YAML-based sidecar files (either during compilation or from the
>> Static Analyzer)
>> * Produce a utility application to read the sidecar files, perform the
>> analysis, and produce results.
>> * Add a static analyzer pass which reads the results and emits diagnostics
>>
>> Our Team:
>> Dr. Dean Sutherland and I work for the securing coding group at CERT
>> (within the Software Engineering Institute of Carnegie Mellon
>> University) and will be the primary people working on
>> implementing thread role analysis.  We are funded to develop and
>> maintain this system for at least the next 16 months. You can find
>> more information about CERT and the secure coding group at:
>> http://www.cert.org/secure-coding/.
>>
>> ~Aaron
>> _______________________________________________
>> cfe-commits mailing list
>> cfe-commits at cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
>>
>
>

-- 
DeLesley Hutchins | Software Engineer | delesley at google.com | 505-206-0315
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20130620/d48a1805/attachment.html>