Component Protocol/Sequencing Constraints

Component Protocols/Sequencing Constraints Bibliography

Component-based software development has increasingly gained popularity in industry. Correct component usage is critical to successful reuse of components. However, the expected component usage is rarely specified explicitly. One recent area of research has been to infer specifications (in the form of pre/post-conditions and in the form of protocols or sequencing constraints) using both static and dynamic techniques. The following papers address various forms of specification inference. Compare and contrast these approaches, identifying their strengths and weaknesses, and identify several possible research approaches for pushing the state-of-the-art forward in this area.

The following is my charge of general exam:

John Whaley, Michael C. Martin and Monica S. Lam. Automatic Extraction of Object-Oriented Component Interfaces, In Proceedings of the International Symposium on Softawre Testing and Analysis, pp. 218-228, July 2002 [PDF] [Slides]
Glenn Ammons, Ras Bodik, James Larus, Mining Specifications. In Proceedings of Principles of Programming Languages (POPL02), Portland, Oregon, 16-18 January 2002. [PDF] [Slides] [Notes] Ammons
S. P. Reiss and M. Renieris. Encoding program executions. In Proceedings of the International Conference on Software Engineering, 2001.[PDF]
Jonathan E. Cook and Alexander L. Wolf. Discovering Models of Software Processes from Event-Based Data, ACM Transactions on Software Engineering and Methodology, vol. 7, no. 3, July 1998, pp. 215-249. [PDF]
M. El-Ramly, E. Stroulia, P. Sorenson. Interaction-Pattern Mining: Extracting Usage Scenarios from Run-time Behavior Traces, The Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, July 23 - 26, 2002, Edmonton, Alberta, Canada [PDF] CELLEST Mohammad El-Ramly Stroulia
D. Lie, A. Chou, D. Engler, and D. Dill. A simple method for extracting models from protocol code. In Proceedings of the 28th Annual International Symposium on Computer Architecture, pp. 192-203, July 2001.[PDF] [Slides]

The following is my general exam report:

Tao Xie. Software Component Protocol Inference. General Examination Report, University of Washington Department of Computer Science and Engineering, (Seattle, WA), June 2002. [PDF][Slides]

Extracting Component Protocols (more):

Dawson Engler, David Yu Chen, Seth Hallem, Andy Chou, and Benjamin Chelf. Bugs as deviant behavior: A general approach to inferring errors in systems code. In Proceedings of Eighteenth ACM Symposium on Operating Systems Principles, pp. 57-72, October 2001. [PDF]
D. Wagner and D. Dean. Intrusion detection via static analysis. In Proceedings of the IEEE Symposium on Security and Privacy, pp. 156-169, May 2001.[PDF]
James Corbett, Matthew Dwyer, John Hatcliff, Corina Pasareanu, Robby, Shawn Laubach, Hongjun Zheng, Bandera : Extracting Finite-state Models from Java Source Code, in Proceedings of the 22nd International Conference on Software Engineering, June, 2000 [PDF]
Matthew Dwyer, John Hatcliff, Roby Joehanes, Shawn Laubach, Corina Pasareanu, Robby, Willem Visser, Hongjun Zheng, Tool-supported Program Abstraction for Finite-state Verification, in Proceedings of the 23rd International Conference on Software Engineering, May, 2001. [PDF]
Patrick Lam, Martin Rinard, A Type System and Analysis for the Automatic Extraction and Enforcement of Design Information,
ECOOP 2003. [PDF]
G.J. Holzmann and M.H. Smith, An automated verification method for distributed systems software based on model extraction, IEEE Trans. on Software Engineering, Vol. 28, 4, pp. 364-377, April 2002. [PDF] Modex tool
G. Ammons, D. Mandein, R. Bodik, J. R. Larus. Debugging Temporal Specifications with Concept Analysis. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation, San Diego, California, June 2003. [PDF]
G. Ammons. Strauss: A Specification Miner. Ph.D. dissertation, University of Wisconsin, Madison, Department of Computer Science, May. 2003. [PDF]

Other dynamic analyses:

Rainer Koschke und Yan Zhang, Component Recovery, Protocol Recovery and Validation. In: 3. Workshop Software-Reengineering, Bad Honnef (10./11.Mai 2001), Fachberichte Informatik, Universität Koblenz-Landau, Nr. 1/2002, pages 73-76, Januar 2002. [PDF] [bauhaus]
W.M.P. van der Aalst. Process Design by Discovery: Harvesting Workflow Knowledge from Ad-hoc Executions. In M. Jarke, D.E. O'Leary, and R. Studer, editors, Knowledge Management: An Interdisciplinary Approach, Dagstuhl, July 2000. Dagstuhl Seminar Report, 281. [PDF]
T. Weijters and W.M.P. van der Aalst. Process Mining: Discovering Workflow Models from Event-Based Data. In B. Kröse, M. de Rijke, G. Schreiber, and M. van Someren, editors, Proceedings of the 13th Belgium-Netherlands Conference on Artificial Intelligence (BNAIC 2001), pages 283-290, 2001 [PDF]
L. Maruster, A.J.M.M. Weijters, W.M.P. van der Aalst, and A. van den Bosch. Process Mining: Discovering Direct Successors in Process Logs. In Proceedings of the 5th International Conference on Discovery Science (Discovery Science 2002), volume 2534 of Lecture Notes in Artificial Intelligence, pages 364-373. Springer-Verlag, Berlin, 2002 [PDF]
A.J.M.M. Weijters and W.M.P. van der Aalst. Rediscovering Workflow Models from Event-Based Data. In Proceedings of the Third International NAISO Symposium on Engineering of Intelligent Systems (EIS 2002), pages 65-65. NAISO Academic Press, Sliedrecht, The Netherlands, 2002.[PDF] [publications]

Static Checking Component Protocol Conformance:

S. Butkevich, M. Renedo, G. Baumgartner, and M. Young. Compiler and tool support for debugging object protocols. In Proceedings of the 8th International Symposium on the Foundations of Software Engineering, pages 50--59. ACM, November 2000. [PDF] [Slides][Slides] RefMaterial
Robert DeLine and Manuel Fähndrich. Enforcing high-level protocols in low-level software. In Proceedings of the ACM Conference on Programming Language Design and Implementation, June 2001, pages 59-69. [PDF]
Thomas Ball, Sriram K. Rajamani, Automatically Validating Temporal Safety Properties of Interfaces, SPIN 2001, Workshop on Model Checking of Software, LNCS 2057, May 2001, pp. 103-122. [PDF]
Manuvir Das, Sorin Lerner, and Mark Seigle, ESP: Path-Sensitive Program Verification in Polynomial Time, PLDI '02: Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation,Berlin, Germany, June 2002. [PDF]
Sagar Chaki, Sriram K. Rajamani, Jakob Rehof, Types as Models: Model Checking Message Passing Programs, POPL 2002, [PDF]
Jamieson M. Cobleigh, Lori A. Clarke, Leon J. Osterweil. FLAVERS: A Finite State Verification Technique for Software Systems. IBM Systems Journal, 41(1):140-165, 2002 [PDF]
J. Field, D. Goyal, G. Ramalingam, and E. Yahav., Shallow finite state verification, November 2002. [PDF]
Yahav E, Verifying Safety Properties of Concurrent Java Programs using 3-Valued Logic, POPL 2001 [PDF]
Yahav E., Reps T., Sagiv M., and Wilhelm R., Verifying Temporal Heap Properties Specified via Evolution Logic, ESOP 2003 [PDF]
Kurt M. Olender, Leon J. Osterweil, Interprocedural Static Analysis of Sequencing Constraints. TOSEM 1(1): 21-52 (1992) [PDF]
- Kurt M. Olender, Leon J. Osterweil: Cecil: A Sequencing Constraint Language for Automatic Static Analysis Generation. TSE 16(3): 268-280 (1990) [PDF]
- Kurt M. Olender, Leon J. Osterweil, Cesar: a static sequencing constraint analyzer, Proceedings of the 3rd Testing, Analysis, and Verification Symposium, December 1989, pages 66-74 [PDF]
Bieman, J.M.; Olender, K.M., Using algebraic specifications to find sequencing defects, 1993. Proceedings of Fourth International Symposium on Software Reliability Engineering, 3-6 Nov 1993 Page(s): 226 -232 [PDF]
G. Ramalingam, A. Warshavsky, J. Field, D. Goyal, M. Sagiv, Deriving Specialized Program Analyses for Certifying Component-client Conformance, PLDI02, 83-94 [PDF]
Paola Inverardi, Alexander L. Wolf, and Daniel Yankelevich. Static Checking of System Behaviors Using Derived Component Assumptions. ACM Transactions on Software Engineering and Methodology, vol. 9, no. 3, July 2000, pp. 239-272 [PDF]

Specifying Component Protocol:

Andrés Farias and Mario Südholt, On components with explicit protocols satisfying a notion of correctness by construction. Distributed Objects and Applications 2002 (DOA 2002). Irvine, California, USA. To appear. Long version: [PDF] [PPT].
Andrés Farías, Yann-Gaël Guéhéneuc, and Mario Südholt, Integrating Behavioral Protocols in Enterprise Java Beans, Proceedings of the OOPSLA Workshop on Behavioral Semantics, 2002.[PDF] [PPT].
Daniel M. Yellin, Robert E. Storm: Protocol Specifications and Component Adaptors. TOPLAS 19(2): 292-333 (1997) [PDF]
- Daniel M. Yellin, Robert E. Strom: Interfaces, Protocols, and the Semi-Automatic Construction of Software Adaptors. OOPSLA 1994: 176-190 [PDF]
L. de Alfaro and T. A. Henzinger, Interface Automata, Proc. ACM Symp. Foundations of Software Engineering, Vienna, Austria, September 2001 [PDF] Chic: A JBuilder plug-in for checking interface compatibility
Il-Hyung Cho; McGregor, J.D.; Krause, L., A protocol based approach to specifying interoperability between objects, Technology of Object-Oriented Languages, 1998. TOOLS 26. Proceedings , 3-7 Aug 1998 Page(s): 84 -96 [PDF]
James Corbett, Matthew Dwyer, John Hatcliff, Robby, Expressing Checkable Properties of Dynamic Systems: The Bandera Specification Language, June, 2001. KSU CIS Technical Report 2001-04. [PDF]
Plasil, F., Visnovsky, S., Behavior Protocols for Software Components, IEEE Transactions on Software Engineering, vol. 28, no. 11, Nov 2002 [PDF]
R. H. Campbell and A. N. Habermann: The Specification of Process Synchronization by Path Expressions, in Operating Systems, International Symposium, Rocquencourt, vol. 16, Lecture Notes in Computer Science, 1974, pp. 89-102.

Testing Based on Sequencing Constraints:

R. H. Carver and K. C. Tai, Use of sequencing constraints for specification-based testing of concurrent programs, IEEE Trans. Software Engineering, Vol. 24, No. 6, June 1998, 471-490. [PDF]
Bengi Karaçali, Kuo-Chung Tai, Automated Test Sequence Generation Using Sequencing Constraints for Concurrent Programs. International Symposium on Software Engineering for Parallel and Distributed Systems (PDSE 1999), 97- [PDF]

Applications in Security:

C. C. Michael, Anup K. Ghosh: Simple, state-based approaches to program-based anomaly detection. ACM Transactions on Information and System Security, 5(3): 203-237, 2002 [PDF]
Lane, T. and Brodley, C. E. Temporal Sequence Learning and Data Reduction for Anomaly Detection ACM Transactions on Information and System Security, 2(3). pp 295--331. 1999 [PS]
Guy Helmer, Johnny Wong, Vasant Honavar, and Les Miller. Automated Discovery of Concise Predictive Rules for Intrusion Detection. Journal of Systems and Software, Volume 60, Issue 3 (February 2002) [PS]
R. Sekar, M. Bendre, P. Bollineni and D. Dhurjati, A Fast Automaton-Based-Method for Detecting Anomalous Program Behaviors, IEEE Symposium on Security and Privacy, 2001. [PS]
T. Lane, C.E. Brodley, An application of machine learning to anomaly detection, in: Proc. 20th Annual National Information Systems Security Conference, Vol. 1, 1997, pp. 366--380. [PS]
Yingjiu Li, Ningning Wu, X. Sean Wang, and Sushil Jajodia, Enhancing Profiles for Anomaly Detection Using Time Granularities, Workshop on Intrusion Detection, in conjunction with the 7th ACM Conference on Computer and Communication Security. Athens, Greece, 1-4 November 2000. [PsS]
W. Lee, S. J. Stolfo. Data mining approaches for intrusion detection. In Proceedings of Seventh USENIX Security Symposium, pages 66-72. San Antonio, TX, January, 1998. [PDF] [Slide]
W. Lee, S. Stolfo, and P. Chan. Learning patterns from UNIX process execution traces for intrusion detection. In Proceedings of AAAI-97 Workshop on AI Approaches to Fraud Detection and Risk Management, pages 50-56, 1997.[PS]
Christoph Michael and Anup K. Ghosh. Using finite automata to mine execution data for intrusion detection: A preliminary report. In Recent Advances in Intrusion Detection, pages 66--79, 2000. [PS]
Ghosh, A.K., Schwartzbard, A., and Schatz. M. Learning program behavior profiles for intrusion detection. in Proceedings of the SANS Third Conference and Workshop on Intrusion Detection and Response, 1999. [PDF]
A.K. Ghosh, C.C. Michael, and M.A. Schatz, A Real-Time Intrusion Detection System Based on Learning Program Behavior, Recent Advances in Intrusion Detection; Third International Workshop, RAID 2000. [PDF]
R. Sekar and P. Uppuluri. Synthesizing fast intrusion prevention/detection systems from high-level specifications. In USENIX Security Symposium, 1999. [PS]

Dynamic Reverse Engineering:

Keith Chan, Zhi Cong Leo Liang, Amir Michail, Design Recovery of Interactive Graphical Applications, ICSE 2003 [PDF] DRT
Marcus, A., Maletic, J.I. Recovering Documentation-to-Source-Code Traceability Links using Latent Semantic Indexing, in Proceedings of the 25th IEEE/ACM International Conference on Software Engineering (ICSE2003), [PDF] SAS sdml jmaletic
Marcus, A., Maletic, J.I. Identification of High-Level Concept Clones in Source Code", in Proceedings of the 16th IEEE International Conference on Automated Software Engineering (ASE 2001), San Diego, CA, USA, November 26-29, pp. 107-114 [PDF]
Maletic, J.I., Marcus, A., Supporting Program Comprehension Using Semantic and Structural Information, in Proceedings of the 23rd International Conference on Software Engineering (ICSE 2001), Toronto, Ontario, Canada, May 12-19, 2001, pp. 103-112 [PDF]
Maletic, J. I. and Valluri, N., Automatic Software Clustering via Latent Semantic Analysis, in Proceedings of 14th IEEE International Conference on Automated Software Engineering (ASE 1999), Cocoa Beach Florida, October, pp. 251-254 [PDF]
K. Sartipi and K. Kontogiannis. Pattern-based Software Architecture Recovery. Proceedings of the Seond ASERC Workshop on Software Architecture, 7 Pages, February 18-19, 2003, Banff Center, Alberta, Canada. [PDF] ksartipi

Links:

Maintained by