Abstract:
A software tool allows a user to filter out the results produced by a software source code correlation program that is executed on sets of software source code files. The tool allows the user to discard elements of source code that are not relevant to the analysis without requiring the user to run the correlation program multiple times.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The present invention relates to software tools for comparing program source code files to determine the amount of similarity, or “correlation,” between the files and to pinpoint specific sections that are similar. In particular, the present invention relates to improving the analysis and interpretation of the results of a source code comparison by filtering out elements that are irrelevant to the comparison. 
         [0003]    2. Discussion of the Related Art 
         [0004]    Programs and algorithms that determine software source code correlation have been around for a number of years but have gotten more attention recently due to two main reasons. One reason is that the Internet and search engines like Google have made source code very easy to obtain. Another reason is the growing open source movement that allows programmers all over the world to write, distribute, and share code. It follows that programs that determine software source code correlation have become more sophisticated in recent years. It also follows that the amount of code to be compared has grown larger, especially as software projects have grown larger. 
         [0005]    Finding a correlation between different sets of source code does not necessarily imply that illicit behavior occurred. There can be correlation between programs for a number of reasons as enumerated below. 
         [0006]    Third-Party Source Code. It is possible that widely available open source code is used in both programs. Also, libraries of source code can be purchased from third-party vendors. 
         [0007]    Code Generation Tools. Automatic code generation tools generate software source code using similar or identical identifiers for variables, classes, methods, and properties. Also, the structure of the code generated by these tools tends to fit into a certain template with an identifiable pattern. 
         [0008]    Commonly Used Identifier Names. Certain identifier names are commonly taught in schools or commonly used by programmers in certain industries. For example, the identifier “result” is often used to hold the result of an operation. 
         [0009]    Common Algorithms. Certain algorithms are most easily implemented using a certain sequence of statements in a particular programming language. Commonly used algorithms, such as for elementary functions, will often be coded in very similar ways and may have a high degree of correlation even though there was no direct contact between the authors. 
         [0010]    Common Author. It is possible that one programmer will create two programs that have correlations simply because the programmer tends to use certain identifiers and tends to write code in a certain way. 
         [0011]    Plagiarism. Code was copied from one program to another. 
         [0012]    When a correlation program is run on sets of source code, often the user is looking to find one specific kind of correlation. For example, if the user is looking to find correlation due to plagiarism, he wants to eliminate the other five sources of correlation. The specific reasons for correlation can often not be determined until after a correlation program has been run and the results analyzed. At that time, it would be useful to be able to filter out correlation results due to forms of correlation that are not relevant. The present invention is a tool for doing just that. 
       SUMMARY OF THE INVENTION 
       [0013]    The present invention provides a software tool for allowing a user to filter out the results of a software source code correlation program that has been executed on sets of software source code files. The tool allows the user to discard aspects of correlation that are not relevant to the analysis without requiring the user to run the correlation program multiple times. 
         [0014]    Further features and advantages of various embodiments of the present invention are described in the detailed description below, which is given by way of example only. 
     
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0015]    The present invention will be understood more fully from the detailed description given below and from the accompanying drawings of the preferred embodiments of the invention, which, however, should not be taken to limit the invention to the specific embodiments but are for explanation and understanding only. 
           [0016]      FIG. 1  illustrates a process for dividing a source code file into statements, comments, and identifiers. 
           [0017]      FIG. 2  shows matching statements in a pair of source code files. 
           [0018]      FIG. 3  shows matching comments in a pair of source code files. 
           [0019]      FIG. 4  shows partially matching identifiers in a pair of source code files. 
           [0020]      FIG. 5  illustrates a sequence of algorithms for determining source code correlation. 
           [0021]      FIG. 6  shows a correlation database. 
           [0022]      FIG. 7  shows a filter file. 
           [0023]      FIG. 8  illustrates a process for filtering a correlation database. 
           [0024]      FIG. 9  shows a correlation database file that has been filtered for identifiers. 
           [0025]      FIG. 10  shows a correlation database file that has been filtered for statements. 
           [0026]      FIG. 11  shows a correlation database file that has been filtered for comments. 
           [0027]      FIG. 12  shows a correlation database file that has been filtered for instruction sequences. 
       
    
    
     DETAILED DESCRIPTION 
       [0028]    The present invention will be understood more fully from the detailed description given below and from the accompanying drawings of the preferred embodiments of the invention, which, however, should not be taken to limit the invention to the specific embodiments but are for explanation and understanding only. 
         [0029]    A well-known software source code correlation program called CodeMatch™ uses five algorithms to find plagiarism: Statement Matching, Comment Matching, Identifier Matching, Partial Identifier Matching, and Instruction Sequence Matching. Before any of the algorithm processing takes place, some preprocessing is done to create string arrays. Each file is represented by three arrays—an array of statements that consists of lines of functional source code and does not include comments, an array of comments that does not include functional source code, and an array of identifiers found in the source code. Identifiers include variable names, constant names, function names, and any other words that are not keywords of the programming language. 
         [0030]    Each line of each file is initially examined and two string arrays for each file are created: Statements 1 [ ], Comments 1 [ ] and Statements 2 [ ], Comments 2 [ ] are the statements and comments string arrays for file  1  and file  2  respectively. Examples of these arrays are shown for a sample code snippet in  FIG. 1 . A sample snippet of a source code file to be examined is shown in part (a)  101 . The separation of statements and comments for the code snippet is shown in part (b)  102 . 
         [0031]    Next the statements are examined from each file to obtain a list of all identifiers in the source code that are not programming language keywords, as shown in part (c)  103  of  FIG. 1 . Note that identifier j is not listed as an identifier because all 1-character identifier are ignored as too common to consider. 
         [0032]    The “statement matching” algorithm compares each functional statement of source code from each file against functional statements in the other file or files.  FIG. 2  illustrates this algorithm. Part (a)  201  shows the lines of two files along with line numbers. Part (b)  202  shows the statement line numbers in the two files that are considered matching. 
         [0033]    The “comment matching” algorithm similarly compares each line of comments from each file against comments in the other file or files.  FIG. 3  shows two files along with line numbers and the comments that are considered matching. Part (a)  301  shows the lines of two files along with line numbers. Part (b)  302  shows the comment line numbers in the two files that are considered matching. 
         [0034]    The “identifier matching” algorithm counts the number of matching identifiers—identifiers being words that are not programming language keywords. 
         [0035]    The “partial identifier matching” algorithm examines each identifier in the source code of one file of a file pair and finds all words that include the identifier as a substring in the other file of a file pair. This algorithm is illustrated in  FIG. 4 . In part (a)  401 , the identifiers from the two files are displayed. In part (b)  402 , every identifier from one file that can be found as a sequence within an identifier from the other file is listed. So the identifier “abc” in file  1  can be found within identifiers “aabc”, “abc1111111”, and “abcxxxyz” in file  2 . 
         [0036]    The “instruction sequence matching” algorithm compares the first word of every statement in the pair of files. This algorithm finds sequences of code that appear to perform the same functions despite changed comments and identifier names. The algorithm determines the longest matching instruction sequence within both files. Look at the example code in  FIG. 3  part (a)  301 . In this case, the instruction sequence of lines  2  through  9  in file  1  matches the instruction sequence of lines  2  through  8  in file  2  because the first word in each non-blank line in file  1  is identical to the first word of the corresponding line in file  2 . There are  6  statements in this sequence, so the algorithm yields a value of  6 . If a longer sequence of statements is found in the file, this algorithm returns the number of statements in the longer sequence. 
         [0037]    The entire correlation algorithm, applying all five algorithms, is shown in  FIG. 5 . In the first step  501 , the statement, comment, and identifier arrays for the two files are created. In the second step  502 , the statement arrays of the two files are compared using the statement matching algorithm. In the third step  503 , the comment arrays of the two files are compared using the comment matching algorithm. In the fourth step  504 , the identifier arrays of the two files are compared using the identifier matching algorithm. In the fifth step  505 , the identifier arrays of the two files are compared using the partial identifier matching algorithm. In the sixth step  506 , the statement arrays of the two files are compared using the instruction sequence matching algorithm. Although all matching algorithms produce output for the user, in the seventh step  507 , the results of all matching algorithms are combined into a single correlation score. 
         [0038]    The correlation score t is a measure of the similarity of the file pairs. A higher score means higher correlation. This score is given by the following equation. 
         [0000]    
       
      
       t=k 
       w 
       +w+k 
       p 
       p+k 
       s 
       s+k 
       c 
       c+k 
       q 
       q  
      
     
         [0039]    where 
         [0040]    w is the number of matching identifiers in the source code of the pair of files, 
         [0041]    p is the number of partially matching identifiers in the source code of the pair of files, 
         [0042]    s is the number of matching statements in the pair of files, 
         [0043]    c is the number of matching comments in the pair of files, and 
         [0044]    q is the number of lines in the longest matching instruction sequence in the pair of files, 
         [0045]    and where 
         [0046]    k w  is a weight given to the number of matching identifiers in the source code of the pair of files, 
         [0047]    k p  is a weight given to the number of partially matching identifiers in the source code of the pair of files, 
         [0048]    k s  is a weight given to the number of matching statements in the pair of files, 
         [0049]    k c  is a weight given to the number of matching comments in the pair of files, and 
         [0050]    k q  is a weight given to the number of lines in the longest matching instruction sequence in the pair of files. 
         [0051]    The weights k w , k p , k s , k c , and k q  may be dependent on other factors such as the length or type of the identifiers, statements, comments, or sequences. 
         [0052]    The output of the correlation detection program is a correlation database file as shown in  FIG. 6 . The first section  601  of the database file specifies the name of the correlation program, the program version, and the date and time that the program began execution. 
         [0053]    The next section of the database file  602  specifies the weights given to the results of each of the five algorithms. In the example,
       k=4 as specified by the tag &lt;IDWeight&gt;,   k p =2 as specified by the tag &lt;PIDWeight&gt;,   k s =10 as specified by the tag &lt;StatementWeight&gt;   k c =10 as specified by the tag &lt;CommentWeight&gt;, and   k q =100 as specified by the tag &lt;MaxSequenceWeight&gt;.       
 
         [0059]    The next section  603  of the database file specifies the two folders containing the source code files that are being compared, the programming language of the source code files, and the source code file name types. 
         [0060]    The next section  604  of the database file specifies the different algorithms being used in the comparison. 
         [0061]    The next section  605  of the database file specifies the directory and file name for each of the two source code files being compared. 
         [0062]    The next section  606  of the database file shows the matching identifiers that were found in the two files. The &lt;ID&gt; tag specifies the beginning of the list of matching identifiers. The &lt;/ID&gt; tag specifies the end of the list of matching identifiers. The identifiers are listed on the lines beginning with the &lt;ID&gt; tag. In the example, the identifiers “aux,” “b1,” “dump,” “happy123,” “image,” “IsWin95,” “len,” “nPlatformVersion,” “private,” “program,” “String,” “TelePhone,” “tran_two,” and “xxx” were found in both files. 
         [0063]    The next section  607  of the database file shows the partially matching identifiers that were found in the two files. The &lt;PID&gt; tag specifies the beginning of the list of partially matching identifiers. The &lt;/PID&gt; tag specifies the end of the list of partially matching identifiers. The partially matching identifiers are listed on the lines beginning with the &lt;PID&gt; tag. 
         [0064]    The next section  608  of the database file shows the matching statements that were found in the two files. The &lt;Statements&gt; tag specifies the beginning of the list of matching statements. The &lt;/Statements&gt; tag specifies the end of the list of matching statements. The &lt;Line&gt; tag specifies the actual statement that was found in both files. The &lt;Lines 1 &gt; tag specifies the line numbers in the first file where this statement was found. The &lt;Lines 2 &gt; tag specifies the line numbers in the second file where this statement was found. 
         [0065]    The next section  609  of the database file shows the matching comments that were found in the two files. The &lt;Comments&gt; tag specifies the beginning of the list of matching comments. The &lt;/Comments&gt; tag specifies the end of the list of matching comments. The &lt;Line&gt; tag specifies the actual comment that was found in both files. The &lt;Lines 1 &gt; tag specifies the line numbers in the first file where this comments was found. The &lt;Lines 2 &gt; tag specifies the line numbers in the second file where this comments was found. 
         [0066]    The next section  610  of the database file shows the matching instruction sequences that were found in the two files. The &lt;Sequences&gt; tag specifies the beginning of the list of matching instruction sequences. The &lt;/Sequences&gt; tag specifies the end of the list of matching instruction sequences. The &lt;Seq&gt; tag specifies the actual sequences that was found in both files. The first number is the line number of the beginning of the sequence in the first file. The second number is the line number of the beginning of the sequence in the second file. The third number is the number of matching lines in the sequence. 
         [0067]    The next section  611  shows the correlation score t of the two files. Sections  605  through  611  are repeated for each pair of files that have been compared. 
         [0068]    A post-process filter file is shown in  FIG. 7 . Section  701  of the filter file specifies the identifiers to be filtered out of the correlation database file. Each identifier is preceded by the &lt;Identifier&gt; tag. 
         [0069]    The next section  702  of the filter file specifies the statements to be filtered out of the correlation database file. Each instruction is preceded by the &lt;Statement&gt; tag. 
         [0070]    The next section  703  of the filter file specifies the comments to be filtered out of the correlation database file. Each comment is preceded by the &lt;Comment&gt; tag. 
         [0071]    The next section  704  of the filter file specifies the files to be filtered out of the correlation database file. Each file name with its full path is preceded by the &lt;File&gt; tag. The file name and path name can include wildcard characters such as *, in order to filter out entire sets of files with the same name in different folders or all files within a particular folder. 
         [0072]    The next section  705  of the filter file specifies whether instruction sequences should be filtered out. The tag &lt;NoSequences&gt; causes all instruction sequences to be filtered out. If there were no tag in this section, no instruction sequences would be filtered out. 
         [0073]    The next section  706  of the filter file includes various other parameters that can be applied to the correlation database file. In this example, the minimum correlation score is specified as  100  while the maximum correlation score is specified as  500 . All file pairs that do not fall within this range will be filtered out of the correlation database file. 
         [0074]      FIG. 8  shows a process for filtering a correlation database. The process begins at step  801  and continues to step  802  where the filter file is read. The identifiers, statements, comments, and files to be filtered are stored in lists. The minimum and maximum correlation scores to be filtered are also read from the filter file and stored in variables MinScore and MaxScore respectively. If no minimum correlation score is specified in the filter file then MinScore is set to the absolute minimum correlation value of 0. If no maximum correlation score is specified in the filter file then MaxScore is set to the absolute maximum correlation score possible. 
         [0075]    The process continues to step  803  where the program section  601  of the correlation database file is read. Because section  601  contains general information, it is simply copied to the filtered correlation database file—there is no information in this section to filter out. 
         [0076]    The process continues to step  804  where the weight section  602  of the correlation database is read. Section  602  is written to the filtered correlation database file and the weights are stored in variables. 
         [0077]    The process continues to step  805  where the setup section  603  of the correlation database file is read and written to the filtered correlation database file. 
         [0078]    The process continues to step  806  where the algorithm section  604  of the correlation database file is read and written to the filtered correlation database file. 
         [0079]    The process continues to step  807  where the correlation database is tested for an end-of-file condition (EOF). If an EOF is found, the filtering process is complete, the filtered correlation database file has been written, and the process goes to step  808  where is terminates. If an EOF is not found, the process continues to step  809  where the file section  605  of the correlation database file is read and written to a temporary file. In this step the variable FilterScore is set to 0 and the filtering process begins for the pair of correlated source code files specified in the correlation database file. The full path names of the two source code files specified in the correlation database file are stored in variables File 1  and File 2 . 
         [0080]    The process continues to step  810  where the identifier section  606  of the correlation database file is read. Each identifier is compared to the list of filtered identifiers. Each identifier that is not found in the list is written to the temporary file. If an identifier is found on the list, it is not written to the temporary file and the value corresponding to the weight given to the identifier, as determined by the weight section  602  of the correlation database file that was read in step  804 , is added to the variable FilterScore. 
         [0081]    The process continues to step  811  where the partial identifier section  607  of the correlation database file is read and written to the temporary file. In this embodiment, partial identifiers are not filtered, though in other embodiments they can be filtered in a manner similar to the way that identifiers are filtered. 
         [0082]    The process continues to step  812  where the statement section  608  of the correlation database file is read. Each statement is compared to the list of filtered statements. All statements not found in the list are written to the temporary file. If a statement is found on the list, it is not written to the temporary file and the value corresponding to the weight given to the statement, as determined by the weight section  602  of the correlation database file that was read in step  804 , is added to the variable FilterScore. 
         [0083]    The process continues to step  813  where the comment section  609  of the correlation database file is read. Each comment is compared to the list of filtered comments. All comments not found in the list are written to the temporary file. If a comment is found on the list, it is not written to the temporary file and the value corresponding to the weight given to the comment, as determined by the weight section  602  of the correlation database file that was read in step  804 , is added to the variable FilterScore. 
         [0084]    The process continues to step  814  where the instruction sequence section  610  of the correlation database file is read. If instruction sequences are not filtered out then this entire section is written to the temporary file. 
         [0085]    The process continues to step  815  where the correlation score section  611  of the correlation database file is read. The correlation score for the particular file pair is read. The value of variable FilterScore is subtracted from the correlation score and stored in variable NewScore, representing the correlation score after the specified identifiers, statements, and comments have been filtered out. 
         [0086]    The process continues to step  816  where NewScore is compared to MinScore and MaxScore. If NewScore falls within these two limits, inclusively, then the process continues to step  817 . If NewScore does not fall within the two limits, inclusively, then the process skips steps  817  and  818  and proceeds to step  819 . 
         [0087]    At step  817  the list of filtered files is checked to determine whether File 1  or File 2  are in the list of filtered files. If not, then the process continues to step  818  where the temporary file is appended to the filtered correlation database file and NewScore is written to the filtered correlation database file as the correlation score in the correlation score section  611 . The process then continues to step  819 . If at step  817  File 1  or File 2  are in the list of filtered files, then the process skips step  818  and proceeds directly to step  819 . 
         [0088]    At step  819  the temporary file is deleted and the process proceeds to step  807  where the filtering process is repeated for another pair of files specified in the correlation database file until an EOF is reached. 
         [0089]      FIG. 9  shows the correlation database file of  FIG. 6  where the identifiers bit 32 , dump, image, program, nPlatformVersion, and IsWin95 have been filtered out. Sections  901  through  905  are identical to the original correlation database file sections  601  through  605  in  FIG. 6 . Sections  907  through  910  are identical to the original correlation database file sections  607  through  610  in  FIG. 6 . Section  906  differs from original section  606  in that the filtered identifiers are missing. Section  911  differs from original section  611  in that the correlation score has been reduced by the weights for the identifiers that have been filtered out. 
         [0090]      FIG. 10  shows the correlation database file of  FIG. 6  where the following statements have been filtered out: 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 #include &lt;Assert.h&gt; 
               
               
                   
                 #include &lt;RegStr.h&gt; 
               
               
                   
                 #include &lt;Stdio.h&gt; 
               
               
                   
                 #include &lt;TChar.h&gt; 
               
               
                   
                 p = null; 
               
               
                   
                 PW32N_ADAPTER_INFO pAdapterInfo, 
               
               
                   
                   
               
             
          
         
       
     
         [0091]    Sections  1001  through  1007  are identical to the original correlation database file sections  601  through  607  in  FIG. 6 . Sections  1009  through  1010  are identical to the original correlation database file sections  609  through  610  in  FIG. 6 . Section  1008  differs from original section  608  in that the filtered statements are missing. Section  1011  differs from original section  611  in that the correlation score has been reduced by the weights for the statements that have been filtered out. 
         [0092]      FIG. 11  shows the correlation database file of  FIG. 6  where the following comments have been filtered out: 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 #include “WiNDIS.h” 
               
               
                   
                 * Copyright (c) 1992, 1993, 1994, 1995, 1996 
               
               
                   
                 * THIS SOFTWARE IS PROVIDED AS IS 
               
               
                   
                 &gt;printf(“%u %u %u %u\n”, insn-&gt;code, 
               
               
                   
                   
               
             
          
         
       
     
         [0093]    Sections  1101  through  1108  are identical to the original correlation database file sections  601  through  608  in  FIG. 6 . Section  1110  is identical to the original correlation database file section  610  in  FIG. 6 . Section  1109  differs from original section  609  in that the filtered comments are missing. Section  1111  differs from original section  611  in that the correlation score has been reduced by the weights for the comments that have been filtered out. 
         [0094]      FIG. 12  shows the correlation database file of  FIG. 6  where the instruction sequences have been filtered out. Sections  1201  through  1209  are identical to the original correlation database file sections  601  through  609  in  FIG. 6 . Section  1210  is identical to the original correlation database file section  611  in  FIG. 6 . Section  610  of the original correlation database file has been entirely filtered out of the filtered correlation database file. 
         [0095]    Various modifications and adaptations of the embodiment that is described here would be apparent to those skilled in the art based on the above disclosure. Many variations and modifications within the scope of the invention are therefore possible. The present invention is set forth by the following claims.