4
$\begingroup$

I have some experience in machine learning, mainly clustering and classifiers. However, I am somewhat of a newbie when it comes to NLP.

That said I am aware of all the various issues and difficulties involved in processing natural language eg part-of-speech, ambiguity, negation detection etc. I am also aware of certain models to represent text such as bag-of-words and Word vector representation.

Whilst the specific problem I have is a textual problem, it is not to my mind a natural language problem. Instead I need to compare 1000s of files of programming code to determine how similar they are to one another.

Unlike natural language processing where we remove stop-words and we care very much about issues such as ambiguity and the scope of negation etc, with programming code there is no ambiguity, at least not with reserved key words such as "function", "if", "else, "while", "end", nor is there any ambiguity with core mathematical functions and other operators eg "log", "sin", "tanh" etc.

For my problem, we can assume all files are in the same programming language (let's say R) and let's also assume that each programming file contains at most 250 lines of code.

The initial objective is to produce a correlation matrix that shows how similar the code files are to one another.

There are to my mind 2 ways of approaching this:

  1. Quick and simplistic. I propose to remove from each text file:

    • All comments as I'm not interested in each developer's individual comments
    • All excessive white space, ie remove all formatting ensuring there is only one space between reserved words and blocks of code

    This is the only pre-processing I would do in a simplistic solution.

    I then propose to use the Doc2Vec model to reduce each file to a single vector and then compare the various vectors to one another by calculating the correlation coefficient.

    Does this seem reasonable to people for a very quick and simplistic solution? If not, please advise what other pre-processing you would do and/or what model you would use to represent the files.

  2. More advanced. An immediate flaw with the simplistic solution is that it is too naive. For instance:

    • If Code A and Code B have exactly the code (ie same functions that perform exactly the same task and all variable and object names are the same) except that Code A's functions are listed in a slightly different order to those listed in Code B's file, then a line-by-line comparison of the two code files will obviously show differences. However, if the code in file B was ``reordered'' so that the functions were in exactly the same order as file A, then there wouldn't be any differences.

    • Code A and Code B could in logical terms be exactly the same (ie same number of functions that perform logically the same operations and output) except that object, variable and function names are different (after all that is a subjective choice by each coder) then again we would have significant differences. For example, in Code A's file there is a function called MyFunction(a,b) whereas in Code B's file there is a function called CopyMyFunction(x,y). Now if both functions perform exactly the same operations (eg the sum of the two input values) then logically the code is the same - it's just the variable names that are different.

    • Finally a more complicated version. Suppose there is a function in Code A's file called MyAverage(a,b) that performs the operations, returning as output d:

      c = a + b

      d = c/2

      Suppose in Code B's file there is also a function called MyAverage(a,b) that performs the same calculation but in only one step, ie

      c = (a + b)/2

      Logically the two functions produce exactly the same output, albeit Code A does it in 2 steps whereas Code B does it in 1 step.

    The above are clearly only some examples of the types of issues that could be encountered.

The objective is not to determine whether there has been plagiarism or whether sections of code have been copied from one code file to another. Instead, if a serious error (a bug or logical error) is subsequently found in one code file, then I need a means of identifying how likely that same error occurs in other code files, ie has that bug propagated itself by being copied from file to file?

How would people approach the more advanced problem? For instance, to solve the last problem (ie determining whether two sections of code are logically equivalent) I could see two ways of approaching this:

  • Renaming of variables and substitution. So in Code A, as variable c is defined as "a + b", it could be substituted into the expression for variable d with the addition of the brackets. After the substitution, variable d could be renamed as variable c. In this case, Code B would then be the same as Code A.
  • Simulation of output. In more complicated function, the above technique may not always work. Instead, if the outputs of the two functions are the same when given the same inputs, can we deduce that the logic of the two must be the same within a certain level of confidence? The problem with this is that simulating millions of inputs would be very time consuming and expensive surely.

Other than the above I've no idea how to approach this problem.

Any thoughts on the approach and/or resources to use?

I am happy to be directed to a good reference or resource on the issue.

$\endgroup$
  • 2
    $\begingroup$ Good luck! The problem is undecidable and seems really hard in general, but it will be interesting if someone with related experience (software testing? formal verification?) can give you some insights. $\endgroup$ – Valentas Apr 27 '18 at 11:42
  • $\begingroup$ Is it possible to look at the 'compiled' code instead? $\endgroup$ – seanv507 Apr 28 '18 at 6:55
1
$\begingroup$

You can start with MOSS (Measure Of Software Similarity). It can find similar software documents in a set of software documents. It has several nice properties - whitespace insensitivity, noise suppression, and position independence. It is based on the more general idea of document fingerprinting where a hash is constructed of the document. The document hash values are compared. There is a more technical explanation in the Winnowing paper.

Here is a review paper covering additional techniques, such as Levenshtein String Edit Distance, RTED—Robust Algorithm for Tree Edit Distance, and Graph Edit Distance.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Hi. I don't think MOSS is a solution as it isn't one of the supported languages for MOSS. Am I missing something here? $\endgroup$ – user2948208 Apr 28 '18 at 17:57
  • $\begingroup$ MOSS is a general algorithm. It can be implemented in any language, including R. $\endgroup$ – Brian Spiering Apr 28 '18 at 18:48
0
$\begingroup$

An alternative approach which is probably not as advanced yet for this is some combination of a deep learning system with and modification of output to provide a 'similarity likelyhood.'

This paper Code2vec, and this one have a neural network training on code to encode it as a vector in a scalable way in order to predict its properties, and then perform some task depending on the paper. It could be conceivable that if you have 'labeled' code that fits the criteria that you want to train on, that a NN could be something to look into (atleast from a distance). The Code2vec intro seems to fit the problem for more complex examples, in terms of being able to predict outputs and compare code in a way that is similar to language (as there are plenty of NN architectures which do that in terms of summarization and sentiment analysis).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Hi. I hadn't heard of Code2Vec before, so that is very interesting - thanks. I'll definitely take a look at that. $\endgroup$ – user2948208 Apr 28 '18 at 17:57
  • $\begingroup$ Tis a long shot indeed, but hope it helps or is at least interesting. $\endgroup$ – Pavel Savine Apr 29 '18 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.