Steven Woods' Ph.D. Thesis

A constraint-based approach to program plan recognition in software reverse engineering

We investigate the application of artificial intelligence plan recognition and constraint satisfaction algorithms to perform reverse-engineering and program understanding based on known programming knowledge such as abstract data types and program schemas. We intend to demonstrate the feasibility of such an approach by performing empirical systematic tests on real legacy code.

In progress work ...

• Software Reverse Engineering using Program Plan Recognition as Constraint Satisfaction, Ph.D. Thesis draft updated May 23, 1996.

Submitted work ...

• Applying Plan Recognition Techniques to Program Understanding: Failures and New Directions. With Qiang Yang and Alex Quilici. An earlier version appears in Technical Report CS 95-52. An abstract is also available.
• Program Understanding as Constraint Satisfaction: Representation and Reasoning Techniques. Advance copy of journal paper, 1995. With Qiang Yang. Appears in Technical Report CS 95-51. An abstract is also available.

Published work ...

• Towards A Constraint Satisfaction Framework for Evaluating Program-Understanding Algorithms. To appear in the Journal of Automated Software Engineering, Kluwer Publishing, 1996. With Alex Quilici.
• Approaching the Program Understanding Problem: Analysis and a Heuristic Solution Proceedings of the 18th International Conference on Software Engineering (ICSE-95), Technical University of Berlin, Berlin, Germany. To appear, March 25-30, 1996. With Qiang Yang.
• A constraint-satisfaction framework for evaluating program understanding algorithms Proceedings of the 4th IEEE Workshop on Program Comprehension (WPC-96), Technical University of Berlin, Berlin, Germany. To appear, March 29-31, 1996. With Alex Quilici. Appears in Technical Report CS 95-52. An abstract is also available.
• Constraint-based Program Plan Recognition in Legacy Code, Proceedings of the 1995 IJCAI Workshop on AI and Software Engineering (AISE-95) , Montreal, August 1995. With Qiang Yang.
• Program understanding as constraint satisfaction, Proceedings of the IEEE Seventh International Workshop on Computer-Aided Software Engineering (CASE-95), IEEE Computer Society Press, July 1995. With Qiang Yang. Also appears appears in the Proceedings of the 2nd Working Conference on Reverse Engineering (WCRE-95), July 1995.

Thesis Specific Presentations, Shared Documents

• LPAIG Day Presentation Dec, 1995.
• Ph.D. Timeline and Overview Current.
• Recognizing Program Plans in Legacy Code Thesis Proposal Talk Slides (new empirical results), March 1995.
• Thesis points to resolve Outstanding Issues, Comments, Discussion, Spring 1995 .
• A constraint-based approach to program plan recognition Ph.D. thesis proposal, February 1995.
• Knowledge based model recognition in program understanding using constraint satisfaction Preliminary report for Ph.D. thesis proposal, December 1994.
• Discussion Papers on Cognitive Modelling, 1994.
• My entire bibliography file might be a source of interest.

Shared Thesis Data

• Example Code Templates, Base Situations, and Statement Distributions used in Experiments. February, 1996.
• Example Legacy Code used in Experiments. February, 1996.
• Zipped CSP solver used in Experiments. May, 1996.

The members of my Doctoral Committee are ...

• Supervisor Dr. Qiang Yang, AI, planning, knowledge-based software engineering, constraint satisfaction.
• Dr. Rick Kazman, HCI, software engineering, computational linguistics.
• Dr. Robin Cohen, AI, user interfaces, natural language, computational linguistics, social issues in computing.
• Dr. Grant Weddell, software engineering, databases.
• External Examiner Dr. Hausi Muller, software engineering, software analysis, reverse engineering.

Related (sort of) interests ...

• Software Reverse Engineering and automating tools for expert-assistance.
• LPAIG bi-weekly Agency discussion group page.
• Constraint Satisfaction problems. In particular, I am interested in investigating novel strategies for hybridization of search and constraint propagation, and in application of these to some real problems. I have built a tool, MOTORS, that can combine CSP search and constraint propagation algorithms to form various problem solvers.
• Non-linear planning, abstraction, and search. Specifically I built a non-linear planner known as AbTweak , based primarily on the earlier work of Yang and Tenenberg, and implemented Left Wedge, a novel search strategy for abstraction.

Information and papers relevant to my thesis ...

• Dr. Alex Quilici, University of Hawaii at Manoa, Department of Engineering (Electrical); program understanding, intelligent user interfaces, natural language.
• Linda Wills, Ph.D. MIT, Automated Program Recognition by Graph Parsing.
• Constraints FAQ
• Artificial Intelligence FAQ set
• David Chin home page, Quilici/Program Understanding.
• Prem Devanbu's Home Page, gen++ annotation.