SOFTM: a software maintenance expert system in Prolog - Software Maintenance, 1988., Proceedings of the Conference on General rights Copyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or other copyright owners and it is a condition of accessing publications that users recognise and abide by the legal requirements associated with these rights.  Users may download and print one copy of any publication from the public portal for the purpose of private study or research.  You may not further distribute the material or use it for any profit-making activity or commercial gain  You may freely distribute the URL identifying the publication in the public portal If you believe that this document breaches copyright please contact us providing details, and we will remove access to the work immediately and investigate your claim. Downloaded from orbit.dtu.dk on: Apr 06, 2021 SOFTM: a software maintenance expert system in Prolog Pau, L.; Negret, J. M. Published in: Proceedings of the Conference on Software Maintenance Link to article, DOI: 10.1109/ICSM.1988.10181 Publication date: 1988 Document Version Publisher's PDF, also known as Version of record Link back to DTU Orbit Citation (APA): Pau, L., & Negret, J. M. (1988). SOFTM: a software maintenance expert system in Prolog. In Proceedings of the Conference on Software Maintenance (pp. 306-311). IEEE. https://doi.org/10.1109/ICSM.1988.10181 https://doi.org/10.1109/ICSM.1988.10181 https://orbit.dtu.dk/en/publications/2ee065d9-fc41-41b3-b0e1-589662df4bb5 https://doi.org/10.1109/ICSM.1988.10181 L. Pau Technical University of Denmark Bldg. 348/EMI, DK 2800 Lyngby, Denmark ABSTRACT: This paper describes a software maintenance (SM) knowledge based system ealled SOFTM, serving t h e three following purposes: (1) assisting a software programmer or analyst in his application code m a i n t e n F c e tasks, (2) gen- erating and updating automatically sonware correction docu- mentation, (3) helping t h e end user register, and possibly in- terpret, observed errors on the successive application code ver- sions. The knowledge based system SOFTM is written in PROLOG 11, a n d i s largely applicable to application codes written in different programming languages, provided code descriptors can be retrieved. SOFTM does not address any of the syntactic, input-output, or procedural errors normally de- tected by the syntactic analyzer, compiler, or by the operating system environment. SOFTM i s relying on a unique ATN network based code description, on diagnostic inference proce- dure based on context based pattern classification, on main- tenance log report generators, and on interfacing capabilities of PROLOG I1 to a variety of other languages. 1. INTRODUCTION 1) The current concern about software maintenance i s justified by t h e cost and quality of code repair and up- dates, while at least maintaining software reliability and performances. The estimated productivity gains ex- pected from software maintenance are, according to Bar- ry Boehm, TRW [451 Corrective maintenance: 18% of current effort Adaptative maintenance: 14% of current effort J.M. Negret Battelle Memorial Institute - software maintenance personnel selection - performance goals, and quality control during mainte- ance - software maintenance work breakdown - distribution of responsibilities amongst code users, d e w - loppers, quality assurance, and maintenance - audits and user reviews - problem reporting systems - maintenance logs - use of specification formalisms, typically of t h e SAD1' model - use of program design languages - use of structured techniques to maintain unstructured code - designing in code maintainability Amongst the tools in use, or at the research stage, can he mentioned: - specification and program design languages - software configuration systems - conversion of source code in i t s structural control-flow graphs (e.g.S3, ADA, Z specification languages) - source code controllers, formatters and comparators - declarative constructs - paragraph parsers - cross referencing and linking facilities (mapping) - display of data flows - symbolic debuggers - test data generation - sequence analysis tools (for synchronization and recoverability) - interpreters of abnormal endings - coverage analysis - diagnostic metarules Perfective maintenance: 7 % of current effort Update: due to mismatch between user requirements and software specification: 14% of current effort Many of the above are still at a n early stage, t h u s result- ing in t h e still overwhelming use of debugging he1.r- istics as t h e basic software maintenance approach and tool. The major issues in software maintenance and i t s role in t h e software production process, a r e discussed in [3,8,9,13,14,21,22,24,25,26,27,28,35,43,45,461. The classical approaches followed are: 2) Some research focusses on knowledge based programm- ing, where code is being written with user driven access thru a n intelligent editor to: CH261S-3/88/oooO/030$01.@I Q 1988 IEEE 306 Authorized licensed use limited to: Danmarks Tekniske Informationscenter. Downloaded on October 16, 2009 at 09:11 from IEEE Xplore. Restrictions apply. gnowledgeeources TOOlS Data flow models and Data flow design descriptors Transform aids Design rules Transaction analysis Data dictionary Procedural templates Abstract procedures Design codes Common data structures Structured programming rules Common algorithms Examples of such related CASE projects a r e (non ex- haustively): T e d i u m m e d i o u s E n t e r p r i s e s , P r o - grammers ApprenticeJMIT, USE-IT/Higher order Soft- ware, RlOOOAXational, REFINWReasoning systems, Knowledge-based software assistant (KBSA)/Kestrel In- stitute, Intelligent program editor/Advanced Informa- tion and decision systems, POISE Interactive pro- gramming environment/Univ. of Massachusetts, IN- FORM/Univ. Stuttgart [ll, KBPAlEsprit 121 and also in AI related CASE research 13,6,13,15.16,21,24, 40,43,44, 45,473. Research h a s been reported on e x p e r t h o w l e d g e based debugging: Message trace analyzer - Source code debug- germniv. Waterloo [4l,SPEAWDigital Eqipment [5l,FA- LOSYNniv. Minnesota [7l,SOFTM/ Technical Univ. Denmark & Battelle C301, besides [6,8,13,15,19,36,37,41, 47,481. However, little work h a s dealt so far with knowledge ba- sed software maintenance, incorporating some of the re- levant approaches and tools mentioned above in 1): see [10,11,17,20,21,30,421. It is the purpose of this paper to de- scribe t h e structure of a software maintenance expert system SOFI'M, written in Prolog I1 1493 , and operating on t h e source code of a diversity of programming langu- ages. 1) On a specific piece of application code C(L), written in a programming language L for which t h e r e is a n interpretor, compiler, linker, and editor, the actual knowledge based software maintenance system SOFTM carries out essentially error diagnosis and provides for the propagation of corrective changes (see Figure 2): 1. detection of errors: except : a) syntactic errors detected by the compiler b) cross-referencing errors c ) calculation errors due to a wrong algorithm d) search, query or IO errors due to a wrong algorithm 2. location of errors, except 1) a,b,c,d 3. error diagnosis 4. maintenance guidance for C(L) 5. generation of explanation facilities for 1.-4. 6. automatic generation of code maintenance logs, to be incorporated into the C(L) code documentation. This obeys the diagnostic strategies described in 1291 and using context based pattern classification. This is essentially a backward chaining process where root error ceusdcorrection goals a r e found from their consequences and partially known attributes C501. The knowledge base of SOFTM is divided into three parts: KB-1: Facts in predicate form, about error types, error localizations, diagnostic classes, the environment, and observables. Observable8 are passive if measured without modifying code execution, and active if external perturbations are necessary. KB-2 Code independent kernel rules, applying to the general software maintenance task. KB-S: ,Symbolic descriptors of C(L), derived by rewriting in predicate form C(L) features provided by the compiler, the specification language, or the data flow model, in an augmented transition network (ATN) form. All three part a r e assigned to different sub-worlds in Prolog, for separation and decomposition; they are edited each by a knowledge base editor specific to each of the three parts. The knowledge base KB-3 is interfaced to other tools as indicated. Regarding inferences and queries, the access is as fol- lows: - the code developper, can query and update KB-1 alone, and update C(L) thru the editor of that L language; he can also execute C(L) - the code user, can query KB-1 and run C(L) - t h e code maintenance programmer, can query and up- date KB-1, query KB-3, and update KB- 2. 3. APPLICATION DEPENDENT CODE KNOWLEDGE RE- PRESENTATION The code representation i s treated as fact predicates in a speci- fic knowledge base world. It consists of: a) code structure: it describes the information flows between code modules and arguments, stressing t h e call order during execution. The representation i s a n augmented transition network (ATN) with attributes, written in pre- dicate logic. The node labels are provided by the linker, and the attributes by a standard run of the code (altemati- vely by a Petri-net based simulator). module structure: each module of the application code is represented by a frame, attached to t h e corresponding ATN node. The frame fields are: pointers to U0 argu- ments, pointers to internal arguments, ordered textual description of the functional purpose of each successive block in t h e module (as specified e.g. in structured or functional programming). These frame fields a r e provi- ded by t h e linker or compiler, and by the module docu- mentation located in "Comments". b) 307 Authorized licensed use limited to: Danmarks Tekniske Informationscenter. Downloaded on October 16, 2009 at 09:11 from IEEE Xplore. Restrictions apply. 4. KNOWLEDGE REPRESENTATION OF APPLICATION CODE CIL) (gB3) The relations between modules of C(L) a r e described by a n ATN with the following fact descriptions of each rela- tion in Prolog syntax: mm(ml,m2,L,p)-->; . where: m l : is the module name being called from m2 m2 : is the module name calling m l , with retum to m2 .t : list of call sequence numbers in call chronology, terminated by nil p : name of code or root module The relations between arguments (compiled by the inter- preter o r debugger) and a module, a r e described by t h e facts: am (a,m,line,p)-->; where: a : is a n (YO) argument of module m m : module name l i n e : p : name of code, or root module relative address of argument a, or pointer Each code module i s represented by the Prolog frame structure: md (m, 41,L2, b,p) --> where: m : module name L 1 : list of YO arguments to m represented by relative address pointers in list form, terminated by nil 22 : list of internal arguments in m, which are not in L 1 b : pointers to relative address of first line in each functional block of m, in list form, ended with nil p : name of code or root module md may be represented also with explicit arguments names, while preserving the same frame structure From t h e above knowledge descriptions of C(L) i t i s ob- vious to estimate the number of steps and processes invol- ved in the code, and to sort them by size. C(L) can also preserve the timelstate dependent informa- tion necessary to determine what activities are possible in a dynamic environment; in this case, t h e arguments about time and state a r e tagged separately for data flow or I/O control. 5. APPLICATION CODE INDEPENDENT KNOWLEDGE BASE This knowledge baselworld, which is application code inde- pendent, contains in predicate form, according to the diag- nostic strategy of [291: Y) : observables about the errors, yielding the values of q d j - tativdcontinuous measurements on the application code, once instantiated; L): physical or virtual error locations; E): generic error type or descriptor, such as data type erroi; undefined arguments, etc. C): diagnostic causes (from the domains: design, execution, environment, human errors); M): generic or specific SM actions affecting:application code programming, application code design, software envi *- onment, human factors. 6. KNOWLEDGE REPRESENTATION FOR THE DOMAIIq I”DENTFAC’I-BASES (EB- 1) 1. 2. 3. 4. 6. 6. The facts in K33-1 are described by t h e following Prolcg data structures: Observables: passive( Y-P) o r active Cy-A) < observable - (type) - p/a, (number of observable), (timi!- stamp), nil, (sentence defining observable). (measuru- ment location). (value of observable) . nil > -->; Location IL) < location, (number), (time-stamp), nil, (sentence d 2- fining locations) . (error number) . nil > -+; En” < error, (number), (time-stamp), (likelihood), (error de- scription sentence) . nil > -->; Diagnosis (C) < caase, (number), (time-stamp), (likelihood), (cause name sentence) . (error number) . (cause name sent- ence) . (error number) ... nil > -+; DlaintenanceN < correction, (number), (time-stamp), (likelihood of c f- fect), (sentence describing correction) . nil > -+; Documentation 0) < documentation, (number), (time-stamp), nil, (tiile sentence) . (location number) . nil >-->; 7.l”cEpRocEDuREs They consist of (see Figure 2): a) control structure: i t is the Prolog I1 depth first backtrack- ing with top-to-bottom and left-to-right clause deletian, supplemented by verification and domain dependent pve- dicates; these predicates a r e supplemented by contc xt sensitive control predicates such as diffx,y) and freeze(x,p), which implement t r u t h maintenance a i d conditional propagation [491 b) explicit inference procedures: they include both a for- ward and backward chaining, with a n observatiodgc a1 restriction phase followed by pattem matching on the scts of rules in (e) below, and then by action clauses. The tic- tion clauses consist in addinddeleting facts with likc li- hoods, and by automatically logging them in t h e SM do- cumentation file; 308 Authorized licensed use limited to: Danmarks Tekniske Informationscenter. Downloaded on October 16, 2009 at 09:11 from IEEE Xplore. Restrictions apply. c) domain dependent inference rules: this rule base con- tains in predicate form, with a list syntax: 1. detection rules: Y -> E 2. localization rules: E -> L 3. diagnostic rules: ExLxY -> C 4. maintenance rules: ExLxYxC -> M with SM error 5. incorrectness and insufficiency metarules operating 6. sequencing constraint control metarules, to check call documentation update on the ATN sequences and propagate effects of corrections accordingly code blocks 7. rule cluster documentation generators for functional d ) uncertainty representation, by attaching likelihoods to each error (E), cause (C) or correction (M) fact, the likeli- hoods are propagated and combined along each inference path into a n importance qualifier for each hypothesis or goal The combination of a) b) and c) allows for the automatic propa- gation of maintenance changes, by asserting into &e fact base KB-3 these changes. If new types of errors or locations or cor- rections a r e entered into KB-1 through the proper editors, they a r e automatically accounted for thanks to the Prolog declar- ative form. Thus t h e inference procedure in SOFTM uses fully propagation mechanisms and analysis. 8. ENVIRONMENTAND IMPLEMENTATION The SOFTM knowledge based software maintenance envir- onment in Prolog I1 [491 h a s been supplemented, besides the in- terfaces to t h e operating system, compiler, and higher level utilities (specification language output, simulator input), by: - SM documentation explanation facilities - fact, rule, code structure editors (specialized) - knowledge base management commands - query editor for forward chaining (diagnose a n error) - backward chaining editor (reason to possible candidate- correctionderrors) - likelihood calculations - time-stamp management on all SM actions - debugger - interface between Prolog I1 and constants, variables, lists in different languages (PASCAL, COBOL, FOR- TRAN, ADA) - optional interface to a text database management system containing the full software documentation (e.g. BASIS) The current implementation i s on VAXNMS for application code written in either COBOL, FORTRAN or ADA, and Prolog itself. Specialized application code languages are also consi- dered, e.g. image processing language, test language, and ex- pert systems [391. 9. KNOWLEDGE EXIEMSIONS The basic information h a s been collected, although not yet im- plemented, to enhance the application independent knowledge basis (KB-2) with respect to: - metarules for identifying modules or module to module relations with similar structures - measuring debuggindmaintenance stress, t o estimate likelihoods for detection or corrective actions - generate and place scope markers to delineate code gov- emed by conditional expressiona - protect from any corrective measure the YO arguments - introduce simple software metric attribqtes to compare old from revised code - generate from t h e call sequences a maintenance plan which obeys module interaction - inclusion of simple alternate program verification tech- niques likely to appear in software testing certification standards. REFERwcEs ref. as [91 G. Fischer, H.D. Boecker, The n a t u r e of design processes a n d how computer systems can support them, in P. Degano, E. Sandewall (Ed), "Intgegrated interactive computing systems", North Holland, 1983, 73-86 (INFORM system, Univers- ity of Stuttgart) K. Poulter, Representing programming knowledge in the KBPA, in G.J.P. Katz (Ed), "ESPRIT'85: Proc. of t h e meeting", North Holland, 1986 (KBPA Franz- Lisplc prototype) K.A. Frenkel, Toward automating t h e software deve- lopment cycle, Comm. ACM, Vol28, no 6, jun 1985,578- 89 N.K. Gupta, R.E. Seviora, An expert system approach to real time system debugging, Proc. 1 s t IEEE Conf. on AI applications, 1984, p. 336 (Message Trace analyzer in Prolog, Univ. Waterloo) SPEAR, Expert systems J., Vol 1, no 2, October 1984, p 98 (SPEAR computer error log analyzer at Digital equip- ment) M. Schindler, AI begins to pay off with expert systems for engineering, Electronic Design Magazine, Aug. 9, 1984,106146 R.L. Sedlmeyer, W.B. Thomson, P.E. Johnson, Diag- nostic reasoning in software fault localization, Proc. IJCAI-83, Karlsruhe 1983, Vol 1,29-31 (FALOSY master file update software fault finding, Univ. Minnesota) H.J. Hindin, Intelligent tools automate high-level lan- guage programming, Computer Design Magazine, May l5,1986,46-56 D. Gustafson, A. Melton, A model for software main- tenance, Proc. IEEWACM Conf. on software mainten- ance (CSM.87). Austin, TX, Sept. 1987 B. Terry, R.D. Cameron, Software maintenance using meta-programming, same ref. as [9] F. Cross, An expert system approach to a program' s in- formatiodmaintenance system, same ref. as [91 D. Richard Kuhn. A source code for maintenance. same 309 Authorized licensed use limited to: Danmarks Tekniske Informationscenter. Downloaded on October 16, 2009 at 09:11 from IEEE Xplore. Restrictions apply. 1131 [14l [15l Cl61 R.L. Baber. The Spine of software: designing provably correct software, Wiley, 1988 M.W. Evans, J. Marciniak,Software quality assurance and management, Wiley, 1987 C. Rich, R.C. Waters (Ed), Readings in AI and soft- ware engineering, Morgan Kaufman Publ., 1986 B. Liskov, J.Guttag, Abstraction and specification in program development, MIT Press, Cambridge (MA), 1986 L.B. Alperin, B.I. Kedzierski, AI based software main- tenance, Proc. 3rd IEEE Conf. on AI applications, Or- lando (FL), Feb. 1987 Proc. conf. on reliability and robutsness of engineering software,Computational Mechanics Institute, Como (Ita- ly), Sept. 1987 M.A. Ould, C. Unwin, Testing in software mainten- ance development, Cambridge Univ. Press, 1986 S.S. Yau, S.S. Liu, A knowledge based software main- tenance environment, Proc. IEEE COMSAC'86, IEEE Computer Society, Chicago, 6-10 Oct. 1986 D.A. Higgins, Data structured software maintenance, Dorset House Publ.iWiley, 1987 J. Mastow, Toward better models of the design process, AI Magazine, Spring 1985 GL.B. Kotik. A.. Rockmore, D.R. Smith, Use of RE- FINE for knowledge based software development, Proc. 4 t h Int. Workshop on software specification and de- sign, IEEE Catalog TH 0181-8, April 1987 M. Lubars, M.T. Harandi, Intelligent support for soft- ware specification and design, IEEE Expert, Vol 1, no 4, winter 1986,3341 I. Sommerville, Software engineering, Addison Wes- ley, 1985 NTIS, Annotated bibliography on software mainten- ance, Superintendent of documents, Washington DC, Software maintenance, IEEE Computer society Press, L.F. Pau, Failure diagnosis and performance monitor- ing, Marcel Deker, N.Y., 1981 L.F. Pau, J.M. Negret, SOFTM: a software mainten- ance expert system, Battelle Memorial Institute, Gene- va, 1985 T.S. Chow, Testing software design method by finite state machine, IEEE Transactions on software engin- eering, May 1979 R.L. Glass, Software reliability guidebook, Prentice Hall, 1979 J.E. Hopcroft, J.D. Ullman, Introduction to automata theory, languages and computation, Addison Wesley, 1979 P.P. Howley, A comprehensive software testing metho- dology, Second software engineering standards appli- cation Workshop, SanFrancisco, May 1983 Standard for software test documentation, ANSYIEEE std 829,1983 J.M. Morin, J. Perez, S. Xanthakis, MBthodes de mod- Blisation pour la g6nBration de tests de recette, Institute genie logiciel, T/0052/DI", 1985 G.J. Myers, The a r t of software testing, John Wiley and sons, New York, 1979 P. Zave, A comprehensive approach to requirement pro- blem, Proceedings of COMPSAC, 1979 [lfl 1181 [19] 1201 El] [22] [233 [25l Ea 127J S/N 003-003-02756-1,1986 1281 1291 [301 Cat. 0-8186-0002-0. EH-02014,1983 E311 1321 1331 1341 1353 1361 O7l 1381 1391 r4a 1411 r431 1441 14n 1481 1491 m1 L.F. Pau, Prototyping, validation and maintenance of knowledge based systems software, h o c . IEEE 3ri Conf. on expert systems in government, Washingtoll DC, Oct. 1987 D. Partridge, AI: applications in t h e future of software engineering, Elis HorwoodlWiley, 1986 Proc. ACM Symp. software engineering for high levtd debugging, SIGPLAN Notices Vol 18, no 8, Aug. 1983, ACM Order 593830 C.A. Dyer, Expert systems in software maintainabilit:r, Proc. 1984 Annual reliability and maintainability M. Schindler, Through automation, software shapes it- self to t h e task at hand, Electronic Design, July 25,198!i, H. Abelson, G. Sussman, The structure and interpretat- tion of computer programs: a LISP perspective, MIF press, 1985 A.J. Rockmore, Knowledge based soRware tums spe:- ifications into efficient programs, Electronic Design, S. Bendifallah, W. Scacchi, Understanding softwa -e maintenance work, IEEE Trans. Software engineer- ing, Vol SE-13, no 1, Jan 1987 H. Wertz, Automatic correction and improvement >f programs, Ellis Horwood/Wiley, 1986 J. Loecky, K Sieber, The foundations of prowam ver- ification, Wiley-Teubner, 1987 F. Giannesini, H. Kanoui , R. Pasero, M. van Ca- neghem, PROLOG, Addison Wesley, 1987. L.F. Pau, A survey of expert systems for failure diagn- osis and maintenance, Expert Systems J., April 1986 s ~ P . , IEEE publ. 0149-144 xEB4,295-2!39 87- July 25,1985,105 - 112 310 Authorized licensed use limited to: Danmarks Tekniske Informationscenter. Downloaded on October 16, 2009 at 09:11 from IEEE Xplore. Restrictions apply. Figurel: SofcwareengineeringCASEcycle r- representa- tion of lcodeATN application 1 module ----------------- I SOFTM t I I t Diagnose gh Propose maintenance actlons corrective actions Figure 2 s o m inference functions 31 1 Authorized licensed use limited to: Danmarks Tekniske Informationscenter. Downloaded on October 16, 2009 at 09:11 from IEEE Xplore. Restrictions apply.