9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # The Program Understanding Problem Analysis and A Heuristic Approach

The Program Understanding Problem: Analysis and A Heuristic Approach

Steven Woods Department of Computer Science University of Waterloo Waterloo, Ontario N2L 3G1 Canada sgwoods@logos.uwaterloo.ca

Abstract

Program understanding is the process of making sense of a complex source code. This process has been considered as computationally dif?cult and conceptually complex. So far, no formal complexity results have been presented, and conceptual models differ from one researcher to the next. In this paper we formally prove that program understanding is NP-hard. Furthermore, we show that even a much simpler subproblem remains NP-hard. However, we do not despair by this result, but rather, offer an attractive problem-solving model for the program understanding problem. Our model is built on a framework for solving Constraint Satisfaction Problems, or CSPs, which are known to have interesting heuristic solutions. Speci?cally, we can represent and heuristically address previous and new heuristic approaches to the program understanding problem with both existing and specially designed constraint propagation and search algorithms.

Qiang Yang School of Computing Science Simon Fraser University Burnaby, British Columbia V5A 1S6 Canada qyang@cs.sfu.ca

isting knowledge about programs and programming. Once constructed, an expert can, and typically does, use these mappings to infer other higher level and lower level goals for a source program. The mappings raise the level of abstraction of the legacy code representation from purely raw source level to include the more abstract level of the existing representational framework for expressing domain knowledge. This abstracted representation may subsequently be exploited as part of the process of at least the following tasks: 1. translating the program into the source code of another programming language, 2. recognizing errors in legacy code and assisting in debugging the code, or 3. replacing understood code portions with generic application code or calls to other code libraries. There have been a variety of methods proposed which partially solve the program understanding problem, primarily as parts of a supposed interactive assistant or maintenance toolset[11, 13, 14, 5, 9, 10]. Each of these approaches attempts to integrate perceptions or recognitions of particular abstracted program plan templates into an overall understanding of the source in terms of a particularly con?gured library of pre-existing knowledge about how programs (in general or in a particular domain) are known to be structured. Past work has not provided a formal analysis of the complexity of the understanding problem, or presented an understanding framework shown to be general enough framework to include most of the previous approaches. In this paper, we present two results. First, we show that the program understanding problem is NP-hard. This result provides a formal justi?cation for researchers to look for heuristic methods for solving the problem.

1 Introduction

An expert attempts to understand the source code of a legacy program as part of the legacy maintenance task. Understanding can be thought of as at least the process of constructing mappings between existing knowledge and some perceived artifact. In the domain of maintaining legacy source, an expert would attempt to construct these mappings based upon a previous knowledge set which includes general knowledge about how programs are constructed and speci?c knowledge about typical program plans. We describe abstracted program plans as templates, both generic and domain speci?c. Given a particular store and representation of expert programming knowledge, and some perceived structure of a legacy artifact, one might describe the process of constructing a mapping between these as understanding. An understood or partially understood program is one which has had its structures and components at least partially contextualized in the scope of ex-

Second, we present a CSP (constraint-based) model for program understanding. This model allows much of the previous work to be cast under a unifying framework. We illustrate this model with associated algorithms and examples.

2 Previous Approaches

In Arti?cial Intelligence research, the problem of program understanding has been approached indirectly from the perspective of plan recognition [4, 1]. These programs have been applied mostly to toy domains (such as the cooking domain), involving small knowledge bases and a small amount of search. Woods et al[16] describe in more detail how current approaches to program understanding fundamentally differ with earlier and some current plan recognition methodologies. Recently, researchers have adopted a more direct approach to program understanding. An explicit library of programming plan templates and concepts is constructed, and various top-down and bottom-up search strategies are utilized to implement the mapping process. Kozaczynski and Ning[5] describe a method of automatically recognizing abstract concepts in source code. Given a library of concepts and a set of rules for how to recognize the higher-level concepts from lower-level language concepts, the search in their Concept Recognizer is controlled in what is essentially a top-down, library-driven manner. Rich and Waters[11] headed the Programmer’s Apprentice project which focused on the development of a demonstration system (Knowledge-Based Editor in Emacs or KBEmacs) with the ability to assist a programmer in analyzing, creating, changing, specifying and verifying software systems. In addition, Rich and Waters[11, pp. 171188] describe a clich? recognizer called Recognize, e based in KBEmacs. Understanding tools rely on the existence of structured legacy source. As part of the effort at providing this structure for maintenance engineering, Muller et al[8] are involved in the construction of Rigi, a system for analyzing software systems which includes visual representations of data and control-?ow structures in a code for the identi?cation of subsystems and hierarchies of structure in the code. Along this line, Devanbu and Eaves[2] have constructed Gen++, a tool which generates tools for analysis of C++ code. Speci?cally, Gen++ can generate tools which in turn generate annotated abstract syntax trees (ASTs) of C++ code showing control and data-?ows. In subsequent sections we review two major themes representative of the endeavor to create understanding tools. In Figure 1 a subset of expert knowledge about a particular application domain is represented in a fragment of a hierarchical library of program templates. One possible mapping is shown between a plan template from the library and a

speci?c legacy source fragment, in this case a single source statement. The existence of such a mapping essentially explains the presence of the low-level source statement at a higher level of abstraction, as an instance of the plan template copy-character speci?ed in the library. There has been a rich tradition of heuristic approaches to program understanding. One recent approach by Quilici[9, 10], a derivative of earlier work by Kozaczynski and Ning[5], is based on a construction of an explicit library of programming plan templates, complete with an indexing ability, which can quickly associate a particular recognized source code fragment with program plan templates in the knowledge base. In this “code-driven” fashion, a combination of top-down and bottom-up search strategies is utilized to implement the matching process. With his DECODE system, Quilici demonstrated how simple C programs could be translated to C++ programs. This approach marks one of the ?rst cognitively motivated1 attempts to program understanding using a hierarchical library of program plans. Program plans, such as those embedded in Abstract Data Types (ADTs), are organized hierarchically in a library as shown in Figure 1. Legacy source code preprocessed as an annotated AST is mapped to the plan library through the use of indices. Indices are pre-de?ned “keys” or pointers in the plan library mapped to key instances in the legacy source. Index tests indicate when it is appropriate to specialize or to attempt to infer the existence of other plans according to a set of pre-de?ned conditions. As an example of specialization, consider Figure 1 in which the program plan initialize-string is specialized to builtin-char*-copy when a direct string assignment is observed in the source code. An example of an inference test is also shown in Figure 1, where the existence of loop-initialize-string is inferred when an instance of loopthrough-character-array is “near” a related instance of copy-character in the source code. In a different approach, Wills[11, 13, 14] models stereotypical program or data structures (clich? s) as a type of e ?ow-graph grammar and parses 2 legacy source represented as a ?ow graph. Each successful partial parse represents a one explanation of part of the source program.

3 Complexity Analysis

Our survey of the approaches to program understanding has resulted in the following model. One is given a source program to understand in terms of a library of program plan templates. From these, one is to compose a solution in

1 Quilici’s work has included observation of the behaviour of student programmers in manipulating legacy examples. 2 Wills notes that although the parsing problem is NP-complete in general, experience suggests that attribute constraint checking signi?cantly prunes the search space in practice.

Legacy Source Code

main() { char* A, B, C; ... A = "s" + "t" + "r" + "i" + "n" + "g" + "1"; ... B = "string 2"; ... sz = 7; for (int j = sz; j > 0; j??) { .... C[sz ? j] = B[sz ? j]; ... } ... C[sz] = 3; ... for (int i=0; B[i]; i++) ... print(B[i]) .... ... for (int j=0; C[j];j++) { .... printf("%s",C[i]); ... } ... for (int k=0;A[k]; k++) { ... outchar(A[k]); ... } ...}

Program Plan Library (excerpt)

String ADT plan

specialize when: contains = "$string"

AND

initialize?string

OR

index when: "near instance" of copy?character

builtin?char* copy

loop?initialize string

AND

copy?character

loop?through character array

plan instance

Figure 1: Conceptualizing source with a plan library. the form of a mapping from portions of the source code to part of the plan library. In this section, we prove that this problem is intractable. between their data-?ow relationships. As an example, in Figure 2, the following correspondence gives rise to an understanding of the example program:

Simple Program Understanding Problem

Our strategy will be to simplify the problem. Consider the following Simple Program Understanding (SPU) problem, depicted in Figure 2. We are given the following: The source code consists of a collection B of program blocks Bi ; i = 1; 2; :::; m. These blocks can be viewed in terms of a corresponding graph P = (B; D ) where D is the set of edges of the graph Dk ; k = 1; 2; :::; n, such that an edge Di;j exists between nodes Bi and Bj if and only if a data-?ow exists between the program blocks. We are also given a library of program plan templates represented as a graph L = (T; C ) where T , the set of templates To ; o = 1; 2; :::; t in L are related to one another through data-?ow relationships. These relations are speci?ed by a set C of edges, such that an edge Ck;l exists between templates Tk and Tl if and only if a data-?ow possibly exists between them. Given the above structure, the SPU problem is to determine if a correspondence exists from program blocks to a subset of templates. The correspondence is of the form of a mapping between templates and program blocks, and

B1 B2 B3 B4

() () () ()

T3 T6 T4 T5

We contend that the SPU problem is representative of many program understanding tasks. In Kozaczynski and Ning’s approach in the Concept Recognizer system, program plans which consist of components and constraints abstracted away from a particular implementation language or method are utilized. Quilici extends these plans with the provision of indices (memory) that control the selection of candidate plans more selectively than in Concept Recognizer. The library of interrelated program plan templates in each approach are essentially the same as we outline in SPU, with the exception that a hierarchical structure may be imposed on the library. In Wills’ approach, program components are modeled as graph grammars and are used to parse an intermediate ?ow graph representation of a source program. A component’s make-up is constrained by it’s grammar, and these components are composed in a library (of constraints). The SPU program understanding model abstracts these differing representations of components and constraints into a

"Mapping" from Program to Library Portion

B1 D1,2 D2,3 B3 D4,2 T4 C 4,5 B2 D 3,4 B4

X

T3 C 6,4

C 3,6

T6 C 5,6

T5 P = {B, D} s s s L = {T ,C }

Program to Understand

C 3,1 T1 C 1,2 T2 C2,4 T4

T3 C 6,4

C 3,6

T6

C 5,6 T5

C 4,5

C 5,7 T7

Library of Program Template Plans

L = {T,C}

Figure 2: Simple Program Understanding. unifying constraint-based library format. Understanding approaches uniformly assume that source programs have been pre-processed into a intermediate representation (annotated abstract syntax trees, annotated ?ow graphs) which makes explicit use of data-?ow and control-?ow information. In SPU, this information is represented as a simple program graph of related program blocks. The SPU problem could be stated more formally as follows. Given a library of program plans L = (T; C ) and a source program P = (B; D), does there exist at least one subgraph of the library LS = (T s ; C s) where the templates in the subgraph T s T , and the constraints among the templates C s C , are matched to the source program by a mapping function X , de?ned as follows: to H , i.e., a subset V V1 and a subset E E1 such that jV j = jV2 j, jE j = jE2j, and there exists a one-to-one function f : V2 ! V satisfying fu; vg 2 E2 if and only if ff (u); f (v)g 2 E ? The transformation to an SPU problem can be done as follows. Every vertex of V1 in G is a program template, and every edge of E1 in G signi?es a data-?ow between templates. Each vertex of V2 in H is a program block and each edge of E2 in H is a data-?ow between blocks. A mapping between a program P and a subset of a library of related templates T exists if and only if H is a an isomorphic subgraph of G. Furthermore, this transformation can clearly be done in polynomial time.

X maps every program block B

and

i

to a member of T ;

s i;k

Program Template Matching is NP-hard

Earlier we discussed that many recognition approaches attempt to recognize typical program plans or clich? s, and e then integrate these instances into a coherent or consistent global understanding. We have proven the simple program understanding problem is NP-hard. Now, what about the seemingly much simpler problem of ?nding instances of a given pattern in a program source code? In this section, we establish that even this simpler problem is NP-hard. The Simple Program Template Matching Problem (SMAP) problem, is depicted in Figure 3. We are given the following: There exists a collection B of program blocks Bi ; i = 1; 2; : : :; m. These blocks can be viewed in terms of

X maps every program data-?ow edge D to a corresponding member C of C , where u = X (B ) and v = X (B ).

u;v s i k

We can prove the claim that SPU is NP-hard by a reduction from the Subgraph Isomorphism problem which is known to be NP-hard[3, p. 202]. The Subgraph Isomorphism problem may be stated as follows:

( 2

Given a graph G = (V1 ; E1) and a graph H = V ; E2), Does G contain a subgraph isomorphic

a corresponding graph P = (B; D) where D is the set of edges of the graph Dk ; k = 1; 2; : : :; n, such that an edge Di;j exists between node Bi and Bj if and only if a data-?ow exists between the program blocks. We are also given a program template plan T = N; C ) where each member Ni of N participates in data-?ow relationships with some other nodes in N . These relationships are speci?ed by C , the set of edges between nodes N , such that Ck;l 2 C exists between nodes Nk and Nl if and only if a data-?ow exists between the two.

(

solution strategies are search-based, propagation-based, or hybrid.

The Modeling Process

The SPU program-understanding constraint-satisfaction problem (refered to as PU-CSP when formed as a constraint satisfaction problem), is formed in the following way. Suppose that an initial decomposition4 of the source code is given. Each block of source code corresponds to a variable in the PU-CSP. The variable domains correspond to all possible explanations (mappings to the knowledge or library) of an individual block of the source code. The constraints between the variables can be speci?ed via both the structural relationships in the source program, and subsequently, knowledge relationships in the program plan library. A solution is a mapping between the source code blocks and the library such that the constraints are satis?ed. We illustrate the modeling process in more detail. A Program Understanding CSP (PU-CSP) is formulated via four distinct steps shown in Figure 4. First, the legacy source is pre-processed, creating an intermediate representation which precisely captures many interrelationships among the elements of the abstract syntax tree implicit from a parsing of the source. This representation includes data-?ow and control-?ow between functional blocks. Second, the source code is partitioned into spatially localized, cohesive code blocks5 which exhibit several inter-block functional relationships. Third, a skeleton CSP is formulated consisting of one variable for each identi?ed source block, and constraints between these variables are derived from the intermediate representation level artifacts. The combination of types input and output ?ows into each particular block are adopted as re?exive constraints on the corresponding variable, effectively limiting the range of program plans that might explain that block. Finally, each CSP variable is matched (or indexed by type information) against the templates in the program plan library. Potentially matching plan templates are then composed as the domain ranges of each variable. In a PU-CSP, the constraints among variables are of two types: Structural constraints are determined from the legacy

4 This decomposition is such as would be created from Devanbu’s annotated abstract syntax tree parsing of C++ programs. 5 These code blocks may be of varying size and complexity. The actual determination of appropriate blocking characteristics will be investigated empirically in later work. It is important to note that since the library of knowledge is arranged hierarchically it will often be the case that smaller blocks will tend to correspond to lower-level program plans and viceversa. Consequently, the problem itself may be thought of as the need to generate a sequence of multi-layered mappings. It has been suggested by Alex Quilici in a personal communication that these mappings would best be generated bottom-up from small code fragments and plans to larger, however, this is not the only possible approach.

Given the above structure, the SMAP problem is to determine if a mapping exists from the template nodes N to a subset of program blocks in B . The mapping is a function between relationships among template nodes and data?ows among program blocks. As an example, in Figure 3, the following correspondence gives rise to a matching instance of the program template:

N1 N2 N3 N4

() () () ()

B2 B4 B1 B3

The formal de?nition for the SMAP problem is similar to that for the SPU problem. We can once again prove that SMAP is NP-hard by a reduction from the NP-hard problem Subgraph Isomorphism, described earlier in Section 3 on page 4. The transformation to a SMAP problem can be done as follows. Every vertex of V1 in G is a program block, and every edge of E1 in G signi?es a data-?ow between blocks. Each vertex of V2 in H is a program template and each edge of E2 in H is a data-?ow between templates. A mapping between a template T and a subset of program blocks in a program P exists if and only if H is a an isomorphic subgraph of G.

4 Modeling Program Understanding

In this work we have outlined our approach[18, 17, 19] for representing and potentially solving the program understanding problem. This approach exploits a constraintbased methodology for recognizing program plan templates in legacy source. We have shown both the larger program understanding problem (SPU) and the template recognition problem (SMAP) to be NP-hard. Consequently, we must resort to heuristic methods for the solution of each problem. Our algorithms for each are based on the exploitation and adaptation of existing algorithms for solving constraint satisfaction3 problems. In general,

3 Kumar[6] provides a good survey of CSPs.

s s s P = {B ,D } B1 D6,1 B1 D7,1 B7 B3 D1,2 D2,3 D4,2 N3 C 4,1 N2 N4 C 4,2 T = (N,C) C 3,1 N1 B5 D 2,5 B2 D 3,4 B4 D4,5 B3 D1,2 B2 D2,3 D 3,4 B4 D4,2

B6

D7,6

M

"Mapping" from Program Template to Program Portion

Source Program

P = {B, D}

C 2,1

Selected Program Template Plan

Figure 3: Program Template Matching. code. They include such things as scope or called/calling relations, precedence relations, or shared information relations between component blocks. Knowledge constraints are independent of the legacy code. These constraints reside in the AND/OR hierarchical program plan library, restricting program plan inter-relationships. The AND connections indicate a parent-child component relationship, while the OR connections indicate specialization/generalization relations. Each of ANDs and ORs can serve to indicate important details of the parent-child relationship, such as the role6 of a child as part of the higher level parent, or what details specialize a child from a parent. specializing an abstract plan in one of several ways. Assigning one program plan as an explanation of a particular PU-CSP variable thus constrains consistent assignments of other component variables. This detail effectively describes the allowable range of known program plan structure. A solution to the PU-CSP is an assignment to each variable by one program plan component in the plan library, such that no structural constraint from the source code, or knowledge constraint from the plan library is violated.

6 For instance, a compositional role might describe what data-?ows a child provides in its function as part of a parent. In a more abstract instance, this role might be a service rather than a low-level data-?ow.

The representation of program understanding as PUCSP provides a convenient framework for the interpretation of earlier program understanding heuristics as particular constraint manipulations. For example, the Quilicistyle indexing outlined earlier in which an index instance in a source code signals the need to attempt to match a particular program plan from the library can be thought of as a speci?c constraint ordering during CSP search. Quilicistyle specialization preferences can be viewed as a heuristic for ordering the application of hierarchical knowledge constraints, essentially reducing the range of domain variables in a hierarchical CSP. Similarly, Quilici and others refer to inferences or implications which indicate the likely existence of plans based on the identi?cation of other plans. Such behaviour can be interpreted as a special kind of dynamic variable-ordering heuristic in which successful instantiation of a particular variable suggests the need to attempt to instantiate a related variable next.

5 Applying Local Constraint Propagation

In general, the more constrained a particular CSP, the easier it is to solve, provided it is known in advance which parts of the problem are the most highly constrained. It is our contention that program understanding can be thought of as a well-constrained problem in many useful instances. Software is ideally well-structured and compartmented by design, and a rich system of structural constraints between functional blocks can be extracted through known meth-

Program Source

Intermediate Representation Complete Program Analysis

Abstract Syntax Tree Control Flow Diagram Data Flow Diagram

Identify Program Blocks

Legacy Blocks Block V1 Block V2 Block V3

Skeleton CSP Graph

Variable V1 Constraint 1-3 Constraint 1-4 Constraint 2-3 Variable V2 Variable V4 Variable V1 { A2 i A2 ii } Variable V3

Block V4 Create PU-CSP Structure

Constraint 3-4

PU CSP Graph

Variable V3 { B2 B1 }

Program Template Hierarchy

Template A AND A1 A2 i A2 OR A2 ii Template B OR B1 B2 AND B2i B2 ii

C 1-3 C 1-4

Assign Initial Domains

{ A1 } Variable V2

C 3-4 C 2-3

{ C2 ii A2 ii}

Variable V4

Figure 4: A PU-CSP Formulation. ods. Program plan libraries such as commercial or shared object libraries contain a similar structure of knowledge constraints which can be annotated with design information much more readily than is the case with any particular piece of software since it has been intended for wider distribution and use. The large number of knowledge and structural constraints in a particular problem instance combine to effectively limit the number of consistent explanations or mappings for collections of related program blocks. In particular, the application of even one such structural constraint among blocks could reduce the domain size of a program block signi?cantly. This reduction can in turn be cascaded through adjoining block relations into successive reductions of other domains. This process is known in CSP related algorithms as local constraint propagation. An algorithm which enforces that all domains be consistent with their immediate neighbors is known as an arc consistency(AC) algorithm7. Many variations and extensions to the original AC algorithm, AC-3[7] have appeared in the literature, some of which are mentioned in [12]. These algorithms and many variations have been extensively applied and tested with a wide range of problems. Consider a pair of variables (X; Y ) and a relation

7 Other algorithms enforce different degrees of consistent, from only partial arc consistency over a subset of all arcs, to consistency along paths of arcs of varying lengths.

R(X; Y ). The arc R is said to be consistent, if for every domain value of X there is at least one consistent domain value of Y . If this condition is not satis?ed, a R EVISE routine can be applied to the pair to remove any value of X that does not have a corresponding consistent value of Y . If, for every pair of related variables in a problem, all are consistent, the problem has been made arc-consistent.

5.1 An Example PU-CSP using Local Constraint Propagation

In this section we demonstrate the applicability of local constraint propagation with an example. The repeated application of local constraints to reduce variables domains admits a solution with no search in this example. A piece of input legacy code is shown on the left of Figure 5. The code is parsed and program blocks extracted along with data-?ow information as shown on the right side of the ?gure. This ?gure has been signi?cantly simpli?ed for the purposes of our example. We wish to utilize the PU-CSP8 framework to understand the legacy source in terms of the hierarchical program template library fragment given in Figure 6. The legacy source blocks are mapped to variables, and initial domain ranges are assigned according to block input and output types. Variable isrt potentially maps to several library plans based solely on input and output typing. A further (re?exive) constraint application

8 PU-CSP corresponds to the SPU model.

main() struct2 isrt( struct1 *this, struct2 * inL ) if ( mbr(this,inL) ) then return inL else return app(inL,this) end isrt

this:struct1 inL:struct2

out:struct2

Contains "If" sub-plan

int mbr(struct1 *ck, struct2 *cks) if ( (cks == nil) or (cks.first ==nil)) then return 0 struct1 *try = cks.first while( not(try.id == ck.id) and not(try.next == nil) ) do try = try.next end while if (try.id == ck.id) then return 1 else return 0 end mbr

isrt

out:int out:struct2 CALL this=ck:struct1 inL=cks:struct2

mbr

CALL this=putE:struct1 inL=inL:struct2

struct2 app(struct2 * intL, struct1 *putE) if(intL.first == nil) then intL.first = putE putE.next = nil else struct1 *temp = intL.first intL.first = putE putE.next = temp return intL end app

app

Figure 5: One Simple “Blocking” of a Legacy Fragment.

Notation SMAP MAP-CSP SPU PU-CSP

Meaning Simple Program Template Matching Problem Template Matching Constraint Satisfaction Problem Simple Program Understanding Problem Program Understanding Constraint Satisfaction Problem Table 1: Notation Summary.

based on observation of key components (If)in the structure of isrt could signi?cantly reduce this set. In our example, only plans Set , Set , and List satisfy this constraint. Similarly, app maps to Set and List ; mbr to Set , List , Set , List , Set , List , Set , and List.

Insert Delete Delete Member Member Putin Putin Cut Cut Insert Insert Delete Delete Insert Delete Delete Putin Member Member Member Cut

and we are left with three combined alternate explanations that are consistent with the structure that we have outlined. These three are: (1) a set insertion plan, (2) a set deletion plan, or (3) a list deletion plan. This ambiguity can be easily resolved if we more closely expanded the structure of app, showing that the structure is an insertion rather than a deletion plan on the basis of the lack of an iteration which a deletion would require. A reduction in the range of app would result, leaving only the value Set in the range. A revision of isrt with respect to app would now result in a singleton value Set remaining, and subsequently mbr could be reduced to only Set .

The domain range of variable isrt may be revised with respect to mbr. In this case no values may be removed since Set is consistent with value Set , Set is consistent with value Set , and List is consistent with value List . Revising app with respect to isrt yields consistent mappings for values Set , Set , and List .

Putin

Insert

Cut

Member

After this revision, no further reductions can be made,

Our example problem is completed with the successful construction of a single mapping to the given program plan

Bool

Collection

Int (range 2)

EnumType (cardinality 2)

C-Insert C E C

C-Delete C E C

C-Create C

C-Structure

Set

Set isA Collection S isA C Es isA C

List isA Collection L isA C El isA C ListInsert :C-Insert L:C L:C

List

SetInsert :C-Insert S:C S:C Es:E

Delete :C-Delete S:C Es:E S:C

SetCreate :C-Create S:C

Delete :C-Delete L:C El:E L:C

ListCreate :C-Create L:C

El:E

If S:C I S:C Bool M P

Member

Cut C E C

L:C P El:E L:C

If

Member

Cut

Putin C S:C Es:E E C

Symbol Key Inheritance Aggregation input type output type Temporal constraint A:C Type A isA Type C

If Bool typeA typeA typeA

Putin C C E

Member C E Bool

Figure 6: Library Fragment. library. The legacy source consisting of three slices is an instance of an Set program plan with two primary subplans Set , and Set . Set occurs in the library fragment only as a part of the Set abstract data type plan group, and further as part of the Collection abstract data type plan. No other interpretations are possible given the knowledge constraints and structural constraints of this example. telecommunications provider to investigate the applicability of this approach to extremely large source code in the telephony domain. Achieving partial automatic recognition of even a small percentage of the code would greatly bene?t software maintainers.

Insert Member

Putin

Insert

6 Implementation and Research Status

In earlier work we introduced our CSP model of program understanding, including promising empirical results in the sub-problem9 of recognizing individual program plan templates in a range of large generated legacy examples[18, 17, 19]. As well, we have outlined the similarities and differences that we perceive between current and past program understanding methodologies and earlier plan recognition work[16]. For an overview of our terminology, pleaser refer to Table 1. We are currently engaging in cooperation with a main

9 The SMAP implementation is refered to as MAP-CSP in other work.

In addition to including earlier understanding efforts in our CSP paradigm[15], our current work includes efforts to elucidate and complete implementation of the encompassing program understanding representation and algorithm (PU-CSP or SPU), accommodating the hierarchical nature of program plan libraries. These hierarchical program plan libraries give rise to interesting algorithms that must accommodate hierarchically organized domain values in constraint satisfaction. We are working towards a future dissertation in which we shall demonstrate that useful cases exist in which the inherent structure in legacy code is suf?cient to allow existing constraint propagation methodologies to provide ef?cient solutions even in the case of large instances of “real” industrial legacy code.

7 Conclusion

In this paper we showed that the program understanding problem is NP-hard. This result provides a formal justi?cation for researchers to look for heuristic methods for solving the problem. We also presented a constraint-based model for program understanding, allowing much of the previous work to be cast under a unifying framework. We illustrated this model with an example and a brief overview of the associated algorithm.

[10] Alex Quilici and David Chin. DECODE: A cooperative environment for reverse-engineering legacy software. In Proceedings of the Second Working Conference on Reverse-Engineering, pages 156–165. IEEE Computer Society Press, July 1995. [11] C. Rich and R.C. Waters. The programmer’s apprentice. Addison-Wesley, Reading, Mass., 1990. [12] P. Van Hentenryck, Y. Deville, and C-M. Teng. A generic arc-consistency algorithm and its specializations. Arti?cial Intelligence, 57:291–321, 1992. [13] L. M. Wills. Automated program recognition: A feasibility demonstration. Arti?cial Intelligence, 45(2):113–172, February 1990. [14] L. M. Wills. Automated program recognition by Graph Parsing. PhD thesis, MIT, July 1992. [15] Steven Woods and Alex Quilici. Representing memory-based program understanding as constraint satisfaction. Technical report, University of Waterloo, Department of Computer Science, 1995. [16] Steven Woods, Alex Quilici, and Qiang Yang. Program understanding and plan recognition: reasoning under different assumptions. Technical report, University of Waterloo, Department of Computer Science, 1995. [17] Steven Woods and Qiang Yang. Constraint-based plan recognition in legacy code. Working Notes of the Third Workshop on AI and Software Engineering : Breaking the Toy Mold (AISE), August 1995. [18] Steven Woods and Qiang Yang. Program understanding as constraint satisfaction. In Proceedings of the IEEE Seventh International Workshop on ComputerAided Software Engineering (CASE), pages 318–327, July 1995. [19] Steven Woods and Qiang Yang. Program understanding as constraint satisfaction: Representation and reasoning techniques. Technical report, University of Waterloo, Department of Computer Science, 1995.

Acknowledgments

We thank Alex Quilici and Toby Donaldson for their insight and comments. This research has been carried out with the support of the Natural Sciences and Engineering Research Council of Canada and the Information Technology Research Centre.

References

[1] Sandra Carberry. Modeling the user’s plans and goals. Computational Linguistics, 14(3):23–37, 1988. [2] Prem Devanbu and Laura Eaves. Gen++ - an analyzer generator for c++ programs. Technical report, AT & T Bell Labs, New Jersey, 1994. [3] Michael R. Garey and David S. Johnson. Computers and Intractability : A guide to the theory of NPCompleteness. W. H. Freeman and Company, Bell Laboratories, Murray Hill, New Jersey, 1979. [4] Henry Kautz and James Allen. Generalized plan recognition. In Proceedings of the Fifth National Conference on Arti?cial Intelligence, pages 32–37, Philadelphia, Pennsylvania, 1986. [5] Wojtek Kozaczynski and Jim Q. Ning. Automated program understanding by concept recognition. Automated Software Engineering, 1:61–78, 1994. [6] Vipin Kumar. Algorithms for constraint-satisfaction problems. AI Magazine, pages 32–44, Spring 1992. [7] A.K. Mackworth. Consistency in networks of relations. Arti?cial Intelligence, 8:99–118, 1977. [8] H. Muller, K. Wong, and S.R. Tilley. Understanding software systems using reverse engineering technology. In Proceedings of the Colloquim on Object Orientation in Databases and Software Enginering, pages 88–98, December 1994. [9] Alex Quilici. A memory-based approach to recognizing programming plans. Communications of the ACM, 37(5):84–93, May 1994.

- A Heuristic Approach to Solving the Software Clustering Problem
- Heuristic approach to the airline schedule disturbances problem
- The probabilistic analysis of a heuristic for the assignment problem
- Exact and heuristic algorithms for the weapon-target assignment problem
- A heuristic solution for the empty container substitution problem
- A SWEEP BASED HEURISTIC FOR THE FLEET SIZE AND MIX VEHICLE ROUTING PROBLEM
- Heuristic approaches for the two- and three-dimensional knapsack packing problem
- A Heuristic Approach for the Open Capacitated Arc Routing Problem
- A tabu search heuristic for the vehicle routing problem with time windows and split deliver
- A Tabu Search Heuristic for the Vehicle Routing problem with time windows and split deliveries

更多相关文章：
**
***Heuristic* *approaches* for *the* multiperiod location-....pdf

*Heuristic* *approaches* for *the* multiperiod location-transportation *problem* with ...*Heuristic* *methods* for ... 137人阅读 15页 1下载券 *A* Note on *the* Complex...**
***The* *Program* *Understanding* *Problem*: *Analysis* *and* *a* *Heuristic* ....unkown

*The* *Program* *Understanding* *Problem*: *Analysis* *and* *a* *Heuristic* *Approach* Steven Woods Department of Computer Science University of Waterloo Waterloo, Ontario N2L ...**
***A* *Heuristic* *Approach* to Solving *the* *Software* Clustering ....pdf

*A* *Heuristic* *Approach* to Solving *the* *Software* Clustering *Problem*_专业资料。This...*Understanding* how *the* *software* is structured at various levels of ...**
***A* *heuristic* *approach* for Hamiltonian Path *Problem* with ....pdf

*A* *heuristic* *approach* for Hamiltonian Path *Problem* with molecules_专业资料。*A* new molecular solution of Hamiltonian Path *Problem* (HPP) is introduced. In this...**
***A* *heuristic* *approach* to *the* weakly interacting Bose gas.pdf

*A* *heuristic* *approach* to *the* weakly interacting Bose gas_专业资料。Some ...number of parameters small, which only makes *a* dimensional *analysis* possible....**
***A* *HEURISTIC* *APPROACH* TO ENGLISH-INTO-JAPANESE MACHINE ....pdf

*A* *HEURISTIC* *APPROACH* TO ENGLISH-INTO-JAPANESE ...|.controlling marks | for *analysis*, trans| ...H M P To accelerate *the* clear *understanding*, an...**
***A* *heuristicapproach*for*the*maxmindiversity*problem*basedonmax-....pdf

c o m / l o c*a* t e / c o r *A* *heuristic* *approach* for *the* maxmin diversity *problem* based on max-clique Federico Della Croce *a*, ? , ...**
***A* *Heuristic* *Approach* to Scoring Gene Clustering Algorithms_....pdf

*A* *Heuristic* *Approach* to Scoring Gene Clustering ...*problem* of choosing an appropriate clustering ...3.2.1. *Software* for Clustering *Analysis* *The* ...**
***A* *heuristic* *approach* to solving *a* class of bilinear matrix ....pdf

*A* *heuristic* *approach* to solving *a* class of bilinear matrix inequality ...This is because many *analysis* *and* synthesis *problems* for static output feed...**
***A* New *Heuristic* *Approach* for *the* One-Commodity Pickup-*and*-....pdf

*A* New *Heuristic* *Approach* for *the* One-Commodity Pickup-*and*-Delivery Traveling Salesman *Problem* Hip? lito Hern? ndez-P? rez, DEIOC, Universidad de La ...**
***A* *Heuristic* *Approach* for Predicting Fault Locations in ....pdf

*A* *software* tool implements *the* *heuristic* rules *and* *a* genetic algorithm based...1 *APPROACH* FOR PREDICTING FAULT LOCATIONS *A*. Fault *Analysis* Traditionally, ...**
***A* promising hybrid GA*heuristic* *approach* for open-shop ....pdf

*A* Promising Hybrid GA/*Heuristic* *Approach* for Open-Shop Scheduling *Problems* Hsiao-Lan Fang1 *and* Peter Ross1 shop scheduling *problem* (OSSP). We describe *a*...**
...***Heuristic* *Approach* for *the* Period Vehicle Routing *Problem* ....pdf

An Integrated*Heuristic* *Approach* for *the* Period Vehicle Routing *Problem* with Simultaneous D_专业资料。This paper introduces an integrated *approach* for solving ...**
***A* Hyper-*Heuristic* *Approach* to Parallel Code Generation.pdf

*The* *software* *problems* associated with parallel ...*analysis* levels, *the* same basic *approach* was ...*problems*, to evolve *the* choice of *heuristic* to ...**
***A* *HEURISTIC* *APPROACH* TO CELL-SUPPRESSION IN HIERARCHICAL ....pdf

*A* *HEURISTIC* *APPROACH* TO CELL-SUPPRESSION IN ... *problem*: *a* bottom-up *and* *a* topdown *approach*....For this case, *the* *program* had to check 11,...**
Exploration of ***a* *Heuristic* *Approach* to Threshold Learning in ....pdf

Exploration of*a* *Heuristic* *Approach* to Threshold ...As we were focussing on *the* threshold *problem*, ...360 4 Learning Effect *Analysis* ~i-~,,old up...**
On ***the* support of quantizers---Part II *Heuristic* *approaches* ....pdf

On*the* support of quantizers---Part II *Heuristic* *approaches* to optimality, submitted to_专业资料。This paper presents three *heuristic* *methods* for finding ...**
New ***Heuristic* Rounding *Approaches* to *the* Quadratic Assignment....pdf

New*Heuristic* Rounding *Approaches* to *the* Quadratic Assignment *Problem*_数学_自然科学_专业资料。Ar2 ,ou ,.Srlo6)p.0 Vl10me7No4(ei .5aN Junlfmmuiain...**
英语论文-***The* Application of *Heuristic* Teaching *Approach* in ....doc

毕业论文(设计)*The* Application of *Heuristic* Teaching *Approach* in English Classroom in Senior High Schools *The* Application of *Heuristic* Teaching *Approach* in ...**
***Heuristic* *Approaches* for *the* Coordinated Motion of *a* ....pdf

numerical*problems* due to *the* singularities, *and*...Both proposed *heuristic* *methods* (alternating (Figure... *The* *analysis* of excava... 5页 1下载券 方向... 更多相关标签：

c o m / l o c

An Integrated

Exploration of

On

New

毕业论文(设计)

numerical