Concurrency Analysis Tool Suite (CATS)

1. Name:
   Concurrency Analysis Tool Suite (CATS)

2. Source:
   University of California, Irvine (UCI) Arcadia project

3. Brief description:
   CATS is a set of tools for statically analyzing concurrent programs. The analyses are performed on the task interaction concurrency graph (TICG), an enhanced reachability graph. CATS includes a TICG builder, deadlock checker, model checker for verifying temporal logic assertions, and support tools such as a task interaction graph viewer.

4. Evaluation against applicable general dimensions:
   1. Availability: commercial/licensed/public domain
      Cost-free license from UCI Arcadia project.

   2. Cost:
      Free if obtained over the Internet, media charge for magnetic tape.

   3. Degree of support/maturity/testing/usage:
      Limited support; used within the project to analyze some large concurrent programs, including the Chiron UIMS.

   4. Speed:
      Execution time for the dining philosophers problem:

      
      Problem   TICG     TICG     SPARC2 CPU
       size     States   Edges     seconds
      -------  -------  -------   ----------
         2          8       11         6
         8       6560    34985        28
         9      19682   118090       339
        10      59048   393651      9124

   5. Computing platforms:
      Sun 4

   6. Language compatibilities:
      Suitable for programs using Ada-style rendezvous; tasking structure is expressed using task interaction graphs (TIGs) which are now constructed manually, though a TIG extractor for Ada code is under development.

   7. Footprint:
      1. Entire distribution: 40 MB
      Includes sources, Verdix/SunAda libraries, executables, examples, and documentation

   8. Openness/integrability/source availability:
      Source code (Ada) provided.

   9. Extensibility:
      Standalone tool suite designed for extensibility, source code provided.

   10. Pedigree: ARPA developed?
       Developed under ARPA Arcadia program.

5. Contact person(s)

   Professor Richard N. Taylor
   Department of Information and Computer Science (ICS)
   University of California
   Irvine, CA 92717-3425
   taylor@ics.uci.edu
   (714) 824-6429
   (714) 824-4056 - fax
   

6. Pointers to literature, demos, etc.:
   Michal Young, Richard N. Taylor, Kari Forester, and Debra Brodbeck. Integrated concurrency analysis in a software development environment. In Proceedings of the ACM SIGSOFT '89 Third Symposium on Software Testing, Analysis, and Verification (TAV3), pages 200-209, Key West, Florida, December 1989. Published as ACM SIGSOFT Software Engineering Notes 14 (8).