Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

A configuration management (CM) tool is supposed to build a consistent software system following incremental changes to the system. The notion of consistency usually is purely syntactic, having to do with the sorts of properties analyzed by compilers. Semantic consistency traditionally has been studied in the field of formal methods and has been considered an impractical goal for CM. Although the semantic CM problem is undecidable, it is possible to obtain a structural approximation of the semantic effects of a change in a finite number of steps. Our approximation technique is formalized in logic and is based on information-theoretic properties of programs. The method in its present form applies to many but not all software systems, and it is programming-language independent. To the best of our knowledge, the semantic CM problem has not been formalized previously in nonsemantic terms, and we believe that our simplified formulation offers the potential for considerably more powerful debugging and configuration management tools.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Gregory R. Andrews , Richard P. Reitman, An Axiomatic Approach to Information Flow in Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.1, p.56-76, Jan. 1980 [doi>10.1145/357084.357088]
• 3: D. Bjorner and C.B. Jones. Formal Specification and Software Development. Series in Computer Science. Prentice-Hall International, 1982.
• 4: Ellis Choen, Information transmission in computational systems, Proceedings of the sixth ACM symposium on Operating systems principles, p.133-139, November 16-18, 1977, West Lafayette, Indiana, United States
• 5: The EHDM Specification Language. Computer Science Laboratory, SRI International, May 1989.
• 6: Johan de Kleer, An assumption-based TMS, Artificial Intelligence, v.28 n.2, p.127-162, March 1986 [doi>10.1016/0004-3702(86)90080-9]
• 7: Dorothy E. Denning, A lattice model of secure information flow, Communications of the ACM, v.19 n.5, p.236-243, May 1976 [doi>10.1145/360051.360056]
• 8: Dorothy E. Denning , Peter J. Denning, Certification of programs for secure information flow, Communications of the ACM, v.20 n.7, p.504-513, July 1977 [doi>10.1145/359636.359712]
• 9: J. Doyle. A truth maintenance system. Artificial Intelligence, 12:231-272, 1979.
• 10: Kokichi Futatsugi , Joseph A. Goguen , Jean-Pierre Jouannaud , José Meseguer, Principles of OBJ2, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.52-66, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318610]
• 11: Joseph Goguen and Timothy Winkler. Introducing OBJ3. Technical Report SRI-CSL-88-9, SRI International, Computer Science Laboratory, August 1988.
• 12: D.I. Good, R.L. Akers, and L.M. Smith. Report on Gypsy 2.05. Technical Report CLI-1, Computational Logic Inc., Austin, Texas, 1986.
• 13: D.I. Good, B.L. DiVito, and M.K. Smith. Using the Gypsy methodology. Technical report, Computational Logic Inc., Austin, Texas, 1988.
• 14: J.V. Guttag, J.J. Horning, and J.M. Wing. The Larch family of specification languages. IEEE Software, 2(5):24-36, September 1985.
• 15: J.V. Guttag, J.J. Horning, and J .M. Wing. Larch in five easy pieces. Technical Report 5, Digital Systems Research Center, Palo Alto, California, July 1985.
• 16: Ian Hayes, Specification case studies, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1987
• 17: C. A. R. Hoare, An axiomatic basis for computer programming, Communications of the ACM, v.12 n.10, p.576-580, Oct. 1969 [doi>10.1145/363235.363259]
• 18: S. Horwitz , T. Reps , D. Binkley, Interprocedural slicing using dependence graphs, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.35-46, June 20-24, 1988, Atlanta, Georgia, United States
• 19: D.C. Luckham and F.W. von Henke. An overview of Anna, A specification language for Ada. IEEE Software, 2(2):9-23, March 1985.
• 20: David C. Luckham , Friedrich W. von Henke , Bernd Krieg-Brückner , Olaf Owe, ANNA: a language for annotating Ada programs, Springer-Verlag New York, Inc., New York, NY, 1987
• 21: J. McHugh and D.I. Good. An information flow tool for Gypsy. In Proc. 1985 Symposium on Security and Privacy, pages 46-48, Oakland, California, April 1985. IEEE Computer Society.
• 22: M. Moriconi, A designer/verifier's assistant, Readings in artificial intelligence and software engineering, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1986
• 23: M. Moriconi and G.A. Harrison. Reasoning about design changes. Technical Report SRI-CSL-88-14, Computer Science Laboratory, SRI International, November 1988. (submitted for journal publication).
• 24: D. E. Perry, Software interconnection models, Proceedings of the 9th international conference on Software Engineering, p.61-69, March 1987, Monterey, California, United States
• 25: D. E. Perry, Version control in the Inscape environment, Proceedings of the 9th international conference on Software Engineering, p.142-149, March 1987, Monterey, California, United States
• 26: R. Reiter. On closed world data bases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 55-76, New York, New York., 1978. Plenum Press.
• 27: J.M. Rushby. The security model of Enhanced HDM. In Proceedings 7th DOD/NBS Computer Security Initiative Conference, pages 120-136, Gaithersburg, Maryland., September 1984.
• 28: R.W. Schwanke and G.E. Kaiser. Certification of programs for secure information flow. In J.F.H. Winkler, editor, Proceedings of the International Workshop on Software Version and Configuration Control, pages 98-118. B.G. Teubner Stuttgart, 1988.
• 29: Robert W. Schwanke , Gail E. Kaiser, Smarter recompilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.627-632, Oct. 1988 [doi>10.1145/48022.214505]
• 30: C.E. Shannon. A mathematical theory of communication. Bell Systems Technical Journal, 27:379- 423 (July), 623-656 (October), 1948.
• 31: John C. Shepherdson, Negation as failure: a comparison of Clark's completed data base and Reiter's closed world assumption, Journal of Logic Programming, v.1 n.1, p.51-79, June 1984 [doi>10.1016/0743-1066(84)90023-2]
• 32: L. Sterling and E. Shapiro. The Art of Prolog. The MIT Press, 1986.
• 33: W.F. Tichy. Tools for software configuration management. In J.F.H. Winkler, editor, Proceedings of the International Workshop on Software Version and Configuration Control, pages l-20. B.G. Teubner Stuttgart, 1988.
• 34: F.W. von Henke, J.S. Crow, R. Lee, J.M. Rushby, and R.A. Whitehurst. The EHDM verification environment: An overview. In Proceedings 11th National Computer Security Conference, pages 147-155, Baltimore, Maryland, October 1988. NBS/NCSC.
• 35: M. Weiser. Program slicing. IEEE Transactions on Software Engineering, SE-10(4):352-357, July 1984.
• 36: J.F.H. Winkler, editor. Proceedings of the International Workshop on Software Version and Configuration Control. B.C. Teubner Stuttgart, 1988.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Version control
      D.2.9 Management
          Subjects: Software configuration management
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

General Terms:
Algorithms, Design, Languages, Management