Cesar: a static sequencing constraint analyzer

ABSTRACT

This paper relates experience with building and using a programmable sequencing analyzer based on data flow analysis algorithms. An earlier paper described both the motivation for and the specification of Cecil, a powerful language for defining constraints on the sequencing of events and gave an algorithm for mapping the sequencing specifications defined by Cecil to data flow analysis algorithms. In this paper, we sketch the architecture of Cesar, a system for carrying out the analysis of Cecil sequencing constraints, describe the problems arising in the analysis of real-world programs, and indicate how we resolved these problems. Finally, we describe our experience in using Cesar, citing speed and efficiency characteristics of the current implementation, and suggesting the error-detection features and powers of Cesar.

REFERENCES

• 1: Krzysztof R. Apt, A Static Analysis of CSP Programs, Proceedings of the Carnegie Mellon Workshop on Logic of Programs, p.1-17, June 06-08, 1983
• 2: V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. Faradzev. On economical construction of the transitive closure of a directed graph. Soviet Math. Doklady, 11:1209-1210, 1970.
• 3: G S Avrunin , L K Dillon , J C Wileden , W E Riddle, Constrained expressions: Adding analysis capabilities to design methods for concurrent software systems, IEEE Transactions on Software Engineering, v.12 n.2, p.278-292, Feb. 1986
• 4: G. Bristow , C. Drey , B. Edwards , W. Riddle, Anomaly detection in concurrent programs, Proceedings of the 4th international conference on Software engineering, p.265-273, September 17-19, 1979, Munich, Germany
• 5: E. M. Clarke , E. A. Emerson , A. P. Sistla, Automatic verification of finite-state concurrent systems using temporal logic specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.2, p.244-263, April 1986 [doi>10.1145/5397.5399]
• 6: G. M. Clemm. The Odin specification language. In Proc. of the Int'l. Workshop on Software Version and Configuration Control, pages 141-155, January 1988.
• 7: Geoffrey Michael Clemm, The Odin system: an object manager for extensible software environments, University of Colorado at Boulder, Boulder, CO, 1986
• 8: G. M. Clemm. personal communication. March 1988.
• 9: L. K. Dillon, Constrained Expression: Toward Broad Applicability of Analysis Methods, University of Massachusetts, Amherst, MA, 1986
• 10: Bo Einarsson , W. Morven Gentleman, Mixed language programming, Software—Practice & Experience, v.14 n.4, p.383-392, April 1984 [doi>10.1002/spe.4380140410]
• 11: P. Fairfield , M. A. Hennell, Data flow analysis of recursive procedures, ACM SIGPLAN Notices, v.23 n.1, p.48-57, Jan., 1988 [doi>10.1145/44304.44308]
• 12: L. D. Fosdick and L. J. Osterweil. DAVE-a validation, error detection and documentation system for FOR- TRAN programs. Software-Practice and Experience, 6:473-486, 1976.
• 13: Stefan M. Freudenberger, On the use of global optimization algorithms for the detection of semantic programming errors (setl, data flow, type finding), 1984
• 14: William E Howden, Functional program testing and analysis, McGraw-Hill, Inc., New York, NY, 1986
• 15: W. E. Howden. A general model for static analysis. In Proc. of the 16th Hawaii Int'l. Conf. on System Sciences, pages 163-169, 1983.
• 16: D. E. Knuth. An empirical study of FORTRAN programs. Software-Practice and Experience, 1:105-135, 1971.
• 17: D. C. Luckham, D. P. Helmbold, S. Meldal, D. L. Bryan, and M. A. Haberler. Task Sequencing Language for Specifying Distributed Ada Systems (TSL-1). Technicd Report CSL-TR-87-334, Computer Systems Laboratory, Stanford Univ., July 1987.
• 18: Kurt Michael Olender , Leon J. Osterweil, Cecil/cesar: specification and static evaluation of sequencing constraints, 1988
• 19: K. M. Olender and L. J. Osterweil. Specification and static evaluation of sequencing constraints in software. In Proc. of the Workshop on Software Testing, pages 2- 9, July 1986.
• 20: L. J. Osterweil. Toolpack-an experimental software development environment research project. IEEE Trans. on Software Engineering, SE-93673-685, November 1983.
• 21: Barbara G. Ryder , Marvin C. Paull, Elimination algorithms for data flow analysis, ACM Computing Surveys (CSUR), v.18 n.3, p.277-316, Sept. 1986 [doi>10.1145/27632.27649]
• 22: M. Sharir and A. Pneuli. Two approaches to interprocedural data flow analysis. In S. S. Muchnick and N. D. Jones, editors, Program Flow Analysis, pages 189-233, Prentice-Hall, 1981.
• 23: Robert Endre Tarjan, Fast Algorithms for Solving Path Problems, Journal of the ACM (JACM), v.28 n.3, p.594-614, July 1981 [doi>10.1145/322261.322273]
• 24: Richard N. Taylor, A general-purpose algorithm for analyzing concurrent programs, Communications of the ACM, v.26 n.5, p.361-376, May 1983 [doi>10.1145/69586.69587]
• 25: R. N. Taylor and L. J. Osterweil. Anomaly detection in concurrent software by static data flow analysis. IEEE Trans. on Software Engineering, 8E6:265-277, May 1980.
• 26: L. L. Werner and W. E. Howden. Fault Detection in COBOL Programs by Means of Data Usage Analysis. Technical Report CS-87-111, Dept. of Computer Science, Univ. of California, San Diego, December 1987.
• 27: Cindy Wilson , Leon J. Osterweil, Omega—a data flow analysis tool for the C programming language, IEEE Transactions on Software Engineering, v.11 n.9, p.832-838, Sept. 1985 [doi>10.1109/TSE.1985.232542]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program verification

General Terms:
Algorithms, Languages, Reliability, Verification