Semantic Code Analysis

I. Introduction

Logic programming is applied to code analysis in a large IBM programming development center. The MVS design group, specifically the Subsystem Des i gn/Exper i ment<Jl L<Jboratory, wanted to prototype the IMS Cross Memory Loc<Jl Stor<Jge Option. The effort was successful. The IMS Development group in S<Jnta Teres<J, C<Jlifornia subsequently developed the product. This was announced as part of IMS 1. 2.

Multiple Virtual memory System is IBM's largest an most advanced operating sytem. It is intended primarily for the largest IBM processors. See for example [ 1 I. Information Management System is IBM's most popular data base m<Jnagement system.~~~ 1u1 example [ 2 I.

We were presented with many very large .and complex assembler language routines. The programmers had to understand these and modify them to work with a new 'cross memory'

Time was of the essence. There was only a small . window in time during which the IMS product plan could be changed to include the desired function. A successful prototype was critical to demonstrating the feasibility and degree of effort .required to change the H1S product.

This need for a quick and effective tool w a s o n e o f t h e p r i m a r y f a c t.o r s i n f 1 u e n c i n g the development of SCAN. The goal was to get IMS prototype running, not to develop a new tool. Time could be spent on the tool only to the extent it facilitated the prototype. Consequently, the human factors of the tool would have to be considerably changed in order to make it avai !able to users not having a good understanding of how the tool was constructed. We do not view this as a defect in the tool, since that was not its purpose.

We needed a tool which would be able to locate patterns and otherwise aid in analysis of the assembler code. It seemed that the PROLOG language might be fruitfully ilPPlied to the problem. We hild Gr<Jnt Roberts PROLOG interpreter on loan from the University of Waterloo for experimental purposes.[31 A pilot project was conceived to test the feasibility of applying logic programming to a 're<Jl-world' problem. It was named Semantic Code Analysis (SCAN), to reflect the fact that it could reason about the meaning of programs. Due to the nature of logic progr<Jms, its understanding could be increased by the simple process of adding rules to the SCAN datab<Jse.

The system extracts the information implicit in assembler output listings, and pl<Jces it in relational form in a PROLOG database. It then performs interval analysis on the extracted information. All of this is placed in the database for querying. Queries may be expressed in the so-called Horn-clause form of first-order logical expressions.[41

The system proved its potential as a substantial foundation for software development assistance.

I I. Seme-nt i c Code Analysis

II.A. Objectives of the System

Semantic Code Analysis (SCAN) is an interactive aid to program understanding and <lnalysis. It understands such things ClS control and data flow, and the effects of operations on machine states. It is intended to be used by people modifying S370 assembler l<lnguClge programs[5], although it is extensible to handle any language or combination of languages.

It is based on logic programming. The information contained in the assembler output listing of a program is converted into Cl PROLOG dCltabase. A flow graph at all levels of detai 1 is deduced from the stCltements. That information becomes part of the database. PROLOG can then be used to interactively query this data. PROLOG is is more than a query languClge. It can reason and ClPPlY rules which capture 'system wisdom'.

Semantically significant conditions such as using register 0 as a base register can be simp 1 y and eas i 1 y expressed in the PROLOG l<lnguage. (In the S/370 architecture, register 0 is treated as always containing 0 when used as a base in computing addresses.) A given query which finds a set of instructions (e. g. a path) can be easily modified to select that subset which satisfies conditions. such semantically significant

Rules for this sort of qualification of a given query (read 'program') in PROLOG require only the addition of a few clauses. This ability to further qualify existing predicates is one of the features that makes programming in PROLOG so easy.

Figure 1. The analYsis procedure

II.B. The Analysis Procedure

1. The Assembler (H) output listing is put in a format which can be reCld by Waterloo PROLOG. A small PL/I routine simply quotes all the strings and forms them into a well-formed PROLOG term.
2. The listings are then 'digested' and the information placed in the database. A PROLOG program is provided which does this.
3. The base relations are then anCllyzed to make some implicit rel<ltions explicit. This is for reClsons of efficiency. The control flow graph was found to be a frequently used implicit relation. Therefore it is made explicit. The flow analysis algorithms we use are taken from [6].

Other useful formulations are available. For example see [7].

4.

• When higher levels of abstraction are desired, the flow analysis is repeated on each succeeding level, until an irriducible form is obtained. Again we follow Hecht.

The base relations include assertions defining the statements and links among them. For some instructions(e.g. ADD), the LINK relationships are clear: one LINK to the next sequential instruction is generated. Also, for conditional branches to internal labels it is clear that two LINKS are needed -- one to the label and one to the next sequential instruction.

There are other situations where it is not so clear where the LINKs should go. For some of these cases we were able to add PROLOG rules which embody some conventions. For example:

• unconditional branch on register 15 is the standard convention for leaving these routines
• Supervisor call 13 CSVC 13 Abnorma 1 end) is considered an EXIT.
• Branch And Link Register CBALR 14,15) is a subrouting call, and no 1 ink is generated.
• SVC 10 (Get main storage) is also considered a subroutine call, and no link is generated.

There are other things which cannot be deduced from the code. For example, user defined supervisor calls may be exits or subroutine calls. This makes a difference in whether a LINK tuple is generated for that statement. In cases like this, the user can· add a rule defining the semantics. This avoids annoying the user with useless repetition of the same question.

We could not simply assert the rule automatically after the first answer, bec<:~use the effect of the Supervisor call could be different depending on its input.

Th e PROLOG code which does this may be of interest. The pertinent part of GETER (which is the main routine) is:

GETER ( *ORS l <­

SUBSTMTC*A,*OP,*OPR,lfB,*C,*l&

STRINGC*B,*O.*R.*S.*T.NILl&

((EQ(*Q,'O'l& /*test for OX ops*/

CCEQClfR,'S'l&BALRC*A,*OPR,*Blll

CEQC*R, '6' l&BCTRC*A,lfOPR,*Bll I

( EQ ( *R' '7') &BCR (*A' *OP' *OPR '*B)) I

CEQC*R, 'A' l&SVC(*A,*OP,*OPR,*Bl))) I

CEQC*Q, '4' l&

When the opcode is seen to be an SVC COAxxl, the rules for handling SVCs are invoked. There are special rules for known SVCs, such as OAOD (Abnormal Termination) --which is asserted to be an EXIT:

Assembler H Listing

000061C 07FF

1466+LABEL BR 15 GO TO ROUTIN 01-RESUM

000126C 4740 608A 3438

BM PXCT010 ENQ ECB 73142280

PROLOG Forma~t

STMTCDFSREP001S.l4661+1 'LABEL' 1 BR.l5 1

'GO TO ROUTINE' I '01-RESUM' I

00061CI

'07FF', ' 'l.

STMTCDFSREPOO,S,38481 ',BM,PXCT0101

'YES-GO ENQ ECB'~'73142280' 1

00126C,

'4740'~'608A',' 'l.

Ba~se Rela~tions

EXITC1466l.

LINKC3848,3822). LINKC384813849).

Flow �re~ph

NODEC115l. GLINKC1151293). NODENDC11511466l.

NODEC245). NODEC246l.

GLINKC2451222l. �LINKC245~246l. NODENDC245,3849). NODESTARTC24613848).

SVCC*A·*·*·'OAOD')<- ADDAXCEXITC*All&

SVCC*AI*I*I'OA07')<- ADDAXCEXITC*All&

/CSVCC*·*·*·*ll&FAIL. /CSVCC*·*·*·*ll&FAIL .

SVCC*A~*~*· 'OA7A' )<­

/(SVCC*~*·*·*ll&FAIL.

SVCC*A~*·*·*Bl<- WRITERRCSVC,31*Al & GENAC*Al.

The last rule applies if no .ne of the others do. It tells the user that an unknown SVC has been encountered 1 and asks what to do Cthis is done by the subroutine GENAl:

It is here that additional rules could be added specifying the semantics for other SVCs that the user knows about. A simple ADDSVCCnumber, exit or subroutine or link) function would be provided the general user would not have to know this internal representat i on. This would most likely be added as a subfunction of GENA.

Other means of building or adding to the database may of course be used. A proposed design could be entered by hand; or our short (50 line) PROLOG analysis routine extended for PL/I or COBOL.

II.C . The Interval Analysis Algorithm

PROLOG allows an easy, straightforward expression of Hecht's interval analysis algorithm. In his book, Hecht first expresses the definition of an interval in a semi-declarative form. He then spends considerable time converting this into a PASCAL program. Much effort is taken to demonstrate that the procedural PASCAL ve rsion is equivalent to the declarative de f inition. The dual declarative/operational semantics of PROLOG enabled us to bypass this effort, and use his definition as the program.

II.D. Possible Queries

Queries are limited only by the imagination and skill of the user. An idea of the capabilities may be formed by noting the following list of some possible queries.

• What possible paths exist between two statements?
• What is the locking status at a specific point on a path?
• What registers are available for use at an instruction?
• Where is a variable referenced? Set?
• Does a certain code sequence occur in the module?
• What are the comments on statements branched to by a conditional branch based on a condition code which may be set by some instruction using one of a set of DC' d constants?

Queries include, but are not limited to, the full range of register usage, including EQUated synonyms. In addition, all other information implicit in the program listing is available as the subject of a suitable query.

Queries may be built up. Simpler ones, such as finding a path, may be used in more complex ones, such as finding locking status. Once they are constructed (and saved l, they become ava i !able for future use, and for use by others.

Examples of PROLOG format for queries.

Here are two of the queries used, and their PROLOG realization.

1 . Where is any symbol eguated to 0 used as a base reqi stel'?

We illustrate for those statements whose operands are of the form D(R), for any displacement D, and check to see if R is equated to 0. There are two other possible operand forms, each of which requires an alternate query.

Step operand in field Figure 1 of every makes the statement available as the 7th of 13 fields in the STMT relation. Since it is frequently used, we define an OPCstatement#, operand) relation which simplifies extracting the operand. Traditional database literature terms this a 'view':

We have defined the relation PARSE(string,treel which parses the operand string and returns the parse tree. For example, operands of the form 'D(Bl' are parsed into the tree inFigure3.

Figure 3. The Parse tree for DCBl So to pick out those operands of this form with 0 as base, we require the operand be parsed into this tree with the symbo 1 B equated to 0.

This tree is an instance of

so the entire query to find 0 used as a base is

OP(*stmt,*op)

& PARSEC*op,OPRCEXPRC*,SYMC*rll,NILll

& EQU(*r,Ol.

When successful, the variable *stmt is bound to a statement whose opcode parses into the looked-for tree, where the register symbol is equated to 0.

A symbol may be a constant, equated to a constant, equated to a symbol equated to a constant, ....·

/*NUMERIC CONSTANT*/ EQU(*sl,*sll <- INTEGERC*sll. /*IMMEDIATE EQUATE*/ EQU(*sl,*sZl <­ STMTC*,A·*·*·*sl,EQU,*sZ,*·*l. /*CHAINED EQUATE*/

<- EQU(*sl,*s3l EQU(*s3,*s2l. &

2. Where ; s a register used as a br01ncn target base, but never set?

Define BRANCHTARGET(r,sJ, which holds when register r is the base of a branch target at statement s ·

Define SET(r,s) which holds when register r is set at statement s ·

Define SETONPATH(r,p), which holds when register r is set on path P ·

We now have enough to define our primary query.

We paths point. assume we are interested in which are from a given entry NOTSET(ENTRY,R,SJ holds when

1. the statement number associated with label ENTRY is STRT,
2. and there is a path from STRT to S,
3. and register R is a branch target b<Jse at S,
4. d . and register R is not set on any path from STRT to S.

NOTSET(*ENTRY,*R,*Sl <­

STMT(*,S,*STRT,*·*ENTRY,*·*·*· PATH(*STRT,*S,*PATH1J & BRANCHTARGET(*R,*S) & NOT( PATH(*STRT,*S,*PATH2) & SETONPATH(*R,*PATH2J ).

III. SIZES

The SCAN system was quite small compared to 'normal' programs, moderately large compared to common PROLOG programs. Appr;oximate sizes are:

• 300 PL/I statements for pre-processor quoting routine
• 200 PROLOG clauses to parse assembler operands
• 200 PROLOG clauses to extract base relations and perform flow analysis

Of more interest is the size of the data used to represent a program. This ranged typically from 5,000 10,000 unit PROLOG clauses per module for the base relations.

When running analysis or query, we used a 6Mbyte stack, which in Waterloo PROLOG is used to hold programs and data, and to perform computations. Even with this stack size we too frequently encountered 'STACK OVERFLOW' conditions due to the size of the data. Since computing a path required much stack space and was frequently done at several levels in a computation, we could have used more space for the computation.

The 'small' stack size was most restrictive on the number of programs we c o u 1 d d e a 1 w i t h a t o n c e . To h a n d 1 e a 1 1 o f I ~IS we estimate would take about 500Mbytes. A stack of this size will be available on MVS/XA.

Waterloo PROLOG is theoretically inefficient in its look-up mechanism for clauses when there are large numbers of clauses with the same predicate symbol, which was the case here. Surprisingly, we found the performance quite satisfactory. A 'STACK OVERFLOW' condition could be reached in just a few (5-15) seconds when an infinit e computation was being per sued.

IV. Cost/Effectiveness of Knowl~dqe Base

Costs are expressed in terms of equivalent person-hour costs. Assum i ng a machine-to-person cost ratio of 400, g i ves us a cost-savings ratio of .l._Q__;_l over base analysis of a given module. Our experienc e tells us that this is an extreme ly conservative estimate for a more fully developed system. The ratio of machine-to-person costs will continue to drop, which will further improve the cost savings.

An improvement in the human interface to the query system will also improve the cost/benefit ratio. Natural language query would seem to be the obvious next step. See for example [8), [9], or [10)

V. Otner related work

of There is currently much work being done the 'programmer's apprentice' variety. Systems like PSL/PSA[11) allow specificatons to be written in an entity-attribute language. These supply the user with a predefined set of relations and reports, which are hard to extend but suffice for a large class of problems.

SCAN allows these relations and reports to be defined and easily extended, but does not force users into preconcieved structures. A prepackaged set of definitions (ie. PSL/PSA provided on a Logic Programming base) which could be easily extended would be an interesting fac i 1 i ty.

The aim of these assistants is to go from specifications to code. SCAN as implemented and used worked from the other direction-­ from written code to higher constructs. Howard Holley's GRASP system[l2) is remarkably similar to SCAN (even to the name of one of the components). GRASP offers a full screen and graphics user interface, but a much more restricted query capab i 1 i ty.

Shapiro [ 13] has investigated a system which debugs or generates PROLOG programs from processing examples. It would be inte resting to see ho~ well his algorithms app 1 y to our PROLOG representation of an assemb ler program.

VI. Conclusion

Logic programming has been successfully applied to a 'real world' problem. The advantages of a strong pattern matc hing and r eason ing system have been amp l y demonstrated. The pilot ·project points the way to the tool which may very well prov i de the industry with a badly needed quantum improvement in productivity and quality .

Refel"ences

• [ 1 I Auslander, M., et al., "The Evolution of the MVS Operating System", IBM Joul"nal of Reseal"ch ~nd Development 1 Vol. 51 No. 51 September 1981, 471-482.
• [21 f1cGee, W., 'The Infromation Management System IMS/VS', IBM Systems Joul"nal, Vol. 16, 1977, 84-168.
• [ 3 I Roberts, G., An Implementation of PROLOG, MS Thesis, Department of Computer Science, University of Water lao, 1977.
• ! 4 I Kowalski, R., Loqi c fol" Pl"oblem Solving, North-Holland, New York, 1979.
• [51 OS/VS Assemblel" Language Order No. GC33 4010 available through IBM branch offices.
• [61 Hecht, M., Flow Analysis of Compute .. PI"091"ams, Science North-Holland Computer Library, Programming Language Series, New York, 1977.
• ! 7 I Holley, H., data and flo~ Transactions Engineering, 1981,60-78. B. Rosen, "Qualified problems", IEEE on Software Vol. SE - 7, No. 1,
• ! 8 I Pereira, 1 . , p. Sabatier and E. Oliveira, "Orbi : a n Expert-System for Environment al Resource Evaluati on through Natural Langu a ge, " Proc . of the Fil"st !ntel"national Logic PI"091" amming Confel"ence ADDP-GIA, Faculte des Sciences de Marseil le, France , 19 82 , 200-209. Luminy, September
• [91Pereira, F ., Logic for Natul"al Languag e Analysis, Ph.D. Thesis, Un ive rs it y o f Edi nburgh , Scotland, 1982.
• [lOIWarren, D., "Efficient Proces sing of Interactive Relational Database Queries Expressed in logic," PI"OC. Seventh Intel"nationa l Confel"ence on Vei"Y Lal"qe Data Bases, Ca nnes, France, September 198lm 272 -281,
• ! 11 I Teichroe~, D., and Hershey, E. "PSL/PSA : a computer-aided technique for structur ed documentation and analysis of information proc es sing syst ems, " IEEE Tl"an5actions on Softwal"e Engineel"ing Vol. SE-3, No. 1, 1977 , 101-108.
• [ 12 I Holley, H., " GRASP, an analytical tool for systems programming", InM Pl"ogl"amming Pl"oductivity Tools Symposium, Santa Teres a , November 19 8 2, 646 - 6 72.
• [ 13] Shapiro, E., Algol"i thmi c Pl"ogl"am Debugging, Ph.D. Dissert ati on, Yale University, 1982.