Adapting input to find integer overflows

• US 7,478,428 B1
• Filed: 10/12/2004
• Issued: 01/13/2009
• Est. Priority Date: 10/12/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Thomlinson, Matthew W.
• Primary Examiner(s): SMITHERS, MATTHEW
• Application Number:
  US10/963,296
• Time in Patent Office: 1,554 Days
• Field of Search: 708/498, 708/552
• US Class Current: 726/22
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 21/57 Certifying or maintaining trusted computer platforms, e.g. secure boots or power-downs, version controls, system software checks, secure updates or assessing vulnerabilities

Abstract

Systems and methods are described for use in evaluating an application for security risks related to integer overflow conditions in conjunction with memory allocations. The evaluation includes finding a relationship between data input to the application and memory allocation requests made by the application. Having established the relationship, a memory allocation-requesting module within the application is tested, using input data selected using the relationship.

Claims

1. One or more computer-readable storage media comprising processor-executable instructions for evaluating an application for security risks due to memory allocations, the processor-executable instructions comprising instructions for:

finding a relationship between data input to the application and memory allocation requests made by the application;

calculating input data, using the relationship, wherein the input data is calculated to test for a memory allocation request that results in a math error during operation of the application;

executing a memory allocation-requesting module within the application, using the calculated input data to calculate a memory allocation request; and

determining if the application erroneously calculated the memory allocation request by allowing overrun of a buffer defined in system memory of a computer system.

2. The one or more media as recited in claim 1, wherein finding the relationship between data input to the application and memory allocation requests made by the application comprises instructions for:

executing the memory allocation-requesting module twice to find two points of reference; and

assuming the relationship is linear and includes the two points of reference.

3. The one or more media as recited in claim 1, wherein finding the relationship between data input to the application and memory allocation requests made by the application comprises instructions for:

providing test input data to the memory allocation-requesting module; and

fitting a curve according to the test input data and resulting memory allocation requests.

4. The one or more media as recited in claim 1, wherein finding the relationship between data input to the application and memory allocation requests made by the application comprises instructions for:

inferring the relationship using data from at least two executions of the memory allocation-requesting module.

5. The one or more media as recited in claim 1, wherein finding the relationship between data input to the application and memory allocation requests made by the application comprises instructions for:

deriving a formula describing input data and memory allocation requests; and

solving the formula to obtain an input likely to cause integer overflow in the memory allocation-requesting module.

6. The one or more media as recited in claim 5, wherein the formula is based on a linear relationship between input data and memory allocation requests.

7. The one or more media as recited in claim 5, additionally comprising instructions for:

determining if the math error results from the input likely to cause integer overflow.

8. The one or more media as recited in claim 1, wherein using the relationship comprises additional instructions for:

calculating input data to test for an integer overflow by the memory allocation-requesting module of the application.

9. The one or more media as recited in claim 1, additionally comprising instructions for:

operating tools interfaced to the application, wherein the tools monitor operation of the memory allocation-requesting module.

10. The one or more media as recited in claim 1, additionally comprising instructions for:

determining if the application erroneously calculates size of a memory allocation.

11. The one or more media as recited in claim 1, additionally comprising instructions for:

determining if the math error resulted from an error in the calculation of a memory allocation request.

12. The one or more media as recited in claim 1, additionally comprising instructions for:

performing the evaluation of the application for security risks within a test environment configured to test applications.

13. The one or more media as recited in claim 1, additionally comprising instructions for:

performing the evaluation of the application for security risks by action of an operating system.

14. One or more computer-readable storage media comprising processor-executable instructions for managing memory allocations, the processor-executable instructions comprising instructions for:

establishing a procedure by which memory allocation requests may be predicted based on input to an application;

selecting input data using the procedure, wherein the input data is selected to test for an integer overflow during operation of the application; and

supplying the selected input data to the application;

executing a memory allocation request within the application based on the selected input data supplied to the application; and

determining if the application erroneously calculated the memory allocation request to allow overrun of a buffer defined in system memory of a computer system.

15. The one or more media as recited in claim 14, wherein establishing the procedure comprises instructions for:

providing test input data to the application; and

deriving an equation explaining the test input data and resulting memory allocation requests.

16. The one or more media as recited in claim 14, wherein establishing the procedure comprises instructions for:

deriving a formula describing input data and memory allocation requests; and

solving the formula to obtain an input likely to cause integer overflow within the application.

17. The one or more media as recited in claim 14, wherein establishing the procedure comprises instructions for:

obtaining at least two input data/memory allocation requests points; and

fitting a curve to the at least two input data/memory allocation requests points.

18. The one or more media as recited in claim 17, wherein the curve is a straight line.

19. The one or more media as recited in claim 14, wherein selecting input data using the procedure comprises additional instructions for:

following the procedure to discover input data which will result in a math error.

20. The one or more media as recited in claim 14, wherein selecting input data using the procedure comprises additional instructions for:

following the procedure to discover input data which will result in an integer overflow within the application during calculation of a memory allocation request.

21. The one or more media as recited in claim 14, wherein selecting input data using the procedure comprises additional instructions for:

following the procedure to discover input data which will result in an unexpected memory allocation request.

22. The one or more media as recited in claim 14, wherein supplying the selected input data to the application comprises additional instructions for:

performing an evaluation of the application within a test environment.

23. The one or more media as recited in claim 14, wherein supplying the selected input data to the application comprises additional instructions for:

performing an evaluation of the application by action of an operating system.

24. A test apparatus to test memory allocation requests made by an application, the test apparatus defined in one or more computer-readable storage media and comprising:

tools interfaced to the application to monitor memory allocation requests made by a memory allocation-requesting module within the application;

a data analyzer for finding a relationship between input data and a size of the memory allocation requests, wherein the relationship is configured to allow prediction of memory allocation requests for given input data, and the data analyzer is configured for;

executing the memory allocation-requesting module two or more times to find two or more points of reference wherein each point of reference is associated with a memory allocation request; and

fitting a curve to the two or more points of reference;

a data generator for generating data to be input to the application, wherein the data is generated according to the relationship and selected in a manner to test for an integer overflow during operation of the application, and wherein the data is input to the application for use by the memory allocation-requesting module within the application; and

an allocation request evaluator configured to determine if operation of the application using the memory allocation request would result in integer overflow and to determine if a size of the memory allocation request was erroneous.

25. The test apparatus as recited in claim 24:

wherein the allocation request evaluator determines if a math error resulted in the integer overflow.

26. The test apparatus as recited in claim 24, wherein the data analyzer is additionally configured for:

assuming the relationship is linear and includes two points of reference.

27. The test apparatus as recited in claim 24, wherein the data analyzer is additionally configured for:

deriving a formula describing input data and memory allocation requests; and

solving the formula to obtain an input likely to cause integer overflow in the memory allocation-requesting module.

28. The test apparatus as recited in claim 27, wherein the test apparatus is configured to operate within a test application or an operating system environment.

29. A test apparatus to test memory allocation requests made by an application, the test apparatus defined in one or more computer-readable storage media and comprising:

means for predicting a memory allocation request by examination of results of at least two inputs to an application resulting in memory allocation requests, wherein the means for predicting comprises;

means for deriving a formula relating input data and memory allocation requests; and

means for solving the formula to obtain an input likely to cause integer overflow within the application; and

means for selecting input data according to the means for predicting a memory allocation request, wherein the selected input data tests the application'"'"'s ability to correctly process data intended to result in integer overflow.

30. The test apparatus of claim 29, wherein the means for predicting additionally comprises:

means for fitting a curve to the at least two inputs.

31. The test apparatus of claim 30, additionally comprising:

means for integrating the test apparatus into an operating system, to allow memory allocation requests made by the application to be tested during operation of the application.

32. A method for evaluating an application for security risks, the method comprising:

finding a relationship between input data and memory allocation requests;

executing a memory allocation-requesting module within the application to obtain a memory allocation request, wherein input data which was provided to the application was selected by using the relationship and was calculated to test for math errors within the application; and

evaluating the memory allocation request for evidence of math errors;

wherein the evaluation of the application for security risks is performed within an operating system environment.

33. The method of claim 32, wherein finding a relationship comprises:

executing the memory allocation-requesting module within the application at least twice; and

inferring the relationship using data from the at least two executions of the memory allocation-requesting module.

34. The method of claim 32, wherein finding a relationship comprises:

deriving a formula describing input data and memory allocation requests; and

solving the formula to obtain an input likely to cause integer overflow in the memory allocation-requesting module.

35. The method of claim 32, wherein the evaluation of the application for security risks is performed within a test application configured for testing the application.