Method of identifying similarities in code segments

• US 5,699,507 A
• Filed: 01/17/1995
• Issued: 12/16/1997
• Est. Priority Date: 01/17/1995
• Status: Expired due to Term

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Puttress, John J., Seaquist, Carl Robert, Helfman, Jonathan Isaac, Kowalski, Thaddeus Julius, Goodnow, James E. II, Rowland, James R.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Palys, Joseph E.
• Application Number:
  US08/373,342
• Time in Patent Office: 1,064 Days
• Field of Search: 395/183.14, 395/183.13, 395/704, 395/568
• US Class Current: 714/38.1
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589

Abstract

A method of analyzing a plurality of code segments to determine the similar static and dynamic features of the code segments compares the static and dynamic features of each of the code segments. Each code segment is comprised of one or more lines of program instructions. One or more predetermined static attributes are extracted from each code segment. Each code segment is then run so that the dynamic attributes of the code segment can be determined. The dynamic attributes are extracted from each code segment and a distance function is computed which is based on the extracted static and dynamic attributes for a given pair of code segments. The distance function produces a distance measurement which indicates the relative degree of similarity between the given pair of code segments.

Claims

1. A method of analyzing a plurality of code segments, each code segment comprised of one or more lines of program instructions, the method comprising:

extracting from each code segment one or more predetermined static attributes;

running each said code segment;

extracting from each said code segment dynamic attributes;

computing a distance function based on said extracted static and dynamic attributes for a given pair of code segments, said distance function producing a number of distance measurements; and

displaying said distance measurements.

2. A method of analyzing at least one attribute in at least two code segments, each code segment comprised of one or more lines of program instructions, the method comprising:

identifying one or method dynamic attributes;

running each code segment and extracting the identified dynamic attributes from said code segment; and

computing a distance function based on the extracted dynamic attributes from each code segment, said distance function producing a measurement indicative of the degree of similarity between the code segments.

3. The method according to claim 2 wherein a weighing function is applied to one or more of the identified dynamic attributes.

4. The method according to claim 2 wherein said measurement falls within a range from 0 to 1 inclusive.

5. The method according to claim 4 wherein a measurement equal to 1 indicates that the code segments are identical.

6. The method according to claim 4 wherein a measurement equal to zero indicates that there are no similarities between said code segments.

7. The method according to claim 2 further comprising the steps of:

identifying one or more semantic attributes for which a measurement of similarity is to be made;

extracting said identified semantic attributes from each code segment; and

computing a distance function based on the extracted semantic attributes from each code segment, said distance function producing a measurement indicative of the degree of similarity between the code segments.

8. The method according to claim 7 wherein said semantic attributes include operators.

9. The method according to claim 7 wherein said measurement falls within a range from 0 to 1 inclusive.

10. The method according to claim 9 wherein a measurement equal to 1 indicates that the code segments are identical.

11. The method according to claim 9 wherein a measurement equal to 0 indicates that there are no similarities between the code segments.

12. The method according to claim 7 wherein a weighing function is applied to one or more of the semantic attributes.

13. A method of analyzing at least one attribute in at least two code segments, each code segment comprised of one or more lines of program instructions, the method comprising:

identifying one or more semantic attributes;

extracting said identified semantic attributes from each code segment; and

computing a distance function based on the extracted semantic attributes from each code segment said distance function producing a measurement indicative of the degree of similarity between the code segments.

14. The method according to claim 13 wherein said semantic attributes include operators.

15. The method according to claim 13 wherein said measurement fails within a range from 0 to 1 inclusive.

16. The method according to claim 15 wherein a measurement equal to 1 indicates that the code segments arc identical.

17. The method according to claim 15 wherein a measurement equal to 0 indicates that there are no similarities between the code segments.

18. The method according to claim 13 wherein a weighing function is applied to one or more of the semantic attributes.

19. The method according to claim 13 further comprising the steps of:

identifying one or more dynamic attributes;

running each code segment and extracting the identified dynamic attributes from said code segment; and

computing a distance function based on the extracted dynamic attributes from each code segment, said distance function producing a measurement indicative of the degree of similarity between the code segments.

20. The method according to claim 19 wherein a weighing function is applied to one or more of the identified dynamic attributes.

21. The method according to claim 19 wherein said measurement fails within a range from 0 to 1 inclusive.

22. The method according to claim 21 wherein a measurement equal to 1indicates that the code segments are identical.

23. The method according to claim 21 wherein a measurement equal to zero indicates that there are no similarities between said code segments.

24. A method of analyzing at least one attribute in at least cut two code segments, each code segment comprised of one or more lines of program instructions, the method comprising:

identifying one or more semantic attributes;

extracting said identified semantic attributes from each code segment;

identifying one or more dynamic attributes;

running each code segment and extracting the identified dynamic attributes from said code segment; and

computing a distance function based on the extracted semantic and dynamic attributes from each code segment, said distance function producing a measurement indicative of the degree of similarity between the code segments.

25. The method according to claim 24 wherein a weighing function is applied to one or more of the identified dynamic attributes.

26. The method according to claim 24 wherein a weighing function is applied to one or more of the semantic attributes.

27. The method according to claim 24 wherein said measurement falls within a range from 0 to inclusive.

28. The method according in claim 27 wherein a measurement equal to 1 indicates that the code segments are identical.

29. The method according to claim 27 wherein a measurement equal to zero indicates that there are no similarities between said code segments.

30. The method according to claim 24 wherein said semantic attributes include operators.

31. The method according to claim 24 wherein said semantic attribute is comprised of one or more code fragments which are programmed to perform a particular function, the method further comprising the steps of:

identifying which code segments contain the one or more code fragments; and

determining whether the code fragments within the identified code segments perform the particular function.

32. The method according to claim 24 further comprising the steps of:

categorizing the code segments that are similar based on the identified attributes contained within the code segments;

allocating resources for creating a general purpose library; and

storing said categorized code segments in said general purpose library.

33. The method according to claim 24 further comprising the steps of:

identifying one or more groups of code segments which contain similar dynamic attributes

creating one or more storage modules; and

storing each group of code segments in a different storage module.

34. The method according to claim 24 wherein said code segments are comprised of one or more lines of instructions programmed in C code.

35. The method according to claim 24 wherein said code segments are comprised of one or more lines of instructions programmed in C++ code.