Behavioral analysis for message-passing application programs

Details Behavioral analysis for message-passing application programs Behavioral analysis for message-passing application programs

2007-04-10

2007-04-10

Khatri, Anil (Department: 2191)

Data processing: software development, installation, and managem

Software program development tool

Modeling

C717S103000, C717S140000, C706S046000

Reexamination Certificate

active

10136680

ABSTRACT:
A system and method for modeling a message-passing program module using type annotations is disclosed. The message-passing program module is constructed with operations that communicate with operations of other message-passing program modules in an asynchronous computing environment. Type annotations are communication protocols that represent processes of input and/or output actions that the program module developer expects each operation to perform or take on a selected set of communication channels. During development of the program module, the type annotations are declared at each operation of the program module. Soundness of the type annotations and whether implementation of the program module conforms to the type annotations is checked using a type system. If the program module is well-typed and well-implemented, the type system abstracts a behavioral module of the message-passing program module that reflects the relevant processes expressed by the type annotations. A model checker determines whether the behavioral module is in fact a valid abstraction of the implementation, and if so, evaluates one or more properties of the behavioral module to render a conclusion about these properties for the program module.

REFERENCES:
patent: 5388189 (1995-02-01), Kung
patent: 5548756 (1996-08-01), Tantry et al.
patent: 5572733 (1996-11-01), Ryu et al.
patent: 5758160 (1998-05-01), McInerney et al.
patent: 5960200 (1999-09-01), Eager et al.
patent: 5991538 (1999-11-01), Becker
patent: 6118448 (2000-09-01), McMillan et al.
patent: 6233620 (2001-05-01), Gish
patent: 6266805 (2001-07-01), Nwana et al.
patent: 6314555 (2001-11-01), Ndumu et al.
patent: 6405363 (2002-06-01), Carlson et al.
patent: 6421681 (2002-07-01), Gartner et al.
patent: 6434598 (2002-08-01), Gish
patent: 6535864 (2003-03-01), Zahn
patent: 6631362 (2003-10-01), Ullman et al.
patent: 6813761 (2004-11-01), Das et al.
patent: 6826579 (2004-11-01), Leymann et al.
patent: 6842894 (2005-01-01), Havemose
patent: 6904588 (2005-06-01), Reddy et al.
patent: 6904590 (2005-06-01), Ball et al.
patent: 6907395 (2005-06-01), Hunt et al.
patent: 6968535 (2005-11-01), Stelting et al.
patent: 6981249 (2005-12-01), Knoblock et al.
Niu et al, “Composale semantics fro model based noations”, ACM SIGSOFT, pp. 149-158, 2002.
Jurjens, “A UML statecharts semntics with message passing”, ACM SAC, pp. 1009-1013, 2002.
Mehra et al, “A comparision of two model based performance prediction techniques for message passing parallel programs”, ACM SIGMETRICS, pp. 181-190, 1994.
Chaki et al, “Types as models model checking message passing programs”, ACM POPL, pp. 45-57, 2002.
Jaroodi et al, “An object passing model for parallel programming”, IEEE COMPSAC, pp. 138-143, 2003.
Grieskamp et al, “A schema language for coordinating construction and composition of partial behavior descriptions”, ACM SCESM, pp. 59-65, 2006.
Ellis et al, “Extending the behavioral capabilities of the object oriented paradigm with an active model of progation”, ACM pp. 319-325, 1990.
Ghelli, A static type system for message passing:, ACM OOPSLA, pp. 129-145, 1991.
M. Abadi and L. Lamport. The Existence of Refinement Mappings. In LICS 88: Logic in Computer Science, pp. 165-175. IEEE Computer Society Press, 1988.
E. Brinksma, B. Jonsson, and F. Orava. Refining Interfaces of Communicating Systems. In TAPSOFT 91: Theory and Practice of Software Development, LNCS 494, pp. 297-312. Springer-Verlag, 1991.
Customer Support Consortium (CSC) and Desktop Management Task Force (DMTF). Service Incident Exchange Standard (sis) Specification, version 1.1. Technical report, DMTF. Available at www.dmtf.org.
C. Fournet, F. Le Fessant, L. Maranget, and A. Schmitt. The JoCaml language beta release, documentation and user's manual. Technical report. INRIA, Jan. 2001. Available at pauillac.inria.fr/jocaml/htmlman.
C. Fournet and G. Gonthier. The Join calculus: a language for distributed mobile programming. In Lecture Notes for Applied Semantics Summer School, Caminha Sep. 2000.
Abadi, M. and Lamport, L., “Composing Specifications”,ACM Transactions on Programming Languages and Systems, 15(1):73-132, 1993.
Abadi, M. and Lamport, L., “Conjoining Specifications”,ACM Transactions on Programming Languages and Systems, 17(3):507-534, 1995.
Agha, Gul A.,Actors: A Model of Concurrent Computation in Distributed Systems, The MIT Press, 1988.
Alur, R. and Henzinger T., “Reactive Modules”,Proceedings of the 11th Annual Symposium on Logic in Computer Science, pp. 207-218, IEEE Computer Society Press, 1996.
Alur, R., Henzinger, T., Kupferman, O. and Vardi, M., “Alternating Refinement Relations”,CONCUR 98: Concurrency Theory, LNCS 1466, pp. 163-178, Springer-Verlag, 1998.
Alur, R., Henzinger, T.A., Mang, F.Y.C., Qadeer, S., Rajamani, S.K. and Tasiran, S., MOCHA: Modularity in Model Checking,Computer Aided Verification, LNCS, pp. 521-525, Springer-Verlag, 1998.
Amtoft, Torben; Nielson, Flemming and Nielson, Hanne R.,Type and Effect Systems, Behaviours for Concurrency, Imperial College Press, 1999.
Christensen, S., Hirshfeld, Y., and Moller, F., “Decidable Subsets of CCS”,The Computer Journal, 37(4):233-242, 1994.
Clarke, Edmund M. Jr., Grumberg, Orna, and Peled, Doron A.,Model Checking, MIT Press, 1999.
Cleaveland, R., Parrow, J., and Steffen, B., “The Concurrency Workbench: A Semantics-Based Tool for the Verification to Concurrent Systems”,ACM Transactions on Programming Languages and Systems, 15(1):36-72, 1993.
de Alfaro, L. and Henzinger, T., “Interface Theories for Component-Based Design”,EMSOFT 01 Embedded Software, LNCS, Springer-Verlag, 2001.
Dill, David L.,Trace Theory for Automatic Hierarchical Verification of Speed-Independent Circuits, MIT Press, 1989.
Dwyer, M., Hatcliff, J., Joehanes, R., Laubach, S., Pasareanu, C., Visser, R.W. and Zheng, H., “Tool-Supported Program Abstraction for Finite-State Verification”,ICSE 01: Software Engineering(to appear), 2001.
Eiriksson, A., “The Formal Design of 1M-Gate ASICs”, G. Gopalakrishnan and P. Windley, editors,FMCAD 98: Formal Methods in Computer-Aided Design, Lecture Notes in Computer Science 1522, pp. 49-63, Springer-Verlag, 1998.
Feret, J., “Confidentiality Analysis of Mobile Systems”,Proceedings of the International Static Analysis Symposium(SAS'00), Springer LNCS 1824, 2000.
Flanagan C., and Freund, S.N., “Type-Based Race Detection for Java”,ACM Symposium on Applied Computing, pp. 219-232, ACM, 2000.
Flanagan, C. and Abadi, M., “Types for Safe Locking”,Proceedings of ESOP 1999, pp. 91-108, Springer LNCS 1576, 1999.
Fournet, C. and Gonthier, G., “The Reflexive CHAM and the Join-Calculus”,POPL 96: Principles of Programming Languages, pp. 372-385, ACM, 1996.
Gordon, A. and Jeffrey, A., Typing Correspondence Assertions for Communication Protocols,MFPS: Mathematical Foundations of Programming Semantics, pp. 99-120, BRICS Notes Serial NS-01-2, 2001.
Gosling, James; Joy, Bill; Steele, Guy and Bracha, Gilad,The Java™ Language Specification, Addison-Wesley, 1996.
Hardin, R., Har'El, Z., Kurshan, R., “COSPAN”,Computer Aided Verification, LNCS 1102, pp. 423-427, Springer-Verlag, 1996.
Henzinger, T., Liu, X., Qadeer, S., and Rajamani, S., “Formal Specification and Verification of a Dataflow Processor Array”,Proceedings of the International Conference on Computer-Aided Design, pp. 494-499, IEEE Computer Society Press, 1999.
Henzinger, T., Qadeer, S. and Rajamani, S., You Assume, We Guarantee: Methodology and Case Studies,CAV 98: Computer Aided Verification, LNCS 1427, pp. 440-451, Springer-Verlag, 1998.
Henzinger, T.A., Qadeer, S., Rajamani, S.K. and Tasiran, S., “An Assume-Guarantee Rule for Checking Simulation”,FMCAD 98: Formal Methods in Computer-Aided Design, LNCS 1522, pp. 421-432, Springer-Verlag, 1998.
Hoare, C.,Communicating Sequential Processe

Affiliated with

Also associated with

Rating

Behavioral analysis for message-passing application programs does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Behavioral analysis for message-passing application programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Behavioral analysis for message-passing application programs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3789066