Automatic Extraction of Programming Rules

• US 20080127043A1
• Filed: 08/30/2006
• Published: 05/29/2008
• Est. Priority Date: 08/30/2006
• Status: Abandoned Application

• Current Assignee: Yuanyuan Zhou, Zhenmin Li
• Original Assignee: Yuanyuan Zhou, Zhenmin Li
• Inventors: Li, Zhenmin, Zhou, Yuanyuan
• Application Number:
  US11/468,589
• Publication Number:
  US 20080127043A1
• Time in Patent Office: Days
• US Class Current: 717/104
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589

Abstract

In accordance with certain aspects of the automatic extraction of programming rules, a plurality of portions of a program are identified. A plurality of sets of numeric values are obtained by generating, for each of the plurality of portions, a set of numeric values that represents the portion. The plurality of sets of numeric values are analyzed to identify programming patterns, and a plurality of programming rules are generated from the programming patterns.

Claims

1. One or more computer readable media having stored thereon a plurality of instructions to extract programming rules from a program, the plurality of instructions causing, when executed by one or more processors of a computer, the one or more processors to:

identify a plurality of portions of the program;

obtain a plurality of sets of numeric values by generating, for each of the plurality of portions, a set of numeric values that represents the portion;

analyze the plurality of sets of numeric values to identify programming patterns; and

generate, from the programming patterns, a plurality of programming rules.

2. One or more computer readable media as recited in claim 1, wherein to generate a set of numeric values that represents the portion is to generate, as the set of numeric values, a set of hash values by hashing elements of the portion.

3. One or more computer readable media as recited in claim 1, wherein each of the plurality of portions is a function of the program, and wherein to obtain the plurality of sets of numeric values is to, for each function:

identify one or more elements in the function;

modify particular ones of the one or more elements to generate one or more modified elements;

generate a hash value for each of the one or more modified elements; and

generate the set of numeric values by including, in a set of values, the generated hash values.

4. One or more computer readable media as recited in claim 3, wherein to modify the particular ones of the one or more elements is to add a prefix to each of the one or more elements, the prefix identifying a data type of the element.

5. One or more computer readable media as recited in claim 3, wherein to modify the particular ones of the one or more elements is to add, to each of the one or more elements that is a field name in a data structure, an indication of a type of the data structure.

6. One or more computer readable media as recited in claim 1, wherein to analyze the plurality of sets of numeric values is to use frequent itemset mining to identify sets of numeric values appearing more than a threshold number of times in the plurality of sets of numeric values, and identify programming patterns corresponding to the identified sets of numeric values.

7. One or more computer readable media as recited in claim 1, wherein to generate the plurality of programming rules is to:

identify each possible programming rule for each programming pattern;

determine a confidence value for each identified programming rule; and

include, in the plurality of programming rules, only those identified programming rules having a confidence value that exceeds a threshold confidence value.

8. One or more computer readable media as recited in claim 1, the plurality of instructions further causing the one or more processors to:

detect a plurality of violations of the plurality of programming rules; and

identify one or more of the plurality of violations as potential errors in the program.

9. One or more computer readable media having stored thereon a plurality of instructions to detect potential errors in a program, the plurality of instructions causing, when executed by one or more processors of a computer, the one or more processors to:

automatically identify a plurality of programming rules in the program;

detect a plurality of violations of the plurality of programming rules; and

identify one or more of the plurality of violations as potential errors in the program.

10. One or more computer readable media as recited in claim 9, the plurality of instructions further causing the one or more processors to:

detect one or more false violations in the plurality of violations;

remove the one or more false violations from the plurality of violations to obtain a plurality of potential errors; and

wherein to identify one or more of the plurality of violations as potential errors in the program is to identify the plurality of potential errors as the potential errors in the program.

11. One or more computer readable media as recited in claim 10, wherein to detect one or more false violations is to:

identify one or more missing elements of one of the plurality of programming rules that results in a violation of the programming rule;

check, for a function in the program that includes the violation, one or more additional functions in the program that are called by the function;

identify the violation in the function as a false violation if the one or more additional functions include the one or more missing elements.

12. One or more computer readable media as recited in claim 10, wherein to detect one or more false violations is to:

identify one or more missing elements of one of the plurality of programming rules that results in a violation of the programming rule;

check, for a function in the program that includes the violation, one or more additional functions in the program call the function;

identify the violation in the function as a false violation if each of the one or more additional functions includes all of the one or more missing elements.

13. One or more computer readable media as recited in claim 9, the plurality of instructions further causing the one or more processors to:

rank the errors of the plurality of potential errors based on confidence values of the programming rules that the plurality of potential errors violate; and

identify, in an order based on the rankings, the plurality of potential errors as potential errors in the program.

14. One or more computer readable media as recited in claim 9, the plurality of instructions further causing the one or more processors to:

group the plurality of violations by functions of the program;

identify, for each function that includes at least one of the plurality of violations, a confidence value for each programming rule that is violated by the function;

select a largest confidence value of the confidence values for the programming rules;

assign the selected confidence value to the function; and

rank the functions according to their assigned confidence values.

15. One or more computer readable media as recited in claim 9, wherein to detect the plurality of violations of the plurality of programming rules is to:

determine, for each of the plurality of programming rules, a confidence value for the programming rule;

determine whether the confidence value for the programming rule is between a threshold confidence value and 100%; and

if the confidence value for the programming rule is between the threshold confidence value and 100%, then detect those cases where the programming rule is violated as one of the plurality of violations, otherwise detect that the programming rule is not violated.

16. One or more computer readable media as recited in claim 9, wherein to automatically identify the plurality of programming rules is to:

identify a plurality of portions of the program;

obtain a plurality of sets of numeric values by generating, for each of the plurality of portions, a set of numeric values that represents the portion;

analyze the plurality of sets of numeric values to identify programming patterns; and

generate, from the programming patterns, the plurality of programming rules.

17. A method comprising:

identifying a plurality of portions of a program;

obtaining a plurality of sets of numeric values by generating, for each of the plurality of portions, a set of numeric values that represents the portion;

analyzing the plurality of sets of numeric values to identify programming patterns;

generating, from the programming patterns, a plurality of programming rules;

detecting a plurality of violations of the plurality of programming rules; and

identifying one or more of the plurality of violations as potential errors in the program.

18. A method as recited in claim 17, wherein each of the plurality of portions is a function of the program, and obtaining the plurality of sets of numeric values comprises, for each function:

identifying one or more elements in the function;

modifying particular ones of the one or more elements to generate one or more modified elements;

generating a hash value for each of the one or more modified elements; and

generating the set of numeric values by including, in a set of values, the generated hash values.

19. A method as recited in claim 17, wherein analyzing the plurality of sets of numeric values comprises:

using frequent itemset mining to identify sets of numeric values appearing more than a threshold number of times in the plurality of sets of numeric values; and

identifying programming patterns corresponding to the identified sets of numeric values.

20. A method as recited in claim 17, wherein generating the plurality of programming rules comprises:

identifying each possible programming rule for each programming pattern;

determining a confidence value for each identified programming rule; and

including, in the plurality of programming rules, only those identified programming rules having a confidence value that exceeds a threshold confidence value.

21. A method as recited in claim 17, further comprising:

detecting one or more false violations in the plurality of violations;

removing the one or more false violations from the plurality of violations to obtain a plurality of potential errors; and

wherein identifying one or more of the plurality of violations as potential errors in the program comprises identifying the plurality of potential errors as the potential errors in the program.

22. A method as recited in claim 17, further comprising:

ranking the errors of the plurality of potential errors based on confidence values of the programming rules that the plurality of potential errors violate; and

identifying, in an order based on the rankings, the plurality of potential errors as potential errors in the program.

23. A computing device comprising:

a processor; and

a memory, coupled to the processor, to store instructions to be executed by the processor in order to extract programming rules from a program by;

identifying a plurality of portions of the program;

obtaining a plurality of sets of values by generating, for each of the plurality of portions, a set of values that represents the portion;

analyzing the plurality of sets of values to identify programming patterns; and

generating, from the programming patterns, a plurality of programming rules.

24. A computing device as recited in claim 23, wherein each of the plurality of portions comprises a function of the program.

25. A computing device as recited in claim 23, wherein the instructions are further to be executed by the processor in order to detect potential errors in the program by:

detecting a plurality of violations of the plurality of programming rules;

detecting one or more false violations in the plurality of violations;

removing the one or more false violations from the plurality of violations to obtain a plurality of potential errors; and

identifying the plurality of potential errors as the potential errors in the program.

26. A computing device as recited in claim 23, wherein analyzing the plurality of sets of values comprises:

using frequent itemset mining to identify sets of values appearing more than a threshold number of times in the plurality of sets of values; and

identifying programming patterns corresponding to the identified sets of values.

27. A computing device as recited in claim 23, wherein generating the plurality of programming rules comprises:

identifying each possible programming rule for each programming pattern;

determining a confidence value for each identified programming rule; and

including, in the plurality of programming rules, only those identified programming rules having a confidence value that exceeds a threshold confidence value.