Null-byte injection detection

Patent metadata

Field	Value
Publication number	US-10044752-B1
Application number	US-201514870537-A
Country	US
Kind code	B1
Filing date	Sep 30, 2015
Priority date	Sep 30, 2015
Publication date	Aug 7, 2018
Grant date	Aug 7, 2018

Abstract

A single system for detecting and blocking all cases of null-byte injection in all text data received for a network, before the text reaches potentially vulnerable services in the network. A set of directed graphs is received, each one of the directed graphs corresponding to a singly encoded null-byte that is encoded according to a corresponding character encoding method contained within a set of character encoding methods. The set of directed graphs is used to generate an output finite-state machine that models detection of at least one multiply encoded null-byte that is encoded according to at least one of the character encoding methods contained in the set of character encoding methods. The output finite-state machine is loaded into an attack detection and prevention system that receives input text, and that detects null-bytes, including multiply encoded null-bytes, within the input text.

First claim

What is claimed is:

1. A computer-implemented method of detecting null-byte injection, comprising executing, on at least one processor, the steps of:
generating an output finite-state machine using a set of directed graphs, wherein each one of the directed graphs in the set corresponds to a singly encoded null-byte that is encoded according to a corresponding one of a set of character encoding methods, and wherein the output finite-state machine models computation for detecting at least one multiply encoded null-byte, the multiply encoded null-byte encoded according to at least one of the character encoding methods contained in the set of character encoding methods;
loading the output finite-state machine into an attack detection and prevention system;
receiving, by the attack detection and prevention system, at least one input text; and
detecting, by the attack detection and prevention system in response to the output finite-state machine loaded in the attack detection and prevention system and the input text, an instance of the multiply encoded null-byte within the input text.

2. The method of claim 1 , wherein each one of the directed graphs in the set of directed graphs comprises an input finite-state machine that models computation for detecting a singly encoded null-byte that is encoded according to the corresponding one of the encoding methods in the set of encoding methods.

3. The method of claim 2 , wherein generating the output finite-state machine includes generating a plurality of composite finite-state machines by convolving each of the input finite-state machines by applying at least one of the encoding methods in the set of encoding methods to each of a plurality of transition characters in the input finite-state machine.

4. The method of claim 3 wherein generating the output finite-state machine further includes summing the plurality of composite finite-state machines to generate a non-deterministic finite-state machine.

5. The method of claim 4 , wherein generating the output finite-state machine further includes converting the non-deterministic finite-state machine to a deterministic finite-state machine.

6. The method of claim 5 , wherein generating the output finite-state machine further includes minimizing the deterministic finite-state machine to generate a minimal deterministic finite-state machine.

7. The method of claim 6 , wherein loading the output finite-state machine into the attack detection and prevention system includes generating an output state-transition table representing the output finite-state machine and loading the output state-transition table into the attack detection and prevention system; and
wherein detecting the instance of the multiply encoded null-byte within the input text by the attack detection and prevention system is in response to the output state-transition table loaded into the attack detection and prevention system.

8. The method of claim 7 , further comprising:
generating, by the attack detection and prevention system and responsive to the output state-transition machine and the input text, a clean subset of the input text, wherein the clean subset of the input text contains no null-bytes; and
passing the clean subset of the input text from the attack detection and prevention system to at least one service that is external to the attack detection and prevention system.

9. The method of claim 8 , further comprising:
generating an inverted finite-state machine by inverting the output finite-state machine;
generating a plurality of multiply encoded, test null-byte encodings by, at least in part, randomly traversing the inverted output finite-state machine; and
generating at least one test input text at least in part by storing the plurality of test null-byte encodings into the test input text.

10. The method of claim 1 , wherein each one of the directed graphs in the set of directed graphs comprises an input finite-state machine that models computation for decoding a singly encoded null-byte that is encoded according to at least one of the encoding methods in the set of encoding methods.

11. The method of claim 10 , wherein generating the output finite-state machine includes combining the input finite-state machines into a total finite-state machine that represents all permutations of the encoding methods in the set of encoding methods.

12. The method of claim 11 , wherein the permutations of the encoding methods represented by the total finite-state machine include at least one repetition of one of the encoding methods in the set of encoding methods.

13. A device for protecting vulnerable services from null-byte insertion, comprising:
memory; and
processing circuitry coupled to the memory, the memory storing program code which, when executed by the processing circuitry, causes the processing circuitry to:
generate, in the memory, an output finite-state machine, using a set of directed graphs stored in the memory, wherein each one of the directed graphs in the set corresponds to a singly encoded null-byte that is encoded according to a corresponding one of a set of character encoding methods, and wherein the output finite-state machine models computation for detecting at least one multiply encoded null-byte, the multiply encoded null-byte encoded according to at least one of the character encoding methods contained in the set of character encoding methods;
load the output finite-state machine into an attack detection and prevention system in the program code stored in the memory; and
detect, in response to the output finite-state machine loaded in the attack detection and prevention system and an input text, an instance of the multiply encoded null-byte within the input text.

14. The device of claim 13 , wherein each one of the directed graphs in the set of directed graphs comprises an input finite-state machine that models computation for detecting a singly encoded null-byte that is encoded according to the corresponding one of the encoding methods in the set of encoding methods.

15. The device of claim 14 , wherein the processing circuitry generates the output finite-state machine at least in part by generating a plurality of composite finite-state machines by convolving each of the input finite-state machines by applying at least one of the encoding methods in the set of encoding methods to each of a plurality of transition characters in the input finite-state machine.

16. The device of claim 15 wherein the processing circuitry generates the output finite-state machine at least in part by summing the plurality of composite finite-state machines to generate a non-deterministic finite-state machine.

17. The device of claim 16 , wherein the processing circuitry generates the output finite-state machine further at least in part by converting the non-deterministic finite-state machine to a deterministic finite-state machine.

18. The device of claim 17 , wherein the processing circuitry generates the output finite-state machine at least in part by minimizing the deterministic finite-state machine to generate a minimal deterministic finite-state machine.

19. The device of claim 18 , wherein the processing circuitry loads the output finite-state machine into the attack detection and prevention system at least in part by generating an output state-transition table representing the output finite-state machine and loading the output state-transition table into the attack detection and prevention system; and
wherein the processing circuitry detects the instance of the multiply encod

Assignees

• Emc Corp
• Emc Ip Holding Co Llc

Inventors

• Wittenstein Andreas

Classifications

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• H04L63/1408

  by monitoring network traffic (monitoring network traffic per se H04L43/00) · CPC title

• H04L63/1466 Primary

  Active attacks involving interception, injection, modification, spoofing of data unit addresses, e.g. hijacking, packet injection or TCP sequence number attacks · CPC title

• G06F17/30958

  Physics · mapped topic