Using Graph Matching: Program Recognition of the Selection Sort Algorithm.
Ronald B. Finkbine · MAICS · 2013
The field of program understanding attempts to determine the function of a code segment without programmer intervention and for this to occur, it is necessary to have a model (plan) against which to attempt to match the code segment of interest. This paper traces in detail the pattern recognition of the selection sort algorithm. Introduction The purpose of this research is to develop a generalpurpose algorithm recognition system, capable of recognizing any well-defined and well-written algorithm. This project uses plans (Wills 1992) to recognize common forms (code segments) within existing software in an attempt to gain knowledge about a legacy system (Sartipi 2003) from its source code (Biggerstaff 1990) by matching against a large defined set of common algorithms, rather than attempting to deduce what a code segment performs from its specific dataflow (Rugaber et. al. 1990). This research uses an intermediate representation of an abstract syntax tree (AST), standard in compiler toolsets. This AST representation is output as a flattened tree into a fact list, which is the operation underpinning of expert systems. Targeted Problems This research concentrates on design recovery from legacy software, written in older languages and with fewer techniques applicable to modern software development. This is because that recently written software is often written in a more modern language, but this leaves a large bulk of older, operational software, orphaned to endless software maintenance until it is rewritten. Legacy software, in general, exhibits a number of the following problems: 1) parameter identification, 2) identifying code segments that are replaceable by calls to commercial libraries (such as IMSL), 3) removing duplicate code to user library, 4) separation of intertwined components, and 5) combining disparate codes into single equations. Each of these problems increases the difficulty in a software maintenance programming attempting to understand a software component. Graph matching is considered one of the most complex problems in computing (Bienenstock 1987). The first problem, parameter identification, is the most simple. It involves searching the source code for variables that are assigned values within assignment statements (no reads) one time. Any usage, thereafter, is only on the righthand side of assignment statements and is a reference to the variable, not a modification to the variable. Therefore, these types of variables, or constants, can be identified by the parameter statement which indicates their true usage. The second problem, plan recognition, is comprised of identifying code segments that are replaceable by calls to commercial libraries (such as IMSL). This will involve detecting codes similar to those used within commercial libraries. The third problem, duplicate removal, consists of detecting and removing duplicate code to the user’s library. This allows the user to designate a section of code as common and to look through their remaining programs searching for codes that are copies of the target. The fourth problem, algorithm separation, involves detection/separation of overlapping algorithms within the same section of code. In Figure 1 it can be seen that there are two initializations of arrays occurring within the same do-loop. This is good for optimizing computer resources, but not for optimizing the programmers’ time for understanding and maintaining a program. The fifth problem, algorithm aggregation, involves combining disparate codes into single equations. As displayed in Figure 2, an equation 1) can be coded in multiple ways. Though the computations are equivalent,