Systems and methods for detecting transactional message sequences that are obscured in multicast communications

• US 10,091,077 B1
• Filed: 06/27/2016
• Issued: 10/02/2018
• Est. Priority Date: 06/27/2016
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Pukish, Michael, Qiu, Minjie, Somasundaram, Shankar
• Primary Examiner(s): Fan, Hua
• Application Number:
  US15/194,337
• Time in Patent Office: 827 Days
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04W 4/44 for communication between vehicles and infrastructures, e.g. vehicle-to-cloud [V2C] or vehicle-to-home [V2H]

Abstract

The disclosed computer-implemented method for detecting transactional message sequences that are obscured in multicast communications may include (i) collecting a sequence of messages that were distributed on a communication channel and that include an obscured cyclic sequence of request-response messages that are interleaved in the sequence of messages, (ii) constructing a sequence graph from the sequence of messages by (a) adding, for each unique message identifier in the sequence of messages, a node to represent the unique message identifier and (b) adding, for each unique sequence transition in the sequence of messages from an immediately-preceding message to an immediately-succeeding message, an edge to connect the nodes that represent the identifiers of the unique sequence transition'"'"'s immediately-preceding and immediately-succeeding messages, (iii) traversing the sequence graph to discover the obscured cyclic sequence of request-response messages, and (iv) performing a security action. Various other methods, systems, and computer-readable media are also disclosed.

Claims

1. A computer-implemented method for detecting transactional message sequences that are obscured in multicast communications, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising:

collecting a sequence of messages that were distributed on a communication channel, wherein;

the sequence of messages comprises at least one obscured cyclic sequence of request-response messages that;

were exchanged by at least two components; and

are interleaved in the sequence of messages; and

each message in the sequence of messages comprises an identifier that indicates a meaning of the message;

constructing a sequence graph from the sequence of messages by;

adding, for each unique message identifier in the sequence of messages, a node to the sequence graph to represent the unique message identifier; and

adding, for each unique sequence transition in the sequence of messages from an immediately-preceding message to an immediately-succeeding message, an edge to the sequence graph to;

represent the unique sequence transition; and

connect the node that represents the identifier of the unique sequence transition'"'"'s immediately-preceding message to the node that represents the identifier of the unique sequence transition'"'"'s immediately-succeeding message;

traversing the sequence graph to discover the obscured cyclic sequence of request-response messages; and

performing a security action using a representation of the obscured cyclic sequence of request-response messages.

2. The computer-implemented method of claim 1, wherein the communication channel comprises an automobile network.

3. The computer-implemented method of claim 1, wherein collecting the sequence of messages comprises:

logging the identifier of each message in the sequence of messages;

logging an order in which each message in the sequence of messages was observed; and

logging a time at which each message in the sequence of messages was observed.

4. The computer-implemented method of claim 1, wherein constructing the sequence graph further comprises:

creating, for each node in the sequence graph, a dictionary of sequence transitions; and

adding, for each sequence transition in the sequence of messages whose succeeding message'"'"'s identifier is equal to the identifier that is represented by the node, an entry to the dictionary to represent the sequence transition, wherein;

the entry comprises;

a preceding-message identifier that is equal to the identifier of the sequence transition'"'"'s preceding message;

a transition order that is equal to the order of the sequence transition in the sequence of messages; and

a time interval equal to the amount of time between observances of the sequence transition'"'"'s preceding message and the sequence transition'"'"'s succeeding message; and

the edge that connects the nodes that represent the identifiers of the sequence transition'"'"'s preceding and succeeding messages comprises a directed edge that is incident from the node that represents the identifier of the sequence transition'"'"'s preceding message and incident to the node that represents the identifier of the sequence transition'"'"'s succeeding message.

5. The computer-implemented method of claim 4, wherein traversing the sequence graph comprises:

visiting a node in the sequence graph;

identifying a potential cyclic sequence transition by identifying a group of entries in the node'"'"'s dictionary whose preceding-message identifiers match; and

determining that the potential cyclic sequence transition is likely a cyclic sequence transition in the obscured cyclic sequence of request-response messages by determining that a variation in the time intervals of the group'"'"'s entries is less than a predetermined threshold.

6. The computer-implemented method of claim 5, wherein traversing the sequence graph further comprises promoting each entry in the node'"'"'s dictionary along a directed edge incident from the node and incident to an adjacent node by:

identifying the transition order of the entry;

locating an adjacent entry in the adjacent node'"'"'s dictionary whose transition order is one more than the transition order of the entry; and

adding an additional entry to the adjacent node'"'"'s dictionary that comprises;

a preceding-message identifier that is equal to the entry'"'"'s preceding-message identifier;

a transition order that is equal to the transition order of the entry; and

a time interval that is equal to a sum of the time interval of the entry and the time interval of the adjacent entry.

7. The computer-implemented method of claim 6, wherein traversing the sequence graph further comprises:

determining that the identifier that is represented by the node is an identifier of a proceeding message of another cyclic sequence transition in the obscured cyclic sequence of request-response messages; and

removing, from the dictionary of each node in the sequence graph, all entries whose preceding-message identifier matches the identifier that is represented by the node.

8. The computer-implemented method of claim 6, wherein traversing the sequence graph further comprises adding an additional directed edge to the sequence graph that is incident from the node that represents the entry'"'"'s previous-message identifier and incident to the adjacent node.

9. The computer-implemented method of claim 6, wherein traversing the sequence graph comprises:

removing, from the sequence graph, each directed edge that is incident with the node; and

removing the node from the sequence graph.

10. The computer-implemented method of claim 5, further comprising:

creating a state machine to represent the obscured cyclic sequence of request-response messages;

adding, to the state machine, a first state to represent the identifier of the potential cyclic sequence transition'"'"'s preceding message;

adding, to the state machine, a second state to represent the identifier of the potential cyclic sequence transition'"'"'s succeeding message; and

adding, to the state machine, a transition from the first state to the second state.

11. The computer-implemented method of claim 10, wherein performing the security action comprises:

monitoring an additional sequence of messages on the communication channel;

detecting an anomaly in the additional sequence of messages by determining that the additional sequence violates the transition from the first state to the second state; and

performing the security action in response to detecting the anomaly.

12. The computer-implemented method of claim 11, wherein:

detecting the anomaly comprises determining that the anomaly indicates that the potential cyclic sequence transition is not a cyclic sequence transition in the obscured cyclic sequence of request-response messages; and

performing the security action comprises updating the state machine.

13. The computer-implemented method of claim 11, wherein:

detecting the anomaly comprises determining that the anomaly indicates that a component has malfunctioned; and

the security action is performed to remediate the malfunctioning of the component.

14. The computer-implemented method of claim 11, wherein:

detecting the anomaly comprises determining that the anomaly indicates a malicious attack on the communication channel; and

the security action is performed to remediate the malicious attack.

15. The computer-implemented method of claim 10, wherein:

adding the transition from the first state to the second state comprises adding a guard condition to the transition that requires the transition to occur within a predetermined amount of time, wherein the predetermined amount of time is based at least in part on the time intervals of the group'"'"'s entries; and

performing the security action comprises;

monitoring an additional sequence of messages on the communication channel;

detecting an anomaly in the additional sequence of messages by determining that the additional sequence violates the guard condition; and

performing the security action in response to detecting the anomaly.

16. A system for detecting transactional message sequences that are obscured in multicast communications, the system comprising:

a collecting module, stored in memory, that collects a sequence of messages that were distributed on a communication channel, wherein;

the sequence of messages comprises at least one obscured cyclic sequence of request-response messages that;

were exchanged by at least two components; and

are interleaved in the sequence of messages; and

each message in the sequence of messages comprises an identifier that indicates a meaning of the message;

a constructing module, stored in memory, that constructs a sequence graph from the sequence of messages by;

adding, for each unique message identifier in the sequence of messages, a node to the sequence graph to represent the unique message identifier; and

adding, for each unique sequence transition in the sequence of messages from an immediately-preceding message to an immediately-succeeding message, an edge to the sequence graph to;

represent the unique sequence transition; and

connect the node that represents the identifier of the unique sequence transition'"'"'s immediately-preceding message to the node that represents the identifier of the unique sequence transition'"'"'s immediately-succeeding message;

a traversing module, stored in memory, that traverses the sequence graph to discover the obscured cyclic sequence of request-response messages;

a security module, stored in memory, that performs a security action using a representation of the obscured cyclic sequence of request-response messages; and

at least one processor that executes the collecting module, the constructing module, the traversing module, and the security module.

17. The system of claim 16, wherein the communication channel comprises an automobile network.

18. The system of claim 16, wherein the collecting module collects the sequence of messages by:

logging the identifier of each message in the sequence of messages;

logging an order in which each message in the sequence of messages was observed; and

logging a time at which each message in the sequence of messages was observed.

19. The system of claim 16, wherein the constructing module constructs the sequence graph by further:

creating, for each node in the sequence graph, a dictionary of sequence transitions; and

adding, for each sequence transition in the sequence of messages whose succeeding message'"'"'s identifier is equal to the identifier that is represented by the node, an entry to the dictionary to represent the sequence transition, wherein;

the entry comprises;

a preceding-message identifier that is equal to the identifier of the sequence transition'"'"'s preceding message;

a transition order that is equal to the order of the sequence transition in the sequence of messages; and

a time interval equal to the amount of time between observances of the sequence transition'"'"'s preceding message and the sequence transition'"'"'s succeeding message; and

the edge that connects the nodes that represent the identifiers of the sequence transition'"'"'s preceding and succeeding messages comprises a directed edge that is incident from the node that represents the identifier of the sequence transition'"'"'s preceding message and incident to the node that represents the identifier of the sequence transition'"'"'s succeeding message.

20. A non-transitory computer-readable medium comprising one or more computer-executable instructions that, when executed by at least one processor of a computing device, cause the computing device to:

collect a sequence of messages that were distributed on a communication channel, wherein;

the sequence of messages comprises at least one obscured cyclic sequence of request-response messages that;

were exchanged by at least two components; and

are interleaved in the sequence of messages; and

each message in the sequence of messages comprises an identifier that indicates a meaning of the message;

construct a sequence graph from the sequence of messages by;

adding, for each unique message identifier in the sequence of messages, a node to the sequence graph to represent the unique message identifier; and

adding, for each unique sequence transition in the sequence of messages from an immediately-preceding message to an immediately-succeeding message, an edge to the sequence graph to;

represent the unique sequence transition; and

connect the node that represents the identifier of the unique sequence transition'"'"'s immediately-preceding message to the node that represents the identifier of the unique sequence transition'"'"'s immediately-succeeding message;

traverse the sequence graph to discover the obscured cyclic sequence of request-response messages; and

perform a security action using a representation of the obscured cyclic sequence of request-response messages.