Mining source code for violations of programming rules
A method for software code analysis includes automatically processing a body of software source code ( 23 ) by a computer ( 22 ) in order to identify a group of sequences of instructions that are characterized by a common pattern. A sequence within the group containing a deviation from a norm of the common pattern is found and reported as a potential vulnerability in the software source code.
1. A method for software code analysis, comprising:
automatically normalizing a body of software source code by a computer, so as to generate a flow graph of the code, wherein the flow graph includes a sequence of tags representing instructions in the software code;
applying a sequence mining method to the flow graph of the code in order to identify a group of a plurality of sub-sequences in the sequence of tags of the flow graph, which sub-sequences are similar to each other;
determining for the identified group of sub-sequences, a common norm pattern;
finding a sub-sequence within the group deviating from the common norm pattern, by an extent beyond a threshold; and
reporting the deviating sub-sequence as a potential vulnerability in the software source code,
wherein the tags in the sub-sequences have the same order as in the sequence, but adjacent tags in the sub-sequences are not necessarily adjacent in the sequence.
2. The method according to claim 1 , wherein normalizing the body of the software code comprises creating a document object model (DOM) of the code.
3. The method according to claim 1 , wherein normalizing the code comprises finding in the code names of entities of a given type, and replacing the names appearing in the code with an indicator of the type.
4. The method according to claim 3 , wherein the entities whose names are replaced with the indicator of the type are selected from a group of the entities consisting of variables and constants.
5. The method according to claim 3 , wherein the code is written in an object-oriented language, and wherein the entities whose names are replaced with the indicator of the type are selected from a group of the entities consisting of classes and members.
6. The method according to claim 1 , wherein normalizing the code comprises finding in the code control blocks of a given type, each control block containing lines of the code, and replacing the lines of the code with a series of tags corresponding to the lines of the code in a format that is predefined for the type of the control block.
7. The method according to claim 1 , wherein the deviation in the sub-sequence comprises a missing operation in the software code.
8. The method according to claim 1 , wherein the deviation in the sub-sequence comprises a failure to check a permission to perform a sensitive operation.
9. The method according to claim 1 , wherein the deviation in the sub-sequence comprises a failure to follow a prescribed invocation sequence.
10. The method according to claim 1 , wherein the deviation in the sub-sequence is associated with a backdoor left in the code.
11. The method according to claim 1 , wherein the deviation in the sub-sequence comprises an error in business logic that is implemented in the code.
12. The method according to claim 1 , wherein applying the sequence mining method comprises identifying a stochastic group of sub-sequences of instructions having a maximum difference not greater than a user set radius.
13. The method according to claim 1 , wherein applying the sequence mining method comprises applying GSP, SPADE or PrefixSpan.
14. The method according to claim 1 , comprising receiving a user setting of the threshold, and wherein finding the sub-sequence within the group deviating from the common norm pattern comprises finding a sub-sequence deviating from the common norm pattern, by an extent beyond the user setting of the threshold.
15. Apparatus for software code analysis, comprising:
a memory, which is configured to store a body of software source code; and
a processor, which is configured to automatically normalize the software source code, so as to generate a flow graph of the code, wherein the flow graph includes a sequence of tags representing instructions in the software code, to apply a sequence mining method to the flow graph of the source code in order to identify a group of a plurality of sub-sequences in the sequence of tags, which sub-sequences are similar to each other, to determine for the identified group of sub-sequences a common norm pattern, to find a sub-sequence within the group containing a deviation from the common norm pattern by an extent beyond a threshold, and to report the deviation as a potential vulnerability in the software source code,
wherein the tags in the sub-sequences have the same order as in the sequence, but adjacent tags in the sub-sequences are not necessarily adjacent in the sequence.
16. The apparatus according to claim 15 , the processor is configured to create a document object model (DOM) of the code in normalizing the software source code.
17. The apparatus according to claim 15 , wherein normalizing the code comprises finding in the code names of entities of a given type, and replacing the names appearing in the code with an indicator of the type.
18. The apparatus according to claim 17 , wherein the entities whose names are replaced with the indicator of the type are selected from a group of the entities consisting of variables and constants.
19. The apparatus according to claim 17 , wherein the code is written in an object-oriented language, and wherein the entities whose names are replaced with the indicator of the type are selected from a group of the entities consisting of classes and members.
20. The apparatus according to claim 15 , wherein the processor is configured to normalize the code by finding in the code control blocks of a given type, each control block containing lines of the code, and replacing the lines of the code with a series of tags corresponding to the lines of the code in a format that is predefined for the type of the control block.
21. The apparatus according to claim 15 , wherein the deviation in the sub-sequence comprises a missing operation in the software code.
22. The apparatus according to claim 15 , wherein the deviation in the sub-sequence comprises a failure to check a permission to perform a sensitive operation.
23. The apparatus according to claim 15 , wherein the deviation in the sub-sequence comprises a failure to follow a prescribed invocation sequence.
24. The apparatus according to claim 15 , wherein the deviation in the sub-sequence is associated with a backdoor left in the code.
25. The apparatus according to claim 15 , wherein the deviation in the sub-sequence comprises an error in business logic that is implemented in the code.
26. A computer software product, comprising a non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to normalize a body of software source code, so as to generate a flow graph of the code, wherein the flow graph includes a sequence of tags representing instructions in the software code, to apply a sequence mining method to the flow graph of the code in order to identify a group of a plurality of sub-sequences in the sequence of tags, which sub-sequences are similar to each other, to determine for the identified group of sub-sequences a common norm pattern, to find a sub-sequence within the group containing a deviation from the common norm pattern by an extent beyond a threshold, and to report the deviation as a potential vulnerability in the software source code, wherein the tags in the sub-sequences have the same order as in the sequence, but adjacent tags in the sub-sequences are not necessarily adjacent in the sequence.
27. The product according to claim 26 , the instructions cause the computer to create a document object model (DOM) of the code in normalizing the software source code.
28. The product according to claim 26 , wherein normalizing the code comprises finding in the code names of entities of a given type, and replacing the names appearing in the code with an indicator of the type.
29. The product according to claim 28 , wherein the entities whose names are replaced with the indicator of the type are selected from a group of the entities consisting of variables and constants.
30. The product according to claim 28 , wherein the code is written in an object-oriented language, and wherein the entities whose names are replaced with the indicator of the type are selected from a group of the entities consisting of classes and members.
31. The product according to claim 26 , wherein normalizing the code comprises finding in the code control blocks of a given type, each control block containing lines of the code, and replacing the lines of the code with a series of tags corresponding to the lines of the code in a format that is predefined for the type of the control block.
32. The product according to claim 26 , wherein the deviation in the sub-sequence comprises a missing operation in the software code.
33. The product according to claim 26 , wherein the deviation in the sub-sequence comprises a failure to check a permission to perform a sensitive operation.
34. The product according to claim 26 , wherein the deviation in the sub-sequence comprises a failure to follow a prescribed invocation sequence.
35. The product according to claim 26 , wherein the deviation in the sub-sequence is associated with a backdoor left in the code.
36. The product according to claim 26 , wherein the deviation in the sub-sequence comprises an error in business logic that is implemented in the code.