Research On Detection Of Functionally Equivalent Code Fragments Via K Nearest Neighbor Algorithm

It is an indispensable important aspect to insure the high quality and high reliabilityof software in system development and maintenance work. It is an important task todetect code clone to insure the high quality and high reliability of software. Thepresence of code clone increases the amount of code in software system, and makes thesoftware system architecture more bloated and there existing some difficulties tomaintain. Because of functionally equivalent duplicated code involves complicatedprocedure semantic analysis, this kind of code clone lacks of effective detection method.For the shortcomings of the current methods, this paper proposes a functionallyequivalent duplicated code detection method based on K-nearest neighbor clusteringalgorithm.Lexical analysis and syntax analysis are done to the source program togenerating abstract syntax tree AST and control dependence graph CDG. Then thespecific data flow analysis is done to get the def-ref information set of variables in theprogram statements. Next, K-nearest clustering algorithm is used to obtain functionallyequivalent and easily extracted code fragments. On the basis of identifying the inputvariables and output variables of code fragments, procedure extraction are done to codefragments, then the non-compilable code fragments are transformed into compilable andexecutable functions. Next automatic random assignment for the input variables in thefunctions is completed. At last, dynamic testing are performed for functions, which areclassified into different clusters according to the output results of functions. The sets offunctionally equivalent code fragments can be obtained.This paper tests the detection modle of functionally equivalent duplicated codeusing student programs and open source code Simens, and compares with the method ofsliding window to obtain candidate code fragment in references. It is be proved that themethod in this paper can obtain functionally cohesive code fragments in a lower timecomplexity, which are further used for the detection of functional equivalenceduplicated code.