Intrusion detection using taint accumulation

• US 9,443,085 B2
• Filed: 08/26/2011
• Issued: 09/13/2016
• Est. Priority Date: 07/19/2011
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Elwha LLC (Intellectual Ventures LLC)
• Inventors: Tegreene, Clarence T., Gerrity, Daniel A., Glew, Andrew F.
• Primary Examiner(s): Lagor, Alexander
• Application Number:
  US13/199,368
• Publication Number:
  US 20130024937A1
• Time in Patent Office: 1,845 Days
• Field of Search: 726 22- 25
• US Class Current: 1/1
• CPC Class Codes: G06F 21/577 Assessing vulnerabilities and evaluating computer system security
• CPC Class Codes: H04L 63/14 for detecting or protecting against malicious traffic

Abstract

A method operable in a computing device adapted for handling security risk can use taint accumulation to detect intrusion. The method can comprise receiving a plurality of taint indicators indicative of potential security risk from a plurality of distinct sources at distinct times, and accumulating the plurality of taint indicators independently using a corresponding plurality of distinct accumulation functions. Security risk can be assessed according to a risk assessment function that is cumulative of the plurality of taint indicators.

Claims

1. A method operable in one or more processing devices for handling security risk comprising:

receiving at least one of an incoming instruction or data from one or more sources; and

executing one or more instructions on the one or more processing devices to perform one or more operations including at least;

detecting one or more potential taint indicators indicative of activities or events occurring during execution associated with the at least one of the incoming instruction or data received from the one or more sources, the activities or events occurring during the execution of the instructions including at least one of a null pointer reference, an integer overflow, a buffer overflow, one or more attempts to access a memory element according to a predetermined restriction, or one or more attempts to access processor element according to a predetermined restriction;

assigning at least one of the one or more potential taint indicators to at least one taint vector including vector fields operated upon by the one or more instructions, the vector fields including at least one taint indicator field associated with the one or more potential taint indicators, at least one source field associated with the one or more sources, and at least one accumulator field corresponding to the at least one taint indicator field and the at least one source field;

accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources; and

assessing security risk based at least partially on the accumulation in the at least one accumulator field of the at least one taint vector according to a risk assessment function that is cumulative of the one or more taints and assesses whether at least one of the one or more cumulative taints is indicative of potential security risk for the one or more potential taint indicators and the associated one or more sources, wherein at least one of the receiving, the detecting, the assigning, the accumulating, or the assessing is at least partially implemented using the one or more processing devices.

2. A method operable in one or more processing devices for handling security risk comprising:

detecting one or more potential taint indicators indicative of activities or events occurring during execution of instructions associated with the at least one of an incoming instructions or data received from the one or more sources, the activities or events occurring during execution including at least one of a null pointer reference, an integer overflow, a buffer overflow, one or more attempts to access a memory element according to a predetermined restriction, or one or more attempts to access processor element according to a predetermined restriction;

specifying three or more bit fields of at least one taint vector including three or more vector fields operated upon by the one or more instructions, the three or more vector fields including at least one taint indicator field associated with the one or more potential taint indicators, at least one source field associated with the one or more sources, and at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field and the at least one source field; and

executing the one or more instructions on the one or more processing devices including at least;

accumulating one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources; and

responding to at least one taint indicative of potential security risk to one or more resources based at least partially on the accumulation in the at least one accumulator field of the at least one taint vector of the one or more taints according to the one or more taint accumulation functions.

3. A computing system comprising:

at least one interface configured at least partially in hardware to receive at least one of an incoming instruction or data from one or more sources; and

one or more processors configured to execute one or more instructions on one or more processing devices to perform one or more operations including at least;

detecting one or more potential taint indicators indicative of activities or events occurring during execution associated with the at least one of the incoming instruction or data received from the one or more sources, the activities or events occurring during the execution of the instructions including at least one of a null pointer reference, an integer overflow, a buffer overflow, one or more attempts to access a memory element according to a predetermined restriction, or one or more attempts to access processor element according to a predetermined restriction;

assigning at least one of the one or more potential taint indicators to at least one taint vector including vector fields operated upon by the one or more instructions, the vector fields including at least one taint indicator field associated with the one or more potential taint indicators, at least one source field associated with the one or more sources, and at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field and the at least one source field;

accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources; and

assessing security risk based at least partially on the accumulation in the at least one accumulator field of the at least one taint vector according to a risk assessment function that is cumulative of the one or more taints and assesses whether at least one of the one or more cumulative taints is indicative of potential security risk to one or more resources for the one or more potential taint indicators and the associated one or more sources.

4. The computing system according to claim 3 wherein the one or more resources include:

at least one of networks, systems, processors, central processing units (CPUs), graphics hardware, network controllers, memory, memory management, hardware, software systems, virtual entities, power, operating cycles, libraries, operating systems, pools of resources, or combinations of resources.

5. The computing system according to claim 3 wherein the at least one interface configured at least partially in hardware to receive at least one of the incoming instruction or data from one or more sources comprises:

at least one network interface configured to receive at least one of the incoming instruction or data forwarded from a network source.

6. The computing system according to claim 3 wherein the detecting one or more potential taint indicators indicative of activities or events occurring during execution of instructions associated with the at least one of the incoming instruction or data received from the one or more sources comprises:

receiving a signal from processor hardware indicating at least one of a null pointer reference, a buffer overrun, a buffer overflow, an integer overflow, or a fault.

7. The computing system according to claim 3 wherein the detecting one or more potential taint indicators indicative of activities or events occurring during execution of instructions associated with the at least one of the incoming instruction or data received from the one or more sources comprises:

detecting execution of at least one instruction indicative of at least one of a virus attempt to call home or an attacker attempting to compromise a web browser.

8. The computing system according to claim 3 wherein the detecting one or more potential taint indicators indicative of activities or events occurring during execution of instructions associated with the at least one of the incoming instruction or data received from the one or more sources comprises:

receiving a signal from at least one trusted platform module (TPM) interface indicating at least one of repeated attempts to access a key, an attempt to access a secured part of a processor, an attempt to access a secured resource, an event originating in a region that raises suspicion, a taint indicated by power law analysis, or a taint indicated by a race function.

9. The computing system according to claim 3 wherein the detecting one or more potential taint indicators indicative of activities or events occurring during execution of instructions associated with the at least one of the incoming instruction or data received from the one or more sources comprises:

receiving a signal from at least one hardware interface indicating at least one attempt to access a secure part of the one or more processing devices.

10. The computing system according to claim 3 wherein the detecting one or more potential taint indicators indicative of activities or events occurring during execution of instructions associated with the at least one of the incoming instruction or data received from the one or more sources comprises:

receiving a signal from at least one operating system interface indicating at least one system call associated with reading data from one or more web pages.

11. The computing system according to claim 3 wherein the detecting one or more potential taint indicators indicative of activities or events occurring during execution of instructions associated with the at least one of the incoming instruction or data received from the one or more sources comprises:

receiving a signal from at least one operating system interface indicating that the information from the one or more web pages originated from a web browser at an identified web site.

12. The computing system according to claim 3 wherein the at least one taint vector including two or more vector fields operated upon by one or more instructions comprises:

at least one taint vector including at least one of one or more event taint indicator fields indicative of one or more risk events, one or more activity taint indicator fields indicative of one or more risk activities, or one or more condition taint indicator fields indicative of one or more risk conditions associated with the one or more sources in the at least one source field.

13. The computing system according to claim 3 wherein the at least one taint vector including vector fields operated upon by one or more instructions comprises:

at least one composite taint vector including two or more resource fields associated with respective two or more resources, the two or more resource fields including at least one source field associated with the at least one indicator of the at least one of the one or more sources and at least one taint indicator field associated with the one or more taint indicators.

14. The computing system according to claim 3 wherein the accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources comprises:

accumulating, in response to the receipt of the data from one or more sources, one or more taints according to a taint accumulation function on at least one of a per-location, per-data, or overall basis to quantify whether data from a predetermined source or entity is indicative of potential security risk.

15. The computing system according to claim 3 wherein the accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources comprises:

accumulating, in response to the receipt of the data from one or more sources, one or more taints according to a taint accumulation function configured to compare accumulated taints to a predetermined threshold.

16. The computing system according to claim 3 wherein the accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources comprises:

accumulating, in response to the receipt of the data from one or more sources, one or more taints according to a taint accumulation function configured to accumulate first taints from a first source to determine first taints indicative of potential security risk and accumulate second taints from a second source to determine second taints indicative of potential security risk, and respond to the first taints indicative of potential security risk and the second taints indicative of potential security risk at distinctive times and with distinctive responses.

17. The computing system according to claim 3 wherein the accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources comprises:

accumulating, in response to the receipt of the data from one or more sources, one or more taints according to a taint accumulation function configured to accumulate first taints in association with first data from a first source to determine first taints indicative of potential security risk based at least in part on the first data and the first source and accumulate second taints in association with second data from a second source to determine second taints indicative of potential security risk based at least in part on the second data and the second source.

18. The computing system according to claim 3 wherein the accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources comprises:

accumulating, in response to the receipt of the data from one or more sources, one or more taints according to a taint accumulation function configured to accumulate taints in association with data from a source to determine taints indicative of potential security risk based at least in part on the data and the source.

19. The computing system according to claim 3 wherein the accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources comprises:

accumulating, in response to the receipt of the data from one or more sources, one or more taints according to a taint accumulation function configured to accumulate taints including at least one of counting a number of taints, counting a number of taints per memory unit, counting a number of instructions tainted, counting a number of tainted instructions, counting a number of instructions written as a result of at least one taint, counting a number of loads or stores associated with at least one taint, counting a number of memory accesses, counting a number of outputs, counting a number of calls, counting a number of returns, counting a number of branches, counting a number of integer overflows, or counting a number of network input/output events.

20. The computing system according to claim 3 wherein the accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources comprises:

accumulating, in response to the receipt of the data from one or more sources, one or more taints according to a taint accumulation function configured to accumulate taints in association with at least one composite taint vector including two or more resource fields associated with respective two or more resources, the taint accumulation function configured to monitor and track taints for multiple of at least one of resources, conditions, events, or activities concurrently.

21. The computing system according to claim 3 wherein the accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources comprises:

accumulating, in response to the receipt of the data from one or more sources, one or more taints according to a taint accumulation function configured to accumulate taints over time and offset the accumulated taints with a predetermined decay function.

22. The computing system according to claim 3 wherein the accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources comprises:

accumulating, in response to the receipt of the data from one or more sources, one or more taints according to a taint accumulation function configured to accumulate taints over time and offset the accumulated taints with a predetermined decay function, the predetermined decay function including at least one of (1) incrementing a taint accumulation, (2) decrementing a taint accumulation, (3) adding a predetermined number to a taint accumulation, (4) subtracting a predetermined number to a taint accumulation, (5) copying at least one taint accumulation to memory periodically to maintain a legacy condition while continuously incrementing and decrementing to enable restoration of the legacy condition in response to an invalid or error condition, (6) imposing a decay that is a race of decay versus accumulation, or (7) shifting a taint accumulation a predetermined number of bits.

23. The computing system according to claim 3 wherein the accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources comprises:

accumulating, in response to the receipt of the data from one or more sources, one or more taints according to a taint accumulation function configured to accumulate taints over time and offset the accumulated taints with a predetermined decay function configured to decay the accumulated taints periodically with a period that varies according to a sensitivity meter wherein a rate of decay is based at least in part on environment of a system.

24. The computing system according to claim 3 wherein the accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources comprises:

accumulating, in response to the receipt of the data from one or more sources, one or more taints according to a taint accumulation function configured to accumulate taints over time and offset the accumulated taints with a predetermined decay function configured to update the accumulated taints according to a decay predetermined in association with at least one of a decay time interval, a decay instruction count, a decay time period, a decay processor frequency, or a decay processor cycle count.

25. The computing system according to claim 3 wherein the accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources comprises:

accumulating, in response to the receipt of the data from one or more sources, one or more taints according to a taint accumulation function configured to accumulate taints over time and offset the accumulated taints with a predetermined decay function configured to decay the accumulated taints periodically with a period that varies according to a sensitivity meter responsive to an instruction configured to operate in conjunction with an operating system to read a register indicating a protection level and set a decay rate based at least in part on the protection level.

26. The computing system according to claim 3 wherein the accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources comprises:

accumulating, in response to the receipt of the data from one or more sources, one or more taints according to a taint accumulation function configured to operate in combination with at least one taint adjustment vector to dynamically adjust the at least one taint vector periodically.

27. The computing system according to claim 3 wherein the accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources comprises:

accumulating, in response to the receipt of the data from one or more sources, one or more taints according to a taint accumulation function configured to operate in combination with at least one taint adjustment vector responsive to an instruction configured to operate in conjunction with an operating system to control a set of taint adjustment parameter vectors configured to adjust the at least one taint vector.

28. The computing system according to claim 3 wherein the accumulating, in response to the receipt of the data from one or more sources, one or more taints in the at least one accumulator field of the at least one taint vector corresponding to the at least one taint indicator field according to one or more taint accumulation functions based at least in part on the one or more potential taint indicators and the associated one or more sources comprises:

accumulating, in response to the receipt of the data from one or more sources, one or more taints according to a taint accumulation function configured for dynamic modification by application of at least one taint bias vector.

29. The computing system according to claim 3 wherein the assessing security risk based at least partially on the accumulation in the at least one accumulator field of the at least one taint vector according to a risk assessment function that is cumulative of the one or more taints and assesses whether at least one of the one or more cumulative taints is indicative of potential security risk to one or more resources for the one or more potential taint indicators and the associated one or more sources comprises:

assessing security risk of at least one of a plurality of taints indicative of potential security risk including setting an indicator of a possibility of potential security risk.

30. The computing system according to claim 3 wherein the assessing security risk based at least partially on the accumulation in the at least one accumulator field of the at least one taint vector according to a risk assessment function that is cumulative of the one or more taints and assesses whether at least one of the one or more cumulative taints is indicative of potential security risk to one or more resources for the one or more potential taint indicators and the associated one or more sources comprises:

assessing security risk of at least one of a plurality of taints indicative of potential security risk including assessing a response of trapping to software.

31. The computing system according to claim 3 wherein the assessing security risk based at least partially on the accumulation in the at least one accumulator field of the at least one taint vector according to a risk assessment function that is cumulative of the one or more taints and assesses whether at least one of the one or more cumulative taints is indicative of potential security risk to one or more resources for the one or more potential taint indicators and the associated one or more sources comprises:

assessing security risk of at least one of a plurality of taints indicative of potential security risk including assessing a response of blocking input/output operations.

32. The computing system according to claim 3 wherein the assessing security risk based at least partially on the accumulation in the at least one accumulator field of the at least one taint vector according to a risk assessment function that is cumulative of the one or more taints and assesses whether at least one of the one or more cumulative taints is indicative of potential security risk to one or more resources for the one or more potential taint indicators and the associated one or more sources comprises:

assessing security risk of at least one of a plurality of taints indicative of potential security risk determined by at least one thresholding operation including at least one of (1) a number of the plurality of taints indicative of potential security risk greater than a predetermined threshold, (2) any of the plurality of taints indicative of potential security risk greater than a predetermined threshold, (3) all of the plurality of taints indicative of potential security risk greater than a predetermined threshold, (4) a sum of the plurality of taints indicative of potential security risk greater than a predetermined threshold, or (5) a sum of the plurality of taints indicative of potential security risk greater than a predetermined intermediate value.

33. The computing system according to claim 3 wherein the assessing security risk based at least partially on the accumulation in the at least one accumulator field of the at least one taint vector according to a risk assessment function that is cumulative of the one or more taints and assesses whether at least one of the one or more cumulative taints is indicative of potential security risk to one or more resources for the one or more potential taint indicators and the associated one or more sources comprises:

assessing security risk of at least one of a plurality of taints indicative of potential security risk including at least determining a response based at least in part on a tolerance set based at least in part on one or more of the at least one indicator of the at least one of the one or more sources and the one or more taint indicators.

34. The computing system according to claim 3 wherein the assessing security risk based at least partially on the accumulation in the at least one accumulator field of the at least one taint vector according to a risk assessment function that is cumulative of the one or more taints and assesses whether at least one of the one or more cumulative taints is indicative of potential security risk to one or more resources for the one or more potential taint indicators and the associated one or more sources comprises:

assessing security risk of at least one of a plurality of taints indicative of potential security risk, wherein assessing a response includes at least one of a trap, an exception, a notification, or an alarm.

35. The computing system according to claim 3 wherein the assessing security risk based at least partially on the accumulation in the at least one accumulator field of the at least one taint vector according to a risk assessment function that is cumulative of the one or more taints and assesses whether at least one of the one or more cumulative taints is indicative of potential security risk to one or more resources for the one or more potential taint indicators and the associated one or more sources comprises:

assessing security risk of at least one of a plurality of taints indicative of potential security risk based at least in part on a hint instruction configured to operate in conjunction with an operating system to indicate at least one taint condition that is not indicative of potential security risk.

36. The computing system according to claim 3 wherein the assessing security risk based at least partially on the accumulation in the at least one accumulator field of the at least one taint vector according to a risk assessment function that is cumulative of the one or more taints and assesses whether at least one of the one or more cumulative taints is indicative of potential security risk to one or more resources for the one or more potential taint indicators and the associated one or more sources comprises:

assessing security risk of at least one of a plurality of taints indicative of potential security risk including incrementing an ignore problems taint vector based at least in part on a hint instruction configured to operate in conjunction with an operating system.

37. The computing system according to claim 3 wherein the assessing security risk based at least partially on the accumulation in the at least one accumulator field of the at least one taint vector according to a risk assessment function that is cumulative of the one or more taints and assesses whether at least one of the one or more cumulative taints is indicative of potential security risk to one or more resources for the one or more potential taint indicators and the associated one or more sources comprises:

associating at least one of a plurality of taints indicative of potential security risk with a complex system including multiple resources assigned in a single taint vector.

38. The computing system according to claim 3 wherein the assessing security risk based at least partially on the accumulation in the at least one accumulator field of the at least one taint vector according to a risk assessment function that is cumulative of the one or more taints and assesses whether at least one of the one or more cumulative taints is indicative of potential security risk to one or more resources for the one or more potential taint indicators and the associated one or more sources comprises:

associating at least one of a plurality of taints indicative of potential security risk with two or more registers individually assigned in corresponding two or more taint vectors.

39. The computing system according to claim 3 wherein the assigning at least one of the one or more potential taint indicators to at least one taint vector including vector fields operated upon by the one or more instructions comprises:

assigning at least one of the one or more potential taint indicators to at least one taint vector including vector fields operated upon by the one or more instructions, the vector fields including at least one resource field associated with at least one resource affected by the execution of the instructions, the at least one resource field indicating an assignment of memory including at least one of;

(1) assigning a taint vector per memory byte, (2) assigning a taint vector per entire memory, (3) assigning a taint vector by memory page, or (4) assigning a taint vector by memory type.

40. The computing system according to claim 3 wherein the assigning at least one of the one or more potential taint indicators to at least one taint vector including vector fields operated upon by the one or more instructions comprises:

assigning at least one of the one or more potential taint indicators to at least one taint vector including vector fields operated upon by the one or more instructions, the vector fields including at least one memory taint hash table indicating a level of tainting per memory block.

41. The computing system according to claim 3 wherein the assigning at least one of the one or more potential taint indicators to at least one taint vector including vector fields operated upon by the one or more instructions comprises:

assigning at least one of the one or more potential taint indicators to at least one taint vector including vector fields operated upon by the one or more instructions, the vector fields including at least one taint hash vector wherein a memory portion receives a specified hash of an address and the specified hash is configured to compress the address.

42. The computing system according to claim 3 wherein the assigning at least one of the one or more potential taint indicators to at least one taint vector including vector fields operated upon by the one or more instructions comprises:

assigning at least one of the one or more potential taint indicators to at least one taint vector including vector fields operated upon by the one or more instructions, the vector fields including at least one resource field associated with at least one resource affected by the execution of the instructions, wherein assignment of the at least one resource field is based at least in part on a predictive hint instruction configured to operate in conjunction with an operating system to hint a prediction of usage for the one or more resources.