Inferring type definitions of user-defined types of variables in application program code

Patent metadata

Field	Value
Publication number	US-12436749-B2
Application number	US-202318194599-A
Country	US
Kind code	B2
Filing date	Mar 31, 2023
Priority date	Mar 31, 2023
Publication date	Oct 7, 2025
Grant date	Oct 7, 2025

Abstract

Type definitions of user-defined types in application program code for which definitions are absent (“unknown types”) are inferred. A static analyzer implements two passes of a fixed-point type inference algorithm. Each pass encompasses a plurality of traversals of the application's control flow to build inferred definitions of unknown types until the inferred definitions are maximally built. To build an inferred definition, based on inferring a variable is an unknown type, the static analyzer infers member variables/functions of the unknown type based on contextual information associated with the variable. Type information of unknown types is propagated along control flow paths. After the first pass terminates, unknown types can be assigned known types based on matching of inferred definitions. Inferred definitions of remaining unknown types are incorporated into the application program code. A second pass of type inferencing and data flow analysis are then performed with the inferred definitions incorporated therein.

First claim

The invention claimed is:

1. A method comprising:
statically analyzing program code of an application over a plurality of iterations, wherein the program code is included in one or more files of the application, and wherein statically analyzing the program code over the plurality of iterations comprises traversing a control flow graph of the application in each of the plurality of iterations to,
determine that an expression or statement identified in the program code of the application comprises a variable that has a user-defined type;
determine if a definition of the user-defined type is known based on the program code of the application; and
based on determining that the definition of the user-defined type is unknown, build an inferred definition of the user-defined type; and

incorporating the built inferred definition of the user-defined type into the one or more files of the application based on determining that the inferred definition satisfies a criterion.

2. The method of claim 1 , wherein traversing the control flow graph to build the inferred definition of the user-defined type comprises,
determining, based on the expression or statement, at least one of an indication of a first function called for the variable and an indication of a first member variable accessed via the variable; and
associating the at least one of the indication of the first function and the indication of the first member variable with an indication of the variable.

3. The method of claim 2 , wherein the user-defined type is a class or struct, and wherein the first function is inferred to be a member function or method of the user-defined type and the first member variable is inferred to be a data member of the user-defined type.

4. The method of claim 2 further comprising:
determining that a subsequent expression or statement identified in the program code of the application comprises the variable; and
determining, based on the subsequent expression or statement, at least one of an indication of a second function called for the variable and an indication of a second member variable accessed via the variable,
wherein traversing the control flow graph to build the inferred definition of the user-defined type further comprises associating the at least one of the indication of the second function and the indication of the second member variable with the indication of the variable.

5. The method of claim 1 , wherein statically analyzing the program code of the application comprises, at each of the plurality of iterations, traversing control flow paths of the application indicated in the control flow graph determined based on the program code.

6. The method of claim 5 further comprising propagating type information included in the inferred definition of the user-defined type along the control flow paths of the application during traversal of the control flow graph, wherein the type information comprises at least one of a parameter type, a return value type, and a member variable type.

7. The method of claim 5 further comprising, based on determining that the definition of the user-defined type is unknown and subsequently determining that type information associated with the user-defined type corresponds to a type with a known definition, recording the type information for the user-defined type without propagating the type information along control flow paths of the application.

8. The method of claim 5 further comprising terminating analysis of the program code based on determining that the inferred definition satisfies the criterion, wherein determining that the inferred definition satisfies the criterion comprises determining that the inferred definition did not change during a last one of the plurality of iterations.

9. The method of claim 1 , wherein the one or more files of the application comprise an intermediate representation of source code of the application, and wherein statically analyzing the program code comprises statically analyzing the intermediate representation of the source code.

10. The method of claim 9 , wherein the source code is PHP code and the intermediate representation of the source code is bytecode.

11. The method of claim 1 further comprising, based on incorporating the inferred definition of the user-defined type into the one or more files of the application, performing data flow analysis of the application.

12. One or more non-transitory machine-readable media having program code stored thereon, the program code comprising instructions to:
statically analyze an application over a plurality of iterations, wherein the instructions to statically analyze the application comprise instructions to traverse a control flow graph of the application in each of the plurality of iterations to,
determine that a type of a first variable identified from program code of the application is a user-defined type;
determine whether a definition of the user-defined type is known based on the program code of the application; and
based on a determination that the definition of the user-defined type is unknown, infer a type definition of the user-defined type to create an inferred definition; and

write the inferred definition into the program code of the application based on a determination that the inferred definition is maximally built.

13. The non-transitory machine-readable media of claim 12 , wherein the instructions to infer the type definition of the user-defined type comprise instructions to infer, over the plurality of iterations over the program code, one or more members associated with the user-defined type based on use of first variable in the program code and add the one or more members to the inferred definition of the user-defined type, wherein the one or more members comprise at least one of a member function and a member variable, and wherein the user-defined type comprises a class or struct.

14. The non-transitory machine-readable media of claim 12 , wherein the instructions to determine that the inferred definition is maximally built comprise instructions to determine that the inferred definition did not change during a last one of the plurality of iterations.

15. The non-transitory machine-readable media of claim 12 , wherein the instructions to statically analyze the application further comprise instructions to,
identify the first variable in an expression or statement encountered along the traversal of the control flow graph, wherein the control flow graph of the application was determined based on the program code of the application.

16. An apparatus comprising:
a processor; and
a machine-readable medium having instructions stored thereon that are executable by the processor to cause the apparatus to,
statically analyze program code of an application over a plurality of iterations, wherein the instructions executable by the processor to cause the apparatus to statically analyze the program code of the application over the plurality of iterations comprise instructions executable by the processor to cause the apparatus to traverse a control flow graph of the application in each of the plurality of iterations to,
based on identification of a first variable at a first of the plurality of iterations, determine that a type of the first variable is user-defined, wherein the program code is included in one or more files of the application;
determine that a definition of the type of the first variable is not known based on the program code of the application; and
build an inferred definition of the type over the first and subsequent ones of the plurality of iterations based on iden

Assignees

• Veracode Inc

Inventors

• Cockerham Beth
• Waddington Trent Craig George

Classifications

• G06F11/3612

  by runtime analysis (performance monitoring G06F11/3466) · CPC title

• G06F8/437 Primary

  Type checking · CPC title