Source code similarity detection using digital fingerprints

1. A method for identifying similarity in source code in accordance with searching digital fingerprints representing at least blocks of programming statements, the method comprising:

accessing, by at least one processor configured by executing program instructions stored on non-transitory processor-readable media, source code;

converting, by at least one processor, at least some of the source code into a plurality of tokens, each token being associated with a plurality of blocks of programming statements;

modifying, by at least one processor, the tokens by normalizing at least one value in at least one of the plurality of blocks of programming statements and by defining at least one abstraction of syntactic structure associated with at least one operation associated with at least one of the blocks of programming statements;

creating, by at least one processor, a representation associated with control flow of the plurality of blocks of programming statements associated with the modified tokens, wherein the control flow includes a plurality of possible operational paths that can be traversed during execution of the source code and associated with the plurality of blocks of programming statements associated with each of the modified tokens;

for each of the possible operational paths that can be traversed during execution:

estimating, by at least one processor, a respective probability of execution as a function of at least one heuristic; and

generating, by at least one processor, as a function of at least the estimated respective probability, a digital fingerprint, wherein the digital fingerprint represents code semantics and code behavior; and

determining, by at least one processor, source code within at least one block of a given token which is identifiable as being a duplicate of source code stored in a repository by comparing the generated digital fingerprint and at least one previously generated digital fingerprint.

2. The method of claim 1 , further comprising:

generating, by at least one processor, an abstract syntax tree from the tokens, wherein the abstract syntax tree comprises a plurality of nodes corresponding to the source code.

3. The method of claim 2 , wherein the abstract syntax tree is derived by:

defining a root element;

assigning statements to each of at least one child node of the root element; and

assigning a value and/or a variable to each of the at least one child node.

4. The method of claim 1 , wherein the generated representation associated with the control flow is a control flow graph.

5. The method of claim 4 , further comprising:

generating, by at least one processor, an abstract syntax tree from the tokens; and

generating the control flow graph using the abstract syntax tree.

6. The method of claim 1 , further comprising:

generating, by at least one processor, a digital fingerprint representing a source code program associated with at least one of the tokens.

7. The method of claim 6 , further comprising:

identifying, by at least one processor as a function of searching and detecting a match between the generated digital fingerprint representing the source code program and at least one previously generated digital fingerprint representing a different source code program, a duplicate of at least part of the source code program associated with at least one of the respective tokens and the different source code program.

8. The method of claim 6 , further comprising:

determining, by at least one processor, that the generated digital fingerprint representing the source code program and at least one previously generated digital fingerprint representing a different source code program meet a predetermined threshold of similarity;

identifying, by at least one processor, at least one statement in the source code program that is a duplicate; and

identifying, by at least one processor, at least one source code program that contains the at least one statement that is a duplicate.

9. The method of claim 1 , wherein the digital fingerprint is generated as a function of hashing.

10. The method of claim 1 , wherein the comparing locates a match between the generated digital fingerprint and the at least one previously generated digital fingerprint.

11. The method of claim 10 , wherein the match is within a prescribed tolerance.

12. The method of claim 1 , wherein the digital fingerprint represents a fixed sized source code program, and further comprising:

generating, by at least one processor, a digital fingerprint representing at least one source code fragment.

13. The method of claim 1 , further comprising:

generating, by at least one processor, a plurality of digital fingerprints; and

grouping, by at least one processor, at least some of the plurality of digital fingerprints based at least on a number of blocks,

wherein determining the source code within at least one block of a given token which is identifiable as being a duplicate of source code stored in a repository occurs for just source code associated with the at least some of the plurality of digital fingerprints.

14. A system for identifying similarity in source code in accordance with searching digital fingerprints representing at least blocks of programming statements, the system comprising:

non-transitory processor readable media;

at least one processor operatively coupled to the at least one processor readable media;

the non-transitory processor readable media having instructions for causing the following steps to be performed by the at least one processor:

accessing source code;

converting at least some of the source code into a plurality of tokens, each token being associated with a plurality of blocks of programming statements;

modifying, by at least one processor, the tokens by normalizing at least one value in at least one of the plurality of blocks of programming statements and by defining at least one abstraction of syntactic structure associated with at least one operation associated with at least one of the blocks of programming statements;

creating a representation associated with control flow of the plurality of blocks of programming statements associated with the modified tokens, wherein the control flow includes a plurality of possible operational paths that can be traversed during execution of the source code and associated with the plurality of blocks of programming statements in each of the modified tokens;

for each of the possible operational paths that can be traversed during execution:

estimating a respective probability of execution as a function of at least one heuristic; and

generating, as a function of at least the estimated respective probability, a digital fingerprint, wherein the digital fingerprint represents code semantics and code behavior; and

determining source code within at least one block of a given token which is identifiable as being a duplicate of source code stored in a repository by comparing the generated digital fingerprint and at least one previously generated digital fingerprint.

15. The system of claim 14 , wherein the non-transitory processor readable media further have instructions for causing the following steps to be performed by the at least one processor:

generating an abstract syntax tree from the tokens, wherein the abstract syntax tree comprises a plurality of nodes corresponding to the source code.

16. The system of claim 15 , wherein the abstract syntax tree is derived by:

defining a root element;

assigning statements to each of at least one child node of the root element; and

assigning a value and/or a variable to each of the at least one child node.

17. The system of claim 14 , wherein the generated representation associated with the control flow is a control flow graph, and further wherein the non-transitory processor readable media further have instructions for causing the following steps to be performed by the at least one processor:

generating an abstract syntax tree from the tokens; and

generating the control flow graph using the abstract syntax tree.

18. The system of claim 14 , wherein the generated digital fingerprint further represents control flow associated with a plurality of the blocks.

19. The system of claim 14 , wherein the non-transitory processor readable media further have instructions for causing the following steps to be performed by the at least one processor:

generating, by at least one processor, a digital fingerprint representing a source code program associated with at least one of the tokens.

20. The system of claim 19 , wherein the non-transitory processor readable media further have instructions for causing the following steps to be performed by the at least one processor:

identifying, as a function of searching and detecting a match between the generated digital fingerprint representing the source code program and at least one previously generated digital fingerprint representing a different source code program, a duplicate of at least part of the source code program associated with at least one of the respective tokens and the different source code program.

21. The system of claim 19 , wherein the non-transitory processor readable media further have instructions for causing the following steps to be performed by the at least one processor:

determining that the generated digital fingerprint representing the source code program and at least one previously generated digital fingerprint representing a different source code program meet a predetermined threshold of similarity;

identifying at least one statement in the source code program that is a duplicate; and

identifying at least one source code program that contains the at least one statement that is a duplicate.

22. The system of claim 14 , wherein the comparing locates a match between the generated digital fingerprint and the at least one previously generated digital fingerprint.

23. The system of claim 22 , wherein the match is within a prescribed tolerance.

24. A method for identifying similarity in source code in accordance with searching digital fingerprints representing at least blocks of programming statements, the method comprising:

accessing, by at least one processor configured by executing program instructions stored on non-transitory processor-readable media, source code;

transforming, by at least one processor, the source code into a data representation of a control flow that can be traversed during execution of the source code;

for each of possible operational paths that can be traversed during execution:

estimating, by at least one processor, a respective probability of execution as a function of at least one heuristic; and

generating, by at least one processor as a function of at least the estimated respective probability, a digital fingerprint associated with the represented control flow;

comparing, by at least one processor, at least one of the generated digital fingerprint with at least one other stored fingerprint to detect a match; and

identifying, by at least one processor, source rode associated with one of the at least one other fingerprint as a function of the match.