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

Patent metadata

Field	Value
Publication number	US-10091077-B1
Application number	US-201615194337-A
Country	US
Kind code	B1
Filing date	Jun 27, 2016
Priority date	Jun 27, 2016
Publication date	Oct 2, 2018
Grant date	Oct 2, 2018

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.

First claim

What is claimed is:

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 wit

Assignees

• Symantec Corp

Inventors

• Pukish Michael
• Qiu Minjie
• Somasundaram Shankar

Classifications

• H04L63/1441

  Countermeasures against malicious traffic (countermeasures against attacks on cryptographic mechanisms H04L9/002) · CPC title

• H04L43/045 Primary

  for graphical visualisation of monitoring data · CPC title

• H04L63/1425

  Traffic logging, e.g. anomaly detection · CPC title

• H04L63/1416 Primary

  Event detection, e.g. attack signature detection · CPC title

• H04L43/08

  Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters · CPC title