Patent ID: 12225035

DETAILED DESCRIPTION

Mechanisms (including systems, methods, and media) for defending computing systems from attack are provided. In some embodiments, these mechanisms operate by assigning each of a plurality of hosts to a vertex in a directed graph. The hosts can be any suitable device, virtual machine, application, process, etc. that operates to detect and alert others to an attack on any of the hosts (i.e., to act as an IDS), thereby allowing countermeasures to respond to the attack in some embodiments. In some embodiments, a host can launch one or more child applications that the host can monitor to determine if the child application(s) stop. The directed graph defines monitoring relationships among the hosts. For example, if a vertex in the graph has an edge that points from the vertex to another vertex, the vertex is to monitor the other vertex. As another example, if a vertex in the graph has an edge that points to the vertex from another vertex, the vertex is to be monitored by the other vertex.

During operation, each host can track a round (or interval) during which certain messages are to be exchanged by the hosts. For example, each host can send a signed message with its round number to hosts that are monitoring the host. As another example, each host can send a heartbeat message to the hosts that are monitoring the host. As yet another example, each host can forward heartbeat messages received from hosts that it monitors to the hosts that are monitoring the host. If any host determines that any messages are invalid or missing, the host can generate an alert indicating an attack. This alert can be transmitted to any suitable hosts and/or other devices, applications, processes, etc.

When certain conditions are met, the hosts can update the positions in the graph occupied by each of the hosts. In some embodiments, the conditions can be that a round number is divisible by a diameter of the graph. The positions can be updated based on a pseudo-random function in some embodiments. In some embodiments, this pseudo-random function can use a shared key, the round counter, and identifiers for each of the hosts to determine the locations of the host in the graph. In some embodiments, each of the hosts can independently determine the locations of the host in the graph using the shared key, the round counter, and identifiers for each of the hosts. This way, the locations of the hosts in the graph are only known by the hosts.

Turning toFIG.1, an example of system hardware100that can be used in some embodiments is illustrated. As shown, system hardware100can include one or more attacker devices102, a plurality of host devices112, a communication network110, communication links108, and/or any other suitable components.

Hardware100can have any suitable scale in some embodiments. For example, in a small-scale implementation, each of the components shown inFIG.1can reside inside a user's home. As another example, in a medium-scale implementation, each of the components shown inFIG.1can reside inside an enterprise (which can span multiple locations). As yet another example, in a large-scale implementation, the components shown inFIG.1can reside anywhere on the Earth.

Attacker devices102can be any suitable devices from which to mount an attack on one or more systems protected by host devices112. Although one attacker device is shown inFIG.1, it should be apparent that any suitable number of attacker devices can be present. Although an attacker device is shown herein as being part of system100, it should be apparent that attacker devices are undesirable and that a system implemented in accordance with some embodiments may have no attacker devices. Although an attacker device may be thought of as being inside a network of components as shown, this presence may virtual and the attacker device may actually be outside the network but connected to the network in such a way as to present a threat to one or more components of the network.

Communication network110can be any suitable computer network such as the Internet, an intranet, a wide-area network (“WAN”), a local-area network (“LAN”), a wireless network, a digital subscriber line (“DSL”) network, a frame relay network, an asynchronous transfer mode (“ATM”) network, a virtual private network (“VPN”), a satellite network, a mobile phone network, a mobile data network, a cable network, a telephone network, a fiber optic network, and/or any other suitable communication network, or any combination of any of such networks.

In some embodiments, attacker devices102and host devices112can be connected to communication network110through communication links108. In some embodiments, communication links108can be any suitable communication links, such as network links, dial-up links, wireless links, hard-wired links, any other suitable communication links, or a combination of such links.

In some embodiments, communication network110and communication links108can be omitted when not needed.

Host devices112can be any suitable devices, virtual machines, applications, processes, etc. for protecting systems (not shown) from computer intrusions by one or more attacker devices. For example, a host device can be, can be part of, or can be attached to a firewall that is protecting a computer network of a business, a school, a home, a community, or any other suitable thing. As another example, a host device can be, can be part of, or can be attached to an endpoint device, such as a desktop computer, a laptop computer, a tablet computer, a smart phone, a smart appliance, an Internet of Things (IoT) device (e.g., a camera, a smart lock, a smart thermostat, a smart fire alarm, a home automation hub, and/or any other suitable IoT device), a set-top box, a streaming media device, a gaming device, a smart television, and/or any other suitable device that is vulnerable to attack and that has the ability to perform some or all of the functions described herein.

Each of devices102and112can include and/or be any of a general-purpose device such as a computer or a special-purpose device such as a client, a server, and/or any other suitable device. Any such general-purpose computer or special-purpose computer can include any suitable hardware. For example, as illustrated in example hardware200ofFIG.2, such hardware can include a hardware processor202, memory and/or storage201, an input device controller206, an input device208, display/audio drivers210, display and/or audio output circuitry212, communication interface(s)214, an antenna216, and a bus218.

Hardware processor202can include any suitable hardware processor, such as a microprocessor, a micro-controller, digital signal processor, dedicated logic, and/or any other suitable circuitry for controlling the functioning of a general-purpose computer or special purpose computer in some embodiments.

Memory and/or storage204can be any suitable memory and/or storage for storing programs, data, metrics, and/or any other suitable information in some embodiments. For example, memory and/or storage204can include random access memory, read only memory, flash memory, hard disk storage, optical media, and/or any other suitable storage device.

Input device controller206can be any suitable circuitry for controlling and receiving input from one or more input devices208in some embodiments. For example, input device controller206can be circuitry for receiving input from a touch screen, from one or more buttons, from a voice recognition circuit, from a microphone, from a camera, from an optical sensor, from an accelerometer, from a temperature sensor, from a near field sensor, and/or any other suitable circuitry for receiving user input.

Display/audio drivers210can be any suitable circuitry for controlling and driving output to one or more display and/or audio output circuitries212in some embodiments. For example, display/audio drivers210can be circuitry for driving an LCD display, a speaker, an LED, and/or any other display/audio device.

Communication interface(s)214can be any suitable circuitry for interfacing with one or more communication networks, such as communication network410in some embodiments. For example, interface(s)214can include network interface card circuitry, wireless communication circuitry, and/or any other suitable circuitry for interfacing with one or more communication networks.

Antenna216can be any suitable one or more antennas for wirelessly communicating with a communication network in some embodiments. In some embodiments, antenna216can be omitted when not needed.

Bus218can be any suitable mechanism for communicating between two or more of components202,204,206,210, and214in some embodiments.

Any other suitable components can be included in hardware200in accordance with some embodiments.

Turning toFIG.3, an example300of a process for monitoring hosts in accordance with some embodiments is shown. Process300can be executed by any suitable device, and any suitable device can execute any suitable number of instances of process300in some embodiments. For example, a host device112(FIG.1) can execute an instance of process300for each critical application running on the device in some embodiments. As another example, a host device112(FIG.1) can execute an instance of process300for each virtual machine running on the device in some embodiments.

As illustrated, after process300begins, at302, the process can connect to other hosts. These connections can be established in any suitable manner and can have any suitable characteristics. For example, these connections can be established as Transport Layer Security (TLS) connections in some embodiments.

Next, at304, process300can generate a signature-verification key pair and send the verification key of the pair to the other hosts. Any suitable signature-verification key pair can be used in some embodiments. For example, in some embodiments, the signature-verification key pair can be a private-public key pair (e.g., such as an RSA key pair), wherein the signature key is a private key that is used to form a digital signature of an item using the signature key and the verification key is a public (or at least public to the other hosts) key that can be used to authenticate the digital signature of the item using the verification key.

Then, at306, process300can generate and send a string to the other hosts. The string can be any suitable string, can have any suitable content, and can have any suitable length. For example, in some embodiments, the string can be binary and can have a length equal to a length needed for a key for any suitable pseudo random function (PRF) in some embodiments, and can be randomly (or pseudo-randomly) generated.

At308, process300can next receive verification keys and strings from instances of process300running on others hosts. These verification keys and strings can be as described above in connection with304and306in some embodiments.

Next, at310, process300can form a shared PRF key (SK) using the string generated at306and the strings received at308. The shared PRF key can be formed using these strings in any suitable manner. For example, in some embodiments, the shared PRF key be formed by an XOR of the strings (i.e., the string generated at306and the strings received at308). Because all instances of process300should be forming the shared PRF key from the same set of strings in the same manner, each instance should form the same shared PRF key in some embodiments.

Then, at312, process300can set a round counter (RC) (i.e., a counter for counting rounds) and an expected round counter (ERC) (i.e., a counter for counting expected rounds) to zero and clear an early heartbeat (EHB) flag. The EHB flag can be used to indicate if an early heartbeat message was received as described further below.

At314, process300can next determine whether the round counter is divisible by a diameter of a directed graph representing monitoring responsibilities of the hosts.

Any suitable directed graph can be used to represent the monitoring responsibilities of the hosts in some embodiments. For example, in some embodiments, a modified De Bruijn graph or a tree graph can be used to represent the monitoring responsibilities of the hosts. An example of a modified De Bruijn graph for eight hosts is shown inFIG.4. In a directed graph, each host can be represented by a vertex in the graph and each monitoring responsibility can be represented by an edge, where the tail of the edge is connected to the monitor (the host doing the monitoring) and the head of the edge is connected to the monitoree (the host being monitored). When the graph is implemented as a modified De Bruijn graph, the two vertices with addresses of all zeros and all ones can have edges pointing to each other rather the having edges that point to themselves as in a normal De Bruijn graph. As shown in the De Bruijn graph ofFIG.4, each vertex is identified by a three-digit binary value and each vertex monitors two vertices and is monitored by two vertices. For example, vertex 000 monitors vertices 001 and 111 and is monitored by vertices 100 and 111.

The diameter of the graph can be any suitable value in some embodiments. For example, in some embodiments, the diameter of the graph can be determined by first identifying, for each pair of vertices in the graph, the smallest number of edges connecting the vertices in the direction of the edges as the distance between the vertices, and then by identifying the distance of the pair of vertices with the largest distance as the diameter of the graph.

The round counter can be determined as being divisible by the diameter of the graph when dividing the value of the round counter by the value of the diameter results in no remainder. Because zero is divisible by any number, when the round counter has a value of zero (e.g., when314is performed immediately after performing312), the determination made at314will be “Yes”.

If it is determined at314that the round counter is divisible by the diameter of the graph, then, at316, process300can determine, for each host, a new location of the host in the graph by evaluating the PRF using the shared PRF key (SK), the round counter (RC), and the host's identifier (e.g., a static identifier of the host). For example, the PRF may output a 000 for a first host indicating that the first host now occupies the left-most position in the graph ofFIG.4and may output a 111 for a second host indicating that the second host now occupies the right-most position in the graph ofFIG.4. Any suitable PRF can be used in some embodiments. For example, in some embodiments, the PRF can be Advanced Encryption Standard (AES) encryption.

Because the directed graph determines which hosts are monitoring which other hosts based on the edges between vertices, being assigned a new location (i.e., a new vertex) in the graph at316results in each host having a new set of other hosts that it is monitoring.

Then, at317, process can determine new monitors for the present host and determine new monitorees for the present host based on the present host's position in the directed graph. For example, referring toFIG.4, if the present host is assigned position 000 in the graph, then it can determine that its monitors are the hosts associated with vertices 100 and 111 and that its monitorees are the hosts associated with vertices 001 and 111.

Next, at318, process300can send to the host's new monitorees a rushing message indicating the value of RC. This rushing message can be sent in any suitable manner and can have any suitable format in some embodiments.

After318, or if it is determined at314that the round counter is not divisible by the diameter of the graph, then, at320, process300can send a signed message to the monitors that are monitoring the host. This message can be sent in any suitable manner, can have any suitable format, and can have any suitable content in some embodiments. For example, in some embodiments, the message can indicate the current value of RC and the identity of the host.

Also, at320, in some embodiments, process300can forward to the monitors any heartbeat messages received from other hosts in the previous round. These heartbeat messages can be sent in any suitable manner in some embodiments. In some embodiments, only heartbeat messages that are directly received are forwarded.

Then, at322, process300can determine if the round counter (RC) is greater than or equal to the expected round counter (ERC) and whether the early heartbeat (EHB) flag is clear. If so, process300can sleep at324for any suitable duration. For example, in some embodiments, process300can sleep until the elapsed time since the end of the last sleep session is equal the round interval time (the sleep time is adjusted for the time spent sending and receiving messages, and performing computations).

In some embodiments, while sleeping, process300can be awoken in response to a message indicating that another process being monitored by the host has stopped. This other process can be any suitable process and any suitable message can be sent. For example, in some embodiments, the process can be a process started by the host and the message can be a SIGCHLD message. If it is determined that the other process has stopped, process300can generate an alert message in some embodiments. This alert message can be sent in any suitable manner, have any suitable format, and contain any suitable content. For example, in some embodiments, an alert message can indicate a possible attack on the other process and can be broadcast to all hosts.

After process300completes sleeping at324, or if process300determines at322that the round counter (RC) is not greater than or equal to the expected round counter (ERC) or that the early heartbeat (EHB) flag is not clear, then at330, process300can receive messages from the other hosts. Any suitable messages can be received in some embodiments. For example, these messages can be signed messages and forwarded heartbeat messages sent at320by other instances of process300executing on the other hosts.

Next, at332, process300can determine whether an invalid message has been received. This determination can be made in any suitable manner in some embodiments. For example, if a signature on a signed message is invalid, then the signed message can be determined to be invalid in some embodiments. As another example, in some embodiments, if a round counter indicated in a signed message is less than the host's round counter, then the signed message can be determined to be invalid in some embodiments. As yet another example, if forwarded heartbeat messages have an invalid signature, have a round counter less than the host's round counter, or come from the wrong host, then the heartbeat messages can be determined to be invalid in some embodiments. Note that since the forwarding host received the heartbeat messages from the previous round, process300can determine the expected identities of the hosts according to the view of the graph from the previous round in some embodiments.

If it is determined at332that a message is invalid, then, at334, process300can generate an alert message in some embodiments. This alert message can be sent in any suitable manner, have any suitable format, and contain any suitable content. For example, in some embodiments, an alert message can indicate a possible attack on the source of the message(s) and can be broadcast to all hosts.

After sending the alert at334, or if no message is determined to be invalid at332, at336, process300can determine if there is an early heartbeat (EHB) message. This determination can be made in any suitable manner in some embodiments. For example, if process300receives an unexpected heartbeat message at330, the heartbeat message can be determined to be an early heartbeat (EHB) message.

If it is determined at336that there is an early heartbeat message, then, at338, process300can set an early heartbeat (EHB) flag at338. This flag can be set in any suitable manner in some embodiments.

After setting the EHB flag at338, or if it is determined that there was no early heartbeat at336, at340, process300can determine whether a rushing message with a round number that is greater than the expected round counter (ERC) has been received. If so, at342, process300can set the expected round counter equal to the value of the round counter in the rushing message.

After setting the ERC at342, or determining that no rushing message with a round number that is greater than the expected round counter (ERC) has been received, then, at344, process300can determine whether a period for receiving messages has timed out. This determination can be made in any suitable manner. For example, in some embodiments, the time period for receiving messages can be the round interval plus a grace period of one second by default, or the default value multiplied by one plus the maximum outdegree of all vertices in the graph, if the round counter is divisible by the diameter.

If it is determined at344that the period for receiving messages has not timed out, then process can loop back to330. Otherwise, process300can branch to346and determine whether there are any missing messages. For example, if a signed message or a heartbeat message from another instance of process300being executed on another host is not received, that message can be determined to be missing.

If process300determines at346that a message is missing, the process can generate an alert message at348in some embodiments. This alert message can be sent in any suitable manner, have any suitable format, and contain any suitable content. For example, in some embodiments, an alert message can indicate a possible attack on the source of the message(s) and can be broadcast to all hosts.

After sending an alert message at348, or if it is determined at346that no message is missing, then process300can increment the round counter at350and loop back to314.

It should be noted that the above steps of the process ofFIG.3can be executed or performed in any order or sequence not limited to the order and sequence shown and described inFIG.3. Also, some of the above steps of the process ofFIG.3can be executed or performed substantially simultaneously where appropriate or in parallel to reduce latency and processing times. Furthermore, it should be noted that the process ofFIG.3is provided as an example only. At least some of the steps shown in this figure may be performed in a different order than represented, performed concurrently, or altogether omitted.

In some embodiments, any suitable computer readable media can be used for storing instructions for performing the processes described herein. For example, in some embodiments, computer readable media can be transitory or non-transitory. For example, non-transitory computer readable media can include non-transitory media such as non-transitory magnetic media (such as hard disks, floppy disks, and/or any other suitable media), non-transitory optical media (such as compact discs, digital video discs, Blu-ray discs, and/or any other suitable optical media), non-transitory semiconductor media (such as flash memory, electrically programmable read only memory (EPROM), electrically erasable programmable read only memory (EEPROM), and/or any other suitable semiconductor media), any suitable media that is not fleeting or devoid of any semblance of permanence during transmission, and/or any suitable tangible media. As another example, transitory computer readable media can include signals on networks, in wires, conductors, optical fibers, circuits, any suitable media that is fleeting and devoid of any semblance of permanence during transmission, and/or any suitable intangible media.

The provision of the examples described herein (as well as clauses phrased as “such as,” “e.g.,” “including,” and the like) should not be interpreted as limiting the claimed subject matter to the specific examples; rather, the examples are intended to illustrate only some of many possible aspects.

Although the disclosed subject matter has been described and illustrated in the foregoing illustrative embodiments, the present disclosure has been made only by way of example, and numerous changes in the details of implementation of the disclosed subject matter can be made without departing from the spirit and scope of the disclosed subject matter, which is limited only by the claims that follow. Features of the disclosed embodiments can be combined and rearranged in various ways.