FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003
COMPLETE SPECIFICATION
(See Section 10 and Rule 13)
Title of invention:
A SYSTEM AND METHOD TO PROVIDE GROUPING OF WARNINGS GENERATED DURING STATIC ANALYSIS
Applicant
Tata Consultancy Services Limited A Company Incorporated in India under The Companies Act, 1956
Having address:
Nirmal Building, 9th Floor,
Nariman Point, Mumbai 400021,
Maharashtra, India
The following specification particularly describes the invention and the manner in which it is to be performed.

TECHNICAL FIELD
[001] The present subject matter described herein, in general, relates to warnings
generated during static analysis, and more particularly to provide grouping of warnings generated during static analysis.
BACKGROUND
[002] The use of static analysis in validation and verification of safety critical
software applications is of prime importance. However, static analysis of the software applications results in many falsely reported warnings commonly referred to as false positives. All the warnings generated by the static analysis require a manual review in order to check if the warnings are safe or unsafe. The manual review of high number of warnings generated is time consuming and cost involved for the manual review is very high. The high number of warnings is a result of use of abstractions, conscious design decisions such as excluding array handling, performing analysis intra-procedurally. Also, the inability of static analysis to determine actual values that a variable can take at run-time leads to high number of warnings generated.
[003] Currently, a user analyzing or reviewing the warnings generated by static
analysis has to review each of the warnings individually. There exist many techniques such as Abstract Interpretation, Difference Bound Matrix and Model-checking which strive to make the static analysis more precise. However, the above mentioned techniques still generate a number of warnings, and fail to reduce the manual review efforts required to analyze the warnings to the extent it could possibly be reduced.
[004] Moreover, other existing techniques provide grouping of warnings based on
severity or priority of the warnings but these techniques fail to reduce the review efforts of the warnings. There exists no technique which ensures reduction in review efforts based on identification of redundancy in the reviewing of the warnings.
SUMMARY
[005] This summary is provided to introduce aspects related to systems and methods
to provide grouping of one or more warnings generated during static analysis and the aspects

are further described below in the detailed description. This summary is not intended to identify essential features of the claimed subject matter nor is it intended for use in determining or limiting the scope of the claimed subject matter.
[006] In one implementation, a system to provide grouping of one or more warnings
generated during static analysis is disclosed. The system comprises a processor and a memory coupled to the processor, wherein the processor is capable of executing a plurality of modules stored in the memory. The plurality of modules comprises an analyzing module configured to analyze an application code in order to generate one or more warnings and an identification module configured to identify the similar warnings so generated, based on similarity of the warnings, wherein the similarity is based on one or more constraints. The plurality of modules further comprises a grouping module configured to form one or more groups of the warnings based on a similarity, wherein each group comprises the warnings identified as similar. Further, the plurality of modules also comprises a computation module, configured to compute a representative warning from each group of the warnings such that the warnings other than the representative warning in the group of the warnings follow a review judgment of the representative warning. The review of the representative warning ensures the review of the warnings in the group other than the representative warning.
[007] In one implementation, a method to provide grouping of one or more warnings
generated during static analysis is disclosed. The method comprises analyzing an application code in order to generate one or more warnings and identifying the warnings so generated, based on similarity of the warnings, wherein the similarity is based on one or more constraints. The method further comprises forming one or more groups of the warnings based on similarity, wherein each group comprises the warnings identified as similar and computing a representative warning from each group of the warnings. The computing of the representative warning is in such a way that the warnings other than the representative warning in the group of the warnings, follow a review judgment of the representative warning and a review of the representative warning ensures the review of the warnings other than the representative warning in the group. In the method, the analyzing of an application code, the identifying the warnings so generated, based on similarity of the warnings , the forming one or more groups of the warnings, and the computing of the representative warning are performed by a processor.

[008] In one implementation, a computer program product having embodied thereon
a computer program for grouping of warnings generated by static analysis is disclosed. The computer program product comprises a program code for analyzing an application code in order to generate one or more warnings and a program code for identifying the warnings so generated, based on a similarity of the warnings, wherein the similarity is based on one or more constraints, The computer program product further comprises a program code for forming one or more groups of the warnings based on the similarity, wherein each group comprises the warnings identified as similar. The computer program product further comprises a program code for computing a representative warning from each group of the warnings such that the warnings other than the representative warning, in the group of the warnings follow a review judgment of the representative warning. The review of the representative warning ensures a review of the warning other than the representative warnings in the group.
[009] In one implementation, a system to provide grouping of one or more warnings
generated during static analysis is disclosed. The system comprises a processor and a memory coupled to the processor, wherein the processor is capable of executing a plurality of modules stored in the memory. The plurality of modules comprises an analyzing module configured to analyze an application code in order to generate one or more warnings and an identification module configured to identify the warnings so generated, such that the expression of interests (EOIs) of the warnings identified have same operators appearing in same order and EOI variables, the EOI variables related by their position in the EOIs, get values from same modification points. The plurality of modules further comprises a grouping module configured to form groups of the warnings identified, wherein a systematic review of one of the warning in the group formed ensures the review of the warnings other than the warning reviewed in the group formed when the reviewed warning is found safe by considering values provided by modification points of the EOI variables.
[0010] In one implementation, a method to provide grouping of one or more warnings
generated during static analysis is disclosed. The method comprises analyzing an application code in order to generate one or more warnings and identifying the warnings so generated, such that the expression of interests (EOIs) of the warnings identified have same operators appearing in same order and EOI variables, the EOI variables related by their position in the

EOIs get values from same modification points. The method further comprises forming groups of the warnings identified, wherein a systematic review of one of the warning in the group formed ensures the review of the warnings other than the warning reviewed in the group formed when the reviewed warning is found safe by considering values provided by modification points of the EOI variables. In the method, the analyzing of an application code, the identifying the warnings to be grouped and the forming of one or more groups of the warnings are performed by a processor.
[0011] In one implementation, a computer program product having embodied thereon
a computer program to provide grouping of one or more warnings generated during static analysis is disclosed. The computer program product comprises a program code for analyzing an application code in order to generate one or more warnings and a program code for identifying the warnings so generated, such that the expression of interests (EOIs) of the warnings identified have same operators appearing in same order and EOI variables, the EOI variables related by their position in the EOIs, get values from same modification points. The computer program product further comprises a program code for forming groups of the warnings identified, wherein a systematic review of one of the warning in the group formed ensures the review of the warnings other than the warning reviewed in the group formed when the reviewed warning is found safe by considering values provided by modification points of the EOI variables.
BRIEF DESCRIPTION OF THE DRAWINGS
[0012] The detailed description is described with reference to the accompanying
figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The same numbers are used throughout the drawings to refer like features and components.
[0013] Figure 1 illustrates a network implementation of a system to provide grouping
of one or more warnings generated during static analysis, in accordance with an embodiment of the present subject matter.
[0014] Figure 2 illustrates the system to provide grouping of one or more warnings
generated during static analysis, in accordance with an embodiment of the present subject matter.

[0015] Figure 3 illustrates a method for computation of a set of leader warnings using
Must Reaching Expressions (MREs), in accordance with an embodiment of the present subject matter.
[0016] Figure 4 illustrates a method for refinement of a set of leader warnings using
Must Live Expressions (MLEs), in accordance with an embodiment of the present subject matter.
[0017] Figure 5 illustrates a method to provide grouping of one or more similar
warnings generated during static analysis, in accordance with an embodiment of the present subject matter.
[0018] Figure 6 illustrates a method to provide modification points based grouping of
one or more warnings generated during static analysis, in accordance with an alternate embodiment of the present subject matter.
DETAILED DESCRIPTION
[0019] Systems and methods to provide grouping of one or more warnings generated
during static analysis are described. Initially, one or more warnings are generated on analysis of an application code. The warnings generated are further classified or grouped based on a similarity in the warnings. In order to group the warnings on basis of similarity, various constraints need to be fulfilled, wherein the constraints include structural and semantical similarity of expressions of interest (EOIs) of the warnings, the warnings are reachable from one another in forward or backward flow, variables from the EOIs of the warnings are not modified between the program points of the warnings, and at least one warning for which values of the EOJ comprises values from the EOIs of other warnings.
[0020] Further, a representative warning is computed from each group of the
warnings such that review of the representative warning ensures the review of the warnings other than the representative warning in each group. If the representative warning is found to be safe, the warnings other than the representative warning are also safe and need not be reviewed. However, if the representative warning is found unsafe, the warnings other than the representative warning in each group have to be manually reviewed individually.

[0021] In another embodiment, the warnings generated are grouped if the expression
of interests (EOIs) of the warnings has same operators appearing in same order and the EOT variables related by their position in the EOIs get values from same modification points. One of the warnings in the group formed is reviewed manually considering the values provided by the modification points of the EOI variables, and if it is found safe, the other warnings from the same group are also safe and need not be reviewed. In the other case, when the warning cannot be found safe then each of the warnings in the group formed need to be reviewed individually.
[0022] While aspects of described system and method to provide grouping of one or
more warnings generated during static analysis may be implemented in any number of different computing systems, environments, and/or configurations, the embodiments are described in the context of the following exemp/ary system,
[0023J Referring now to Figure 1, a network implementation 100 of a system 102 to
provide grouping of one or more warnings generated during static analysis is illustrated, in accordance with an embodiment of the present subject matter. In one embodiment, the system 102 provides for grouping of one or more warnings generated during static analysis. In one embodiment, the system 102 analyzes an application code in order to generate warnings. The warnings generated are identified based on similarity of the warnings, wherein the similarity is based on one or more constraints. The warnings identified are grouped based on similarity, wherein each group comprises the warnings identified as similar. Further, the system 102 computes a representative warning from each group of the warnings, such that the warnings other than the representative warning in the group of the warnings follow a review judgment of the representative warning, and a review of the representative warning ensures the review of the warnings other than the representative warning in the group. In an embodiment of the invention the terms similar warnings and warnings based on similarity are interchangeable.
[0024] In another embodiment of the system 102, amongst the warnings generated,
some warnings are identified such that the expression of interests (EOIs) of the warnings identified have same operators appearing in same order and the EOI variables related by their position in the EOIs get values from same modification points. Further, the system 102 forms groups of the warnings identified wherein review of one of the warning in the group formed

ensures the review of the warnings other than the warning reviewed in the group formed, when the selected warning is reviewed considering the values provided to the EOI variables by their modification points. If the reviewed warning is found safe in this manner, all the grouped warnings are also safe and need to be reviewed individually. In the other case when reviewed warning cannot be found safe, then all the warnings in its group have to be manually reviewed individually.
[0025J Although the present subject matter is explained considering that the system
102 is implemented on a server, it may be understood that the system 102 may also be implemented in a variety of computing systems, such as a laptop computer, a desktop computer, a notebook, a workstation, a mainframe computer, a server, a network server, and the like. It will be understood that the system 102 may be accessed by multiple users through one or more user devices 104-1, 104-2... 104-M, collectively referred to as user 104 hereinafter, or applications residing on the user devices 104. Examples of the user devices 104 may include, but are not limited to, a portable computer, a personal digital assistant, a handheld device, and a workstation. The user devices 104 are communicatively coupled to the system 102 through a network 106.
[0026] In one implementation, the network 106 may be a wireless network, a wired
network or a combination thereof. The network 106 can be implemented as one of the different types of networks, such as intranet, local area network (LAN), wide area network (WAN), the internet, and the like. The network 106 may either be a dedicated network or a shared network, The shared network represents an association of the different types of networks that use a variety of protocols, for example, Hypertext Transfer Protocol (HTTP), Transmission Control Protocol/Internet Protocol (TCP/IP), Wireless Application Protocol (WAP), and the like, to communicate with one another. Further the network 106 may include a variety of network devices including routers, bridges, servers, computing devices, storage devices, and the like.
[0027] Referring now to Figure 2, the system 102 is illustrated in accordance with an
embodiment of the present subject matter. In one embodiment, the system 102 may include at least one processor 202, an input/output (I/O) interface 204, and a memory 206. The at least one processor 202 may be implemented as one or more microprocessors, microcomputers,

microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the at least one processor 202 is configured to fetch and execute computer-readable instructions stored in the memory 206.
[0028] The I/O interface 204 may include a variety of software and hardware
interfaces, for example, a web interface, a graphical user interface, and the like. The I/O interface 204 may allow the system 102 to interact with a user directly or through the client devices 104. Further, the I/O interface 204 may enable the system 102 to communicate with other computing devices, such as web servers and external data servers (not shown). The I/O interface 204 can facilitate multiple communications within a wide variety of networks and protocol types, including wired networks, for example, LAN, cable, etc., and wireless networks, such as WLAN, cellular, or satellite. The I/O interface 204 may include one or more ports for connecting a number of devices to one another or to another server.
[0029] The memory 206 may include any computer-readable medium known in the art
including, for example, volatile memory, such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. The memory 206 may include modules 208 and data 210.
[0030] The modules 208 include routines, programs, objects, components, data
structures, etc., which perform particular tasks or implement particular abstract data types. In one implementation, the modules 208 may include an analyzing module 212, an identification module 214, a grouping module 216, a computation module 218 and other modules 220. The other modules 220 may include programs or coded instructions that supplement applications and functions of the system 102.
[0031] The data 210, amongst other things, serves as a repository for storing data
processed, received, and generated by one or more of the modules. The data 210 may also include a system database 222, and other data 224. The other data 224 may include data generated as a result of the execution of one or more modules in the other module 220.
[0032] In one implementation, at first, a user may use the client device 104 to access
the system 102 via the I/O interface 204. The user may register them using the VO interface

204 in order to use the system 102. The working of the system 102 may be explained in detail in Figures 3 and 4 explained below. The system 102 may be used to provide grouping of one or more warnings generated during static analysis. In order to provide grouping of one or more warnings generated during static analysis, the system 102, at first, analyzes an application code in order to generate one or more warnings. Specifically, in the present implementation, the application code is analyzed by the analyzing module 212.
[0033] Further, the identification module 214 is configured to identify the warnings so
generated, based on similarity of the warnings, wherein the similarity is based on one or more constraints. The constraints include structurally and semantically similar expressions of interest (EOIs) of the warnings, the warnings are reachable from one another in forward or backward flow, variables from the EOIs of the warnings are not modified between the program points of the warnings, and at least a warning for which values of the EOI comprises values from the EOIs of other warnings.
[0034] The constraint of being semantically similar is included since structurally
similar EOIs may evaluate to different values. For example, consider two EOIs as 'v + a' (where 'a' is a local variable) and 'v + a' (where 'a' is a global variable). The above mentioned EOIs will not be treated as similar because they evaluate to different values and hence the warnings generated with the above mentioned EOIs cannot be considered as similar. Also, by way of a further example, the warnings generated with their EOIs 'v + 1' and ' 1 + v' cannot be treated as similar since these EOIs have different structures even though they evaluate to same values. In order to identify the warnings as similar all the constraints need to be satisfied.
[0035] By way of a specific example, consider a program mentioned below.
#defineSIZE10
int rColors[SIZE], gColors[SIZE], bColors[S!ZE];
1. void func(int r, int g, int b)
2- {
3. // Values of 'n' and 'factor' are not known
4. ...

5. factor = getDivFactorf);
6. if((r/factor>rvall )&&...)
7. rColors[n] = r; 8.

9. if((g/factor > gvall) && ...)
10. gColors[n] = g; 11.

12. if((b/factor>bvall )&&...)
13. bColors[n] = b; 14.

15. gradient = getG rad i ent( rColors[n],gColors[n],bColors[n]);
16. ...
17. }
[0036] In the above mentioned program, there exists 3 Zero Division (ZD) and 6
Array Index Out of Bound (AlOB) warnings since, respectively, the values of denominator 'factor' and array index 'n' are unknown statically. Notations ZDn and AIOBn are used to denote the ZD and AIOB points at a line 'n' respectively. In case more than one such points exist at a single line, the points in the program are differentiated with the position of the points seen from left to right and is presented as a prefixed superscript. For example, first and second AIOB points from line 15 shall be denoted as 'AIOB15 and 2AIOB15 respectively. In the above program all ZD warnings are similar in themselves because the ZD warnings have same denominator expression 'factor' and value of the denominator expression 'factor' is not modified in between ZD6 and ZD12 points. In the above example, only the denominator expressions may be considered as the EOls because the denominator expression is sufficient for reviewing any given ZD warning point by checking if it may lead to evaluation of the value '0'.

[0037] Further, the grouping module 216 is configured to form one or more groups of
the warnings based on a similarity, wherein each group comprises the warnings identified as similar. In the above mentioned program, the ZD warnings may be grouped together as they are similar. The system 102 implements grouping of warnings generated by static analysis, for single code verification property at a time.
[0038] Further, the computation module 218 is configured to compute a representative
warning from each group of the similar warnings, such that the warnings other than the representative warning in the group of the warnings follow a review judgment of the representative warning. During a review of the representative warning, finding the representative warning as safe ensures the review of the warnings other than the representative warnings in the group. In the other case, when representative warning is found unsafe, then all the warnings from its group need to be reviewed individually. The computation module 218 further performs computation of Must Reaching Expressions (MREs) to compute the warning from each group in forward flow of information computation, and the computation of Must Live Expressions to compute the warning from each group in backward flow of information computation. The representative warning may also be denoted as a Leader Warning (LW) and the warnings other than the representative warning in each group may be denoted as Follower Warnings (FW). In the above mentioned program code, from the group of the ZD warnings, ZD6 may be safely chosen as the LW because other warnings are observed to follow its review judgment.
[0039] Any warning from the group of similar warnings formed may be selected as
LW only if its EOI is definitely reaching (Must Reaching Expression - MRE) or definitely live (Must Live Expression - MLE) to other warning points from same group. That is for any warning ' W' if there exists-
- one or more MRE/MLE from some other warning(s) identified as similar to W, then W must be a FW.
- no MRE/MLE from some other warning identified as similar to W, then strictly W must be a LW.
[0040] Still referring to the program mentioned above, the ZD6 warning may be
chosen as the LW because the denominator expression of ZD6 is definitely reaching at later

ZD points, i.e. all paths to ZD9 & ZD12 also includes ZD6 and denominator variable 'factor' is not modified in between. Thus, the values evaluated by denominators of ZD9 & ZD12 (FWs) are contained in the values evaluated by the denominator of ZD6. In case, the ZDg warning is found to be safe upon manual review, then the FWs are guaranteed to be safe, and if the ZD6 warning is found as unsafe then FWs may be unsafe. In later case the FWs may not necessarily be observed as unsafe since there might exist some added checks which may prevent the FWs from being unsafe.
[0041J Generally, the probability of finding the warning generated as defect/unsafe is
experienced to be very low. With the given review judgment relationship between LW & FWs and the probability of finding the warning generated as a defect, it may be observed that there exists only the leader warnings (LWs) for manual review. Thus, the proposed grouping of similar warnings avoids the user from paying attention to the FWs during review, and leads to a reduction in review efforts.
[0042] Still referring to the program mentioned above, 6 AIOB points in the program
are warnings since their index values cannot be known statically. These AIOB warnings may also be observed as similar since indexes of these warnings are same and are not modified in between line 7 and 16. Given two AIOB warnings are similar only if their related array indexes and array sizes are same. Only the array index is considered as the EOI in context of verification of the AIOB warnings, and the array being indexed is excluded from the EOI since it is only required to get the bound (array size) for its index check. The reason behind shifting focus from arrays accessed to array-sizes is to identify maximum possible number of the warnings as similar. Had the array been treated as a part of an EOI then the warnings,
1AIOB 15 and2 AIOB 15 may not be identified as similar.
[0043] The AIOB warnings identified as similar may be grouped together to view it
as a single warning. With respect to the AIOB warnings grouped together, AIOB7 may not be computed as the LW because the index of AIOB7 is not definitely reaching to other AIOB points and with this selection the required guarantee of review judgment relationship may not be given. Similarly the AIOB9 and AIOB12 warnings may not be considered as the LW. However the 1AlOB15 or any other warning from same line may be taken as LW of the group since this selection guarantees the required review judgment relationship between LW &

FWs. The values evaluated by index of AIOB15 contain the values evaluated by the indexes of other AIOB warnings. This be ensured by observing that the index (n) of 1AIOBIS is definitely live at earlier AIOB points, i.e. any path passing through the FWs computed also passes through the 1AIOB15 (LW) and the index 'n' is not modified in between. The review of the warning 1AIOB15 ensures the review of the other warnings in the group formed.
[0044] The above mentioned program only considers EOIs (factor for ZD, n for
AIOB) with single variables but the warnings identified as similar may be grouped even if their EOIs are complex expressions such as (varl+var2-var3) or (arrl[0] + arr[i]). The grouping of warnings identified as similar at an application level reduces the number of generated warnings, avoids multiple verification cycles during a process of review and reduces manual review efforts.
[0045] The computation module 218 computes MREs and MLEs for the computation
of the Leader Warnings. The Must Reaching Expression (MRE) is defined as follows. An expression 'e' from a program point PE is a MRE at a program point P, if every path coming to P also comes through PE and no path segment between PE and P contains a l-value occurrence of any of the r-value(s) of 'e' That is, PE precedes P and the values evaluated by 'e' at PE contains the values of 'e' if it is evaluated at P. Few examples of MREs from the program mentioned above are:
The denominator of ZD6is a MRE at ZD6 and ZD12 as each path to ZD9 and ZD12 is coming through ZD6 and the variable 'factor' is not modified in
between.
The denominator of ZD9 is a MRE at ZDj2 however cannot be a MRE at ZD6 as ZD9 does not precede the ZD6.
The index n of AIOB7 (or AIOB]0, AIOB13) is not a MRE at any other AIOB points since there exists a path without their inclusion.
[0046] Further, the MREs may be efficiently computed by using Data Flow Analysis
(DFA). DFA gathers flow-information as a value or a set of values at various program points in an application. Function summary based approach is used for DFA solving in order to compute the required MREs in a context and flow sensitive manner. The below presented data

flow formulization for MREs computation depicts forward flow analysis and targets single verification functionality at a time. For instance, the required MREs for grouping ZD and AIOB warnings will have to be computed separately. Unlike available expressions, the EOIs considered are actual expressions as they are in IR representation (abstract syntax tree built for the input source program). The below data flow equations are shown for a node 'n' in a CFG (Control Flow Graph).

usedVars(e) = r-values from expression e
modified Vars(n) = 1-values from program statement n
[0047] Some points for above formulization are as below-
Boundary value = 0;
Initialization/Top = set of all EOIs from all warnings since meet operation is intersection
The partial order is Reflexive, Transitive and Anti-symmetric.
The meet operation is Commutative, Associative and Idempotent

[0048] The equation for 'Outn' is deviated from standard DFA equation as the kill
component is computed from Genn+Inn, This change is incorporated as the MREs may get generated and killed at the same program points like'W = arr[val]". The index 'val' is not expected to be flowing out as a MRE after this program point.
[0049] In order to compute the MREs more efficiently the following points should be
considered:
Consideration is given to program points with analysis warnings only. The POIs identified as safe or unsafe are to be ignored from MRE computations.
Ignore the EOIs including function calls and volatile variables from MREs computations, because with their presence the required guarantee in the review judgment of the so computed LW and FWs cannot be given.
The information of modified variables should be computed as a separate"May-Kill/Modified" data flow problem.
When arrays are included in computing killed information, conservative approach should be taken. The expressions like (arr[0] + b) should not be reached after "arr[i] = n" program point when value of i' is unknown.
[0050] The Must Live Expression (MLE) may be defined as follows. An expression
'e' from program point PE is a MLE at a program point P, if every path passing through P also passes through PE and no path segment between P and PE contains a l-value occurrence of any of the r-value(s) of 'e' That is, P precedes PE and the values evaluated by 'e' at PE contains the values of 'e' if it is evaluated at P. Few examples of MLEs from the program mentioned above are:
The index of n of1AIOB15 is a MLE at AIOB7 as all paths from AIOB7 also pass through 1AIOBis and their index n is not modified in between. Similarly the indices from warnings at line 15 will be MLEs at AIOB7, AIOB10 and AIOBi3.
The index of A]OBi3 is not a MLE at AIOB7 and AIOB10 warnings, since there exists a path which passes through AIOB7 and AIOB10 but does not pass through AIOB13.

[0051] Further, the MLEs may be efficiently computed by using Data Flow Analysis
(DFA). The formulization for MLEs computation is same as for MREs computations with only change in equation of Inn. This change is incorporated to consider the backward flow of information computation and is shown below.

The considerations given for efficient MREs computation shall also remain same for MLEs computation.
[0052] The computation module 218 further implements optimization in DFA in order
to avoid unnecessary MRE/MLE identifications. The formulated DFA shows that the MRE/MLE gets generated at each warning point. During DFA solving, if a warning point observes MRE/MLE flowing in from some other similar warning then the MRE/MLE for current warning need not be generated. Generation of such MRE/MLE is avoided for efficiency purpose, because such warning is definitely going to be a FW and this computation will not add any value. This will not only reduce the data that is computed in DFA but also the LWs and FWs computation becomes faster as explained below.
[0053] At any warning W, if there does not exist a MRE/MLE from any other similar
warning point then W is a LW. Initially, each warning generated may be viewed as a LW having its own group without any FW. In order to achieve maximum benefit out of the grouping of the warnings, the number of LWs should be minimum. The number of LWs can be reduced by associating these initial LWs with some other LW, i.e., by converting them to FWs. After this type of grouping, every warning must belong to single group and cannot be a LW and a FW at the same time. Further, a group of similar warnings so formed, strictly contains exactly one LW and any number of FWs including zero.
[0054] Henceforth in this document, we use notation LWo to denote a set of LWs
computed after grouping of similar warnings. In one implementation, the computation module 218 implements a graph based approach to compute required LWo. Let each generated

warning be represented as a tree having only one node (denoting the warning) so that. initially, the number of trees will be equal to the number of warnings those are generated. At a warning point W, the MREs/MLEs are computed and for each MRE/MLE that is generated from warning WL, a directed edge is added from vertex related WL to vertex corresponding to W. Such edge needs to be added only if below both points hold true:
if the EOIs (and other required information such as array sizes) of W and WL warnings are similar.
there is no incoming edge to the vertex corresponding to WL,
[0055] The first constraint is required to associate the warnings identified as similar
only, and second constraint is required to avoid the redundant edges additions as both the warnings (W & WL) are guaranteed to be FWs. When WL has an incoming edge then it cannot be a LW. Once the edges addition is complete as per MRE and MLE results the resultant forest depicts the LWs and their associated FWs. Here, each tree in the forest will be a group of warnings identified as similar, where the vertex without incoming edge will be a LW of the group and the vertices which all can be traversed from the LW will be the FWs of the group. Thus, the number of groups formed will be the number of trees in the forest. At first, for efficiency purpose, the LWs (LW0) are computed using MREs and then the MLEs are computed for these LWs only. Later using the computed MLEs, the earlier obtained LWo as per MREs is refined further to get the lesser LWs.
[0056] By way of a specific example, consider the program mentioned above. The
vertex in a forest is denoted corresponding to any warning with the same notation used to denote the warning. Initially all these vertices will not have any incoming or outgoing edges. The directed edges are added as described using the results of MREs for ZD and AIOB and the forest obtained is shown in Figure 3. Following are the observations obtained from the forest shown in figure 3.
• The index of ZD6 is MRE to ZD9 and ZD\2, hence there are respective edges
from ZD6 to ZD9 and ZDi2.

• Even though the index of ZD9 is index to MRE to ZD12, the respective edge is
not added as the vertex for ZD9 has an incoming edge (as per second constraint of edge addition).
[0057] The forest in figure 3 represents the LW0 as expected for ZD with ZD6 as a
single LW and ZD9 & ZD12 as the FWs. The LW0 for AlOB is not as per expectation since it represents 4 warnings as LWs for review instead of one. This is because, the MREs are not always sufficient to compute the expected LWo, and it requires refinement using MLEs. The MLEs are computed only for the LWs which are obtained using MREs and the edges are added as per their computation results. The refined LWo obtained using MLEs is shown in Figure 4 where it presents single AIOB warning as a LW and is as required.
[0058] In another embodiment of the invention, the system 102 provides grouping of
one or more warnings generated during static analysis using modification points based grouping (MPG). At first, the analyzing module 212 is configured to analyze the application code in order to generate one or more warnings. Further, the identification module 214 is configured to identify the warnings so generated, such that the expression of interests (EOIs) of the warnings identified have same operators appearing in same order and EOI variables, the EOI variables related by their position in the EOIs, get values from same modification points. The grouping module 216 is further configured to form groups of the warnings identified, wherein a systematic review of one of the warning in the group formed ensures the review of the warnings other than the warning reviewed in the group formed when the reviewed warning is found safe by considering values provided by modification points of the EOI variables. Further, the grouping module 214 associates and reports the modification points against each MPG group, wherein the associated modification points are the modification points of the EOI variables from the grouped warnings.
[0059] The grouping module 216 further performs computation of Reaching
Definitions to form groups of the warnings identified. If a warning from the group formed is found to be safe on the user's review considering the EOI variable values from their associated modification points, then the other warnings from the same group need not be reviewed. In other case, if a selected warning from the group after user's review is not found safe, then each warning from the group needs to be reviewed individually.

[0060] By way of a specific example, consider the program mentioned below.
intarr[10];
void func(const int* baseAddr, const int* currPtr) {// val gets assignment of values from 0 to 9.
int val = currPtr - baseAddr;
switch (switch Var)
{
case 1: fund (val); break;
case 2: func2(val); break; case 3: func3(val); break; default; break;
} } void fund (int pi)
{
if(...)arr[pl] = ...;
else if (...) arr[pl] = ...;
}
void func2(int p2)
{
if(...) arr[p2] =...;
else if (...) arr[p2] = ...;
}
void func3(int p3)

{
if(...) arr[p3] =...; else if (...) arr[p3] = ...;
}
[0061] The program above depicts an example where the value (0 to 9) of val variable
is computed using pointer arithmetic and is passed to multiple functions for array index usage. Most static analysis tools report these AIOB points as warnings, because the values for var cannot be determined statically. The review of each warning will require finding values taken by their respective index variable (pi, p2, p3) and hence will require manual traversing from warning point to definition point of val (the one with pointer arithmetic). The user may then decide if warning can be safe or unsafe based on these found values. Thus reviewing of all such warnings collectively takes considerable efforts.
[0062] In such a scenario the identification module 214 identifies the warnings whose
EOI variables get values from same modification (or definition) points and the grouping module 216 groups the warnings identified so that review efforts can be minimized. Along with such modification points other parameters from review perspective should also match in order to treat them in a single group. When the EOIs are complex expressions involving multiple variables then they must observe same order of operators and the variables related by their positions in these EOIs must find same modification points.
[0063] For example -
• the array-sizes should also match for grouping AIOB warnings using MPG.
• the warnings with their EOIs as v+], v, and v-1 cannot be grouped using MPG since EOIs differ in structure.
• the warnings with a+b+c & a+b+c as EOIs can be grouped by using MPG only if the each variable (a, b, c) gets values from same modification points.
[0064] Let Vw be the set of values evaluated by EOI at any MPG grouped warning
point. During review, user mostly refers to the values of EOI variables being assigned to at their modification points and evaluates EOI under review. Let VM be set of values for same

EOI when evaluated considering its variables' values obtained from modification points. Now intuitively, for any MPG grouped warning it's obvious that Vw S VM. If user observes that any MPG grouped warning is safe considering VM then safety of all of the grouped warnings is definitely ensured. In this scenario the review of other MPG grouped warnings individually is redundant and can be avoided. In other scenario when warning cannot be identified as safe using VM, then all MPG grouped warnings must be reviewed individually by the user.
[0065] The AIOB warnings in the above program may be grouped together as per
MPG. since their array sizes are equal and indexes get values from same modification point. During review user may find the required values for any index variable directly looking at the reported modification point of val. Here user observes that the values of variable val are within array bound [0..9] and hence the index will be within bound. This way, a selected warning from a MPG group of warnings will be found safe and reviewing of other warnings will get skipped.
[0066] In one implementation of the invention, the system 102 is configured to
perform the grouping of the warnings based on MPG only for the LWs computed by the computation module 218. The FWs from each group may be ignored as the review judgment of the FWs is same as that of LW. The grouping of LWs based on the MPG results in higher efficiency and further reduces the efforts required for manual review of the warnings.
[0067] Referring now to Figure 5 and 6, methods 500 and 600 to provide grouping of
one or more warnings generated during static analysis is shown, in accordance with an embodiment of the present subject matter. The methods 500 and 600 may be described in the general context of computer executable instructions. Generally, computer executable instructions can include routines, programs, objects, components, data structures, procedures, modules, functions, etc., that perform particular functions or implement particular abstract data types. The methods 500 and 600 may also be practiced in a distributed computing environment where functions are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, computer executable instructions may be located in both local and remote computer storage media, including memory storage devices.

[0068] The order in which the methods 500 and 600 is described is not intended to be
construed as a limitation, and any number of the described method blocks can be combined in any order to implement the methods 500 and 600 or alternate methods. Additionally, individual blocks may be deleted from the methods 500 and 600 without departing from the spirit and scope of the subject matter described herein. Furthermore, the method can be implemented in any suitable hardware, software, firmware, or combination thereof. However, for ease of explanation, in the embodiments described below, the methods 500 and 600 may be considered to be implemented in the above described system 102.
[0069] At block 502, an application code is analyzed. In one implementation, the
application code is analyzed in order to generate one or more warnings by the analyzing module 212.
[0070] At block 504, the warnings so generated are identified based on similarity of
the warnings. In one implementation, the warnings so generated are identified based on similarity of the warnings, wherein the similarity is based on one or more constraints by the identification module 214.
[0071] At block 506, one or more groups of the warnings based on similarity are
formed. In one implementation, the one or more groups of the warnings based on similarity are formed, wherein each group comprises the warnings identified as similar by the grouping module 216.
[0072] At block 508, a representative warning from each group of the warnings is
computed. In one implementation, a representative warning from each group of the warnings is computed by the computation module 218, such that the warnings other than the representative warning, in the group of the warnings follow a review judgment of the representative warning, and a review of the representative warning ensures the review of the warnings other than the representative warning in the group.
[0073] Referring now to Figure 6, a method 600 providing grouping of one or more
warnings generated during static analysis is shown, in accordance with an embodiment of the present subject matter.

[0074] At block 602, an application code is analyzed. In one implementation, the
application code is analyzed in order to generate one or more warnings by the analyzing module 212.
[0075] At block 604, the warnings so generated are identified such that the expression
of interests (EOIs) of the warnings identified have same operators appearing in same order and the EOI variables, the EOI variables related by their position in the EO1s, get values from same modification points. In one implementation, the warnings so generated are identified by the identification module 214.
[0076] At block 606, one or more groups of the warnings are formed wherein review
of one of the warning in the group formed ensures the review of the warnings other than the warning reviewed in the group formed when the reviewed warning is found safe by considering values provided by modification points of the EOI variables. In one implementation, the one or more groups of the warnings are formed by the grouping module 216.
[0077] Although implementations for methods and systems to provide grouping of
one or more warnings generated during static analysis have been described in language specific to structural features and/or methods, it is to be understood that the appended claims are not necessarily limited to the specific features or methods described. Rather, the specific features and methods are disclosed as examples of implementations for to provide grouping of one or more warnings generated during static analysis.

WE CLAIM:
1. A method to provide grouping of one or more warnings generated during static
analysis, the method comprising:
analyzing an application code in order to generate one or more warnings;
identifying the warnings so generated, based on similarity of the warnings, wherein the similarity is based on one or more constraints;
forming one or more groups of the warnings based on similarity, wherein each group comprises the warnings identified as similar; and
computing a representative warning from each group of the warnings, such that the warnings other than the representative warning in the group of the warnings follow a review judgment of the representative warning, and a review of the representative warning ensures the review of the warnings other than the representative warning in the group;
wherein the analyzing, the identifying, the forming, and the computing are performed by a processor.
2. The method of claim 1, wherein the constraints include structurally and semantically similar expressions of interest (EOIs) of the warnings, the warnings are reachable from one another in forward or backward flow, variables from the EOIs of the warnings are not modified between the program points of the warnings, and at least a warning for which values of the EOI comprises values from the EOIs of other warnings.
3. The method of claim I, wherein the computing further comprises computation of Must Reaching Expressions (MREs) to compute the warnings based on similarity, from each group and the representative warning in forward flow of information computation, and the computation of Must Live Expressions (MLEs) to compute the warnings based on similarity from each group and the representative warning in backward flow of information computation.
4. The method of claim 1, wherein the method is performed for single code verification property.

5. The method of claim 1. wherein, if the review of the representative warning is found to be safe, then the warnings other than the representative warning in the group formed are also safe and need not be reviewed, and if the review of the representative warning is found to be unsafe then the warnings other than the representative warning in the group formed need to be reviewed individually.
6. A system to provide grouping of one or more warnings generated during static analysis, the system comprising:
a processor; and
a memory coupled to the processor, wherein the processor is capable of executing a plurality of modules stored in the memory, and wherein the plurality of modules comprising:
an analyzing module configured to analyze an application code in order to generate one or more warnings;
an identification module configured to identify the warnings so generated, based on similarity of the warnings, wherein the similarity is based on one or more constraints;
a grouping module configured to form one or more groups of the warnings based on a similarity, wherein each group comprises the warnings identified as similar; and
a computation module configured to compute a representative warning from each group of the warnings, such that the warnings other than the representative warning in the group of the warnings follow a review judgment of the representative warning , and a review of the representative warning ensures the review of the warnings other than the representative warnings in the group.
7. The system of claim 6, wherein the constraints include structurally and semantically
similar expressions of interest (EOIs) of the warnings, the warnings are reachable from one
another in forward or backward flow, variables from the EOIs of the warnings are not
modified between the program points of the warnings and at least a warning for which values
of the EOI comprises values from the EOIs of other warnings.

8. The system of claim 6, wherein the computation module further performs computation of Must Reaching Expressions (MREs) to compute the warnings based on similarity, from each group and the representative warning in forward flow of information computation, and the computation of Must Live Expressions (MLEs) to compute the warnings based on similarity from each group and the representative warning in backward flow of information computation.
9. The system of claim 6, wherein system is implemented for single code verification property.
10. The system of claim 6, wherein, if the review of the representative warning is found to be safe, then the warnings other than the representative warning in the group formed are also safe and need not be reviewed, and if the review of the representative warning is found to be unsafe then the warnings other than the representative warning in the group formed need to be reviewed individually.
11. A computer program product having embodied thereon a computer program to provide grouping of one or more warnings generated during static analysis, the computer program product comprising:
a program code for analyzing an application code in order to generate one or more warnings;
a program code for identifying the warnings so generated, based on a similarity of the warnings, wherein the similarity is based on one or more constraints;
a program code for forming one or more groups of the warnings based on the similarity, wherein each group comprises the warnings identified as similar; and
a program code for computing a representative warning from each group of the warnings, such that the warnings other than the representative warning in the group of the warnings follow a review judgment of the representative warning , and a review of the representative warning ensures a review of the warning other than the representative warnings in the group.
12. A method to provide grouping of one or more warnings generated during static
analysis, the method comprising:

analyzing an application code in order to generate one or more warnings;
identifying the warnings so generated, such that the expression of interest (EOls) of the warnings identified have same operators appearing in same order and EOI variables, the EOI variables related by their position in the EOls get values from same modification points; and
forming groups of the warnings identified, wherein review of at least one of the warning in the groups formed ensures the review of the warnings other than the warning reviewed in the groups formed when the reviewed warning is found safe by considering values provided by modification points of the EOI variables; wherein the analyzing, the identifying and the forming are performed by a processor.
13. The method of claim 12, wherein the forming groups further comprises computation of Reaching Definitions to form groups of the warnings identified.
14. The method of claim 12, wherein, if the review of any one of the warning in the group formed, by considering the values of the EOI provided by their modification points, is found to be safe then the warnings other than the warning reviewed in the group formed are also safe and need not be reviewed, and if the review of any one of the warning in the group formed is not found safe then all the warnings in the group formed need to be reviewed individually.
15. A system to provide grouping of one or more warnings generated during static analysis, the system comprising:
a processor; and
a memory coupled to the processor, wherein the processor is capable of executing a
plurality of modules stored in the memory, and wherein the plurality of modules
comprising:
an analyzing module configured to analyze an application code in order to generate one or more warnings;
an identification module configured to identify the warnings so generated, such that the expressions of interest of the warnings identified have same operators

appearing in same order and EOI variables, the EOl variables related by their position in the EOIs, get values from same modification points; and
a grouping module configured to form groups of the warnings identified, wherein review of at least one of the warning in the group formed ensures the review of the warnings other than the warning reviewed in the group formed, when the reviewed warning is found safe by considering values provided by modification points of the EOI variables.
16. The system of claim 15, wherein the grouping module further performs computation of Reaching Definitions to form groups of the warnings identified.
17. The system of claim 15, wherein, if the review of any one of the warning in the group formed, by considering the values of the EOI provided by their modification points, is found to be safe then the warnings other than the warning reviewed in the group formed are also safe and need not be reviewed, and if the review of any one of the warning in the group formed is not found safe then all the warnings in the group formed need to be reviewed individually.
18. A computer program product having embodied thereon a computer program to provide grouping of one or more warnings generated during static analysis, the computer program product comprising:
a program code for analyzing an application code in order to generate one or more warnings;
a program code for identifying the warnings so generated, such that the expressions of interest of the warnings identified have same operators appearing in same order and EOI variables, the EOI variables related by their position in the EOIs get values from same modification points; and
a program code for forming groups of the warnings identified , wherein review of at least one of the warning in the group formed ensures the review of the warnings other than the warning reviewed in the group formed, when the reviewed warning is

found safe by considering values provided by modification points of the EOI variables.