Patent Description:
Digital security exploits that steal or destroy resources, data, and private information on computing devices are an increasing problem. Governments and businesses devote significant resources to preventing intrusions and thefts related to such digital security exploits. Some of the threats posed by security exploits are of such significance that they are described as cyber terrorism or industrial espionage.

Security threats come in many forms, including computer viruses, worms, trojan horses, spyware, keystroke loggers, adware, and rootkits. Such security threats may be delivered in or through a variety of mechanisms, such as spearfish emails, clickable links, documents, executables, or archives. Other types of security threats may be posed by malicious users who gain access to a computer system and attempt to access, modify, or delete information without authorization. <CIT> discloses a query graph decomposed into query subgraphs to facilitate analysis of computer network traffic represented as a dynamic data graph. <CIT> discloses systems and methods for in-memory processing of events. <CIT> discloses a system to monitor in real time events occurring in an operating system of a motor vehicle.

Events can occur on computer systems that may be indicative of security threats to those systems. Although in some cases a single event may be enough to trigger detection of a security threat, in other cases individual events may be innocuous on their own but be indicative of a security threat when considered in combination. For instance, opening a file, copying file contents, and opening a network connection to an Internet Protocol (IP) address may each, on their own, be normal and/or routine events on a computing device. However, the particular combination of those events may indicate that a process executing on the computing device is attempting to steal information from a file and send it to a server.

Digital security systems have accordingly been developed that can observe events that occur on computing devices, and that can use event data about one or more event occurrences to detect and/or analyze security threats. However, many such digital security systems are limited in some ways.

For example, some digital security systems receive event data reported by local security agents executing on computing devices, but store event data associated with numerous computing devices at a cloud server or other centralized repository. Although such a centralized repository of event data may have the storage space to store a large amount of event data, it can be difficult and/or inefficient for other elements of the digital security system to interact with the event data in the centralized repository. For instance, an event analysis system may be configured to evaluate received event data to determine whether the event data matches patterns associated with malicious behavior. However, the event analysis system may have to use an application programming interface (API) to submit a query over a network to the separate centralized repository, and wait for the centralized repository to return a response to that query over the network. Such network-based interactions can introduce latencies, and thereby delay the event analysis system from determining that patterns of malicious behavior have occurred on a computing device. Such delays can be significant for digital security systems, as malicious processes may be able to continue operating and attack computing devices until digital security systems identify corresponding patterns of malicious behavior.

As another example, some digital security systems may execute a set of standing queries against a collection of received event data on a regular basis, such as every minute. However, if a pattern of malicious behavior includes a series of multiple events that may occur over a period of five minutes, it can be inefficient for a digital security system to attempt to find that pattern in received event data once per minute. For example, the first four attempts at executing a query for that pattern (executed at a first minute mark, a second minute mark, a third minute mark, and a fourth minute mark) may be unlikely to succeed, if the full pattern is generally not found for five minutes. In this situation, executing a particular query every minute, even though multiple initial attempts are unlikely to succeed, can waste processing cycles, increase load on a database that stores the event data, delay execution of other queries that may be more likely to succeed, and/or cause other inefficiencies.

In some digital security systems, it may also be difficult to determine which queries to execute, and at which times. For instance, a security system may be configured to execute a set of queries against a database of event data. The security system may not be able to execute all of the queries concurrently, and thus may need to select which query to execute when resources are available to execute a new query. However, many security systems do not execute queries in an order determined based at least in part on event data that has actually been received. For instance, some security system may execute queries from the set of queries in a random order, in a round-robin order, in a predefined order, or in other orders, without selecting those queries based on which ones may be most likely to succeed. As an example, a security system may, based on a round-robin execution order, execute a query for an external network connection event even though the security system has not received event data indicating that a computing device recently initiated an external network connection. This query may accordingly be unlikely to succeed.

Additionally, some digital security systems may repeat entire queries if the queries are not initially successful. For instance, if a full pattern of events associated with a query is not found during an initial execution of the query, some digital security systems may search again for the full pattern of events during the next execution of the query, even if a portion of the pattern had been found during the initial query. Accordingly, these digital security systems may have to keep data associated with the partial pattern that has already been found so that it can be found again, and it may take longer and/or use additional computing resources to search for the entire pattern again during the next execution of the query.

Described herein are systems and methods associated with a digital security system that can address these and other deficiencies of digital security systems. For example, an event query host in the digital security system can store, in local memory, an event graph that represents events and relationships between events. Accordingly, information in the event graph can be locally-accessible by elements of the event query host. An event processor of the event query host can add representations of events that occurred on a computing device to the local event, substantially in real-time as event information is received by the event query host. If an event added to the event graph matches a trigger event for a query, the event processor can add a corresponding query instance to a query queue, to be executed at a scheduled execution time. Accordingly, query instances can be scheduled and executed at least in part due to corresponding event data that has actually been received by the event query host. Additionally, at the scheduled execution time for a query instance, a query manager can search the local event graph for a corresponding event pattern. If a matching event pattern is not found in the local event graph, the query manager can reschedule the query instance in the query queue to be re-attempted at a particular later point in time when a matching event pattern is more likely to be in the event graph. The query manager may also store a partial query state associated with any matching portions of the event pattern that were found in the event graph, such that the query manager can avoid searching for the full event pattern again during the next execution of the query instance.

<FIG> shows an example <NUM> of a system in which an event query host <NUM> can process an event stream <NUM> associated with at least one computing device <NUM>. The event stream <NUM> can include instances of event data associated with discrete events that occurred on the computing device <NUM>. The event query host <NUM> can generate and maintain an event graph <NUM> based on the event stream <NUM>. The event graph <NUM> can include vertices that represent events that occurred on the computing device <NUM>, and edges between the vertices that represent relationships between the events. The event query host <NUM> can manage a set of queries <NUM>, such as query 110A and query 110B shown in <FIG>. The event query host <NUM> may also execute individual query instances <NUM>, corresponding to one or more of the queries <NUM>, against the event graph <NUM>. The query instances <NUM> may be ordered within a query queue <NUM> according to scheduled execution times <NUM>. The event query host <NUM> may accordingly execute individual query instances <NUM> in the query queue <NUM> at the scheduled execution times <NUM>. If the event query host <NUM> finds matches for the query instances <NUM> in the event graph <NUM>, the event query host <NUM> can output corresponding query results <NUM>. If the event query host <NUM> does not find matches for a query instance in the event graph <NUM>, the event query host <NUM> may reschedule the query instance within the query queue <NUM> based on a later scheduled execution time.

The computing device <NUM> may have a sensor <NUM> that is configured to detect the occurrence of events on the computing device <NUM>. For example, the sensor <NUM> may be a security agent installed on the computing device <NUM> that is configured to monitor operations of the computing device <NUM>, such as operations executed by an operating system and/or applications. An example of such a security agent is described in <CIT>, which issued as <CIT>. The sensor <NUM> may be configured to detect when certain types of events occur on the computing device <NUM>. The sensor <NUM> may also be configured to transmit the event stream <NUM>, over the Internet and/or other data networks, to a remote security system that includes the event query host <NUM>.

The event stream <NUM> may indicate information about multiple events on the computing device <NUM> that were detected by the sensor <NUM>. Such events can include events and behaviors associated with software operations on the computing device <NUM>, such as events associated with Internet Protocol (IP) connections, other network connections, Domain Name System (DNS) requests, operating system functions, file operations, registry changes, process executions, and/or any other type of operation. By way of non-limiting examples, an event may be that a process opened a file, that a process initiated a DNS request, that a process opened an outbound connection to a certain IP address, that there was an inbound IP connection, that values in an operating system registry were changed, or any other type of event. In some examples, events may also, or alternatively, be associated with hardware events or behaviors, such as virtual or physical hardware configuration changes or other hardware-based operations. By way of non-limiting examples, an event may be that a Universal Serial Bus (USB) memory stick or other USB device was inserted or removed, that a network cable was plugged in or unplugged, that a cabinet door or other component of the computing device <NUM> was opened or closed, or any other physical or hardware-related event.

The event query host <NUM> can be part of a security system, such as a system associated with a security service that operates remotely from the computing device <NUM>. For example, the event query host <NUM> can be, or execute on, a computing system different from the computing device <NUM>, such as the computing system described below with respect to <FIG>. In some examples, the security system that includes the event query host <NUM> may process event streams associated with multiple computing devices, as will be discussed further below with respect to <FIG>. The event graph <NUM>, generated from such event streams, may be associated with a single computing device or a group of computing devices. One or more event query hosts in the security system can use queries <NUM> to determine when events or patterns of events, associated with behavior of interest, have occurred on one or more of the computing devices. In some examples, the behavior of interest associated with a query may be malicious behavior, such as behavior that may occur when malware is executing on the computing device <NUM>, when the computing device <NUM> is under attack by an adversary who is attempting to access or modify data on the computing device <NUM> without authorization, or when the computing device <NUM> is subject to any other security threat.

If the event query host <NUM> detects an occurrence of such an event or pattern of events, based on executing a query against the event graph <NUM> representing events that occurred on one or more computing devices, the event query host may output corresponding query results <NUM>. For instance, the query results <NUM> may indicate that a pattern of events associated with malware, other malicious behavior, or any other behavior of interest has occurred on the computing device <NUM>. Based on query results <NUM> generated by the event query host <NUM>, the security system may log instances of the behavior of interest, provide the query results <NUM> and/or corresponding event data to data analysts or event analysis systems within the security system, provide the query results <NUM> and/or corresponding instructions to the sensor <NUM>, and/or take other actions in response to the query results <NUM>. For example, if the query results <NUM> indicate that the computing device <NUM> is under attack by a malicious process executing on the computing device <NUM>, the security system may instruct the sensor <NUM> to block or terminate the malicious process, or to provide further information in the event stream <NUM> about ongoing activity of the malicious process.

The event query host <NUM> can have an event processor <NUM> that is configured to modify the event graph <NUM> to add information about individual events that the event processor <NUM> identifies within the event stream <NUM>, substantially in real-time as information about events are received in the event stream <NUM>. Accordingly, the event graph <NUM> can be updated, substantially continuously and in real-time, to include information about a set of events that occurred on the computing device <NUM>. For example, when the event processor <NUM> identifies an occurrence of new event on the computing device <NUM> based on new information received in the event stream <NUM>, the event processor <NUM> may add a new vertex to the event graph <NUM> that represents the new event. In some cases, the event processor <NUM> may also add or edit one or more edges in the event graph <NUM> that link the new vertex to one or more other vertices in the event graph <NUM>, based on relationships determined by the event processor <NUM> between the events represented by the vertices. Data associated with the event graph <NUM> may be stored in a database at the event query host <NUM>, for example as discussed below with respect to <FIG>.

In some examples, the event processor <NUM> may be configured with a set of event definitions. The event definitions may define data formats that the event processor <NUM> can use to identify and/or interpret event data within the event stream <NUM>. For example, the sensor <NUM> may be configured to use a particular data format to provide event data about a particular type of event within the event stream <NUM>, and the event processor <NUM> may also be configured to interpret the event data according to that particular data format. In some examples, the event definitions used by the event processor <NUM> and/or the sensor <NUM> may be changed or reconfigured over time. For example, event definitions associated with various event types can be changed or added to cause the sensor <NUM> to capture data about new types of events or to capture new or different data about known types of events, and the event processor <NUM> can accordingly also use such event definitions to interpret corresponding event data provided by the sensor <NUM> in the event stream <NUM>.

In some examples, the event definitions used by the event processor <NUM> and/or the sensor <NUM> may be ontological definitions managed by an ontology service within the security service, as described in <CIT>. For example, the event query host <NUM> may have an ontology manager (not shown) that is configured to receive ontological definition configurations from the ontology service, and provide ontological definitions of events to the event processor <NUM>.

The event query host <NUM> may also be configured with a set of query definitions <NUM> associated with queries <NUM>. The query definitions <NUM> may be configuration files, computer-executable instructions, and/or other data that indicate attributes of queries <NUM>. In some examples, the event query host <NUM> may store the query definitions <NUM> in the same database as the event graph <NUM>. In other examples, the event query host <NUM> may store the query definitions <NUM> in a different database or data structure.

The event query host <NUM> may also maintain the query queue <NUM>, which can include an ordered representation of query instances <NUM>. The query queue <NUM> may be ordered or sorted, for example, based on scheduled execution times <NUM> associated with the query instances <NUM>. In some examples, the event query host <NUM> may store data associated with the query queue <NUM> in the same database as the event graph <NUM> and/or the query definitions <NUM>. In other examples, the event query host <NUM> may store the data associated with the query queue <NUM> in a different database or data structure.

Each query instance in the query queue <NUM> may be associated with a corresponding query, and have the attributes of that query defined by the query definitions <NUM>. For example, the query queue <NUM> may include any number of distinct query instances <NUM> corresponding to query 110A, as well as any number of distinct query instances <NUM> corresponding to query 110B. Query instances <NUM> corresponding to query 110A may be distinct instances of query 110A, and/or have the attributes of query 110A. Similarly, query instances <NUM> corresponding to query 110B may be distinct instances of query 110B, and/or have the attributes of query 110B.

At any point in time, the query queue <NUM> may or may not include query instances <NUM> that correspond to all of the queries <NUM> managed by the event query host <NUM>. For example, the query queue <NUM> may not include a query instance that corresponds to query 110A at a first point in time, but the query queue <NUM> may include one or more query instances <NUM> that correspond to query 110A at a second point in time.

The queries <NUM> may be associated with corresponding trigger events <NUM>. For example, query 110A may be associated with trigger event 126A, while query 110B may be associated with trigger event 126B. The trigger event for a query may be a particular type of event, that if detected in the event stream <NUM>, may indicate that the event query host <NUM> should execute an instance of the query against the event graph <NUM>.

Accordingly, the event processor <NUM> may be configured to detect trigger events <NUM>, associated with the queries <NUM>, in the incoming event stream <NUM>. If the event processor <NUM> detects a trigger event associated with a particular query in the event stream <NUM>, the event processor <NUM> can add a new query instance to the query queue <NUM> that corresponds to that particular query. For example, as the event processor <NUM> is identifying events in the event stream <NUM> in order to add information associated with such events to the event graph <NUM>, the event processor <NUM> may determine that one of the events is the trigger event 126A for query 110A. The event processor <NUM> may add information associated with the event to the event graph <NUM>, and also add a new query instance to the query queue <NUM> that corresponds with query 110A.

In some examples, a trigger event for a query may be associated with an event type, as well as one of more filters that, if satisfied, indicate that a corresponding query instance should be added to the query queue <NUM>. Filters may indicate a minimum version requirement for an event, a requirement that a particular data field associated with the event includes a particular value, a requirement that an identifier of the event be included on a whitelist stored by the event query host, and/or any other requirement. The event processor <NUM> may accordingly identify one or more candidate events in the event stream <NUM> that may be a trigger event for a query, and then use one or more filters associated with the query to determine if the candidate events are actually trigger events <NUM> for the query. If such an event satisfies the filters associated with a query, and is therefore a trigger event associated with the query, the event processor may add a corresponding query instance to the query queue <NUM>.

As a non-limiting example, a trigger event for a query may have a DNS lookup event type, but be associated with one or more filters for DNS lookups of particular domain names, or that return specific IP addresses or an IP address in a particular range of IP addresses. The event processor <NUM> may accordingly identify all DNS lookup events in the event stream <NUM> as potential trigger events, and use corresponding filters to determine if any of those DNS lookup events satisfy the filters and are to be treated as actual trigger events <NUM>.

In some examples, the event processor <NUM> may be configured to perform de-duplication operations on received event data. For example, multiple instances of the same event data may arrive at different times in the event stream <NUM>. The event processor <NUM> may be configured to determine whether an instance of received event data <NUM> has already been added to the event graph <NUM> and/or matched a trigger event such that the instance of event data already prompted the event processor <NUM> to add a query instance to the query queue <NUM>. In these examples, if the event processor <NUM> determines that an instance of received event data is a duplicate of a previously-received instance of event data, the event processor <NUM> may avoid adding another representation of the duplicated instance of event data to the event graph <NUM>, and may also avoid adding another query instance to the query queue <NUM> based on the duplicated instance of event data.

In some examples, the event processor <NUM> may add new query instances <NUM> to the query queue <NUM> with scheduled execution times <NUM> that are selected based on a default scheduling configuration. For example, the event processor <NUM> may be configured to add a new query instance to the end of the query queue <NUM> by assigning the new query instance a scheduled execution time that is at least a predefined amount of time later than the scheduled execution time of the last query instance already present within the query queue <NUM>.

As a non-limiting example, the query queue <NUM> may contain query instance 112A and query instance 112B. The query instance 112A may be the lowest-priority query instance in the query queue <NUM>, because the scheduled execution time 116A of query instance 112A is later than the scheduled execution time 116B of query instance 112B. The event processor <NUM> may be configured to add new query instance 112C at the end of the query queue <NUM> with a scheduled execution time 116C that is later than scheduled execution time 116A of query instance 112A.

In other examples, the event processor <NUM> may be configured to assign a new query instance a scheduled execution time that causes the new query instance to be placed at the front or middle of the query queue <NUM>. As a non-limiting example, if a particular query has a high importance or priority level, and the event processor <NUM> detects a trigger event associated with that query, the event processor <NUM> may add a new corresponding query instance to the query queue <NUM> with a scheduled execution time that causes the new query instance to be executed before other query instances <NUM> already present in the query queue <NUM>.

Some or all of the queries <NUM> may be standing queries that can lead to corresponding query instances <NUM> being added to the query queue <NUM> at any time. However, in some examples, the query definitions <NUM> may indicate that one or more of the queries <NUM> are ephemeral queries. Ephemeral queries may be associated with specific periods of time, specific sensors, specific events in the event stream, or other specific conditions. As an example, an ephemeral query may indicate that all of the event data from a particular sensor, such as sensor <NUM>, should be examined using specific query criteria <NUM> for a period of ten minutes. Accordingly, corresponding query instances may be active in the query queue <NUM> for up to ten minutes. As another example, an ephemeral query may indicate that if a particular process is launched on the computing device <NUM>, all related events associated with that particular process and/or any of its child processes should be monitored according to specific query criteria <NUM> until the particular process terminates. Accordingly, corresponding query instances may be active in the query queue <NUM> until event data is received in the event stream indicating that the particular process has terminated.

In some examples, the event query host <NUM> may be associated with a user interface and/or APIthat allows users to view query definitions <NUM>, edit query definitions <NUM>, delete query definitions <NUM>, and/or add new query definitions <NUM>. For example, a user may generate a definition for a new type of query, and use the API to submit the new query definition to the event query host <NUM> as a new standing query or an ephemeral query. In some examples, the user interface and/or API may be associated with a centralized computing device or service that can manage query definitions <NUM> and periodically provide updates to the query definitions <NUM> to the event query host <NUM> and/or other event query hosts. In other examples in which multiple event query hosts are associated with each other, as discussed below with respect to <FIG>, updates to query definitions <NUM> made locally at the event query host <NUM> may be propagated to the other event query hosts over a network connection. The centralized computing device, and/or each event query host, may have a database that stores information about changes to the query definitions <NUM> over time, for example for backup and/or auditing purposes.

The event query host <NUM> can have a query manager <NUM> that is configured to manage and execute query instances <NUM> in the query queue <NUM>, based on corresponding scheduled execution times <NUM>. The query queue <NUM> may be ordered based on the scheduled execution times <NUM> of the query instances <NUM>, such that the query manager <NUM> can attempt to process the highest-priority query instance in the query queue <NUM> at the scheduled execution time of that query instance. For example, query instance 112B shown in <FIG> may be the highest-priority query instance in the query queue <NUM>, if the scheduled execution time 116B is earlier than the scheduled execution times <NUM> of other query instances <NUM> in the query queue <NUM>.

The queries <NUM>, and thus corresponding query instances <NUM> in the query queue <NUM>, may be associated with query criteria <NUM>. For example, query 110A may be associated with query criteria 130A, while query 110B may be associated with query criteria 130B. Query criteria <NUM> for the queries <NUM> may indicate that the queries <NUM> are filter queries, metadata queries, or pattern queries.

Filter queries may indicate a particular event type, and determine if any detected events of that event type represented in the event graph <NUM> match one or more filters. For example, a filter query may be associated with DNS lookup events, and indicate that query results <NUM> should be emitted if a DNS lookup event represented in the event graph <NUM> is associated with a particular IP address range defined by a filter.

Metadata queries may indicate a particular event type, and query one or more types of metadata associated with the event. For instance, a metadata query may identify an event type that may be indicative of an attack or compromise on the computing device <NUM>. If that event type is found in the event graph <NUM>, the metadata query may indicate that related contextual data, such as information about parent processes or other related events, should be collected and emitted as query results <NUM> if such information is present within the event graph <NUM>.

Pattern queries may indicate a pattern of one or more events that are relevant to the queries, such as a pattern of events that may be associated with malware, other malicious behavior, or any other behavior of interest. For example, query criteria <NUM> for a query may indicate a type of each event in the pattern, relationships between the events in the pattern, timeframes associated with relationships between the events in the pattern, and/or any other information about the pattern of events. The query may accordingly be satisfied if the pattern of events is found within the event graph <NUM>, and corresponding query results <NUM> can be emitted.

In some examples, the query criteria <NUM> for a query may be a pattern of one or more events that is expressed using a graph representation that represents the events as vertices, and uses edges between the vertices to represent relationships between the events. An example of a graph for such an event pattern for query criteria <NUM> is shown in <FIG>, and is discussed further below with respect to that figure. A query may accordingly be satisfied if at least one sub-graph that matches the graph associated with the query criteria <NUM> for the query is found within the event graph <NUM>.

At the scheduled execution time of a query instance in the query queue <NUM>, the query manager <NUM> may determine the query criteria <NUM> of that query instance. The query manager <NUM> may also attempt to find a sub-graph, within the event graph <NUM>, that matches a pattern indicated by the query criteria <NUM>. For example, the query manager <NUM> may use graph isomorphism principles and/or perform graph traversal operations to search for one or more sub-graphs, within the event graph <NUM>, that match a graph of events associated with a query instance.

If the query manager <NUM> executes a query instance in the query queue <NUM>, and finds a sub-graph within the event graph <NUM> that matches the query criteria <NUM> of that query instance, the query instance may be satisfied. The query manager <NUM> may remove the query instance from the query queue <NUM>, and cause the event query host <NUM> to generate corresponding query results <NUM>.

However, if the query manager <NUM> executes a query instance in the query queue <NUM>, but does not find a sub-graph within the event graph <NUM> that matches the query criteria <NUM> of that query instance, the query manager <NUM> may reschedule the query instance in the query queue <NUM>. For example, the query manager <NUM> may edit the scheduled execution time of the query instance in the query queue <NUM>, such that the query instance is lowered in the query queue <NUM> and is scheduled to be retried at a later time.

As a non-limiting example, the query manager <NUM> may have previously executed query instance 112A, but not found a matching sub-graph in the event graph <NUM>. The query manager <NUM> may have changed the scheduled execution time 116A of query instance 112A to a time that is later than the scheduled execution time of 116B of query instance 112B, in order to reschedule the next execution of query instance 112A after the next execution of query instance 112B.

The queries <NUM>, and thus corresponding query instances <NUM> in the query queue <NUM>, may be associated with rescheduling schemes <NUM>. For example, query 110A may be associated with rescheduling scheme 132A, while query 110B may be associated with rescheduling scheme 132B. The rescheduling scheme for a query may indicate a wait time, or other rescheduling information, which the query manager <NUM> can use to determine a new scheduled execution time for a query instance corresponding to that query. The query manager <NUM> may accordingly re-order the query queue <NUM> based on a new scheduled execution time for a query instance determined based on a rescheduling scheme. For example, if the query manager <NUM> executes a query instance, but the query instance is not satisfied, the query manager <NUM> may reschedule the query instance in the query queue <NUM> to be executed again three minutes later, based on a rescheduling scheme that indicates a three-minute wait time. As a non-limiting example, query instance 112A shown in <FIG> may have been rescheduled after an earlier attempt, such that query instance 112B is a higher priority, and has an earlier scheduled execution time 116A, in the query queue <NUM> than query instance 112A.

In some examples, a rescheduling scheme for a query may indicate that each corresponding query instance within the query queue <NUM> should be retried on a regular basis after a consistent wait time if the query instance has not yet been satisfied, such as every minute, every two minutes, or on any other frequency. In other examples, a rescheduling scheme for a query may indicate that each corresponding query instance in the query queue <NUM> should be retried after varying wait times based on an exponential backoff scheme if the query instance has not yet been satisfied, such as a first retry after one minute, a second retry two minutes later, a third retry four minutes later, a fourth retry eight minutes later, and so on.

However, in still other examples, a rescheduling scheme for a query may indicate a wait time, or other rescheduling information, that has been determined based on historical information about prior corresponding query instances. For instance, the event query host <NUM> may use statistical analysis operations to determine averages, percentiles, or other statistical metrics associated with times it has historically taken to find sub-graphs that satisfy query instances. Such statistical metrics may be used to determine scheduled execution times <NUM> that can be used to schedule and/or reschedule query instances <NUM>. In some examples, the event query host <NUM> may use artificial intelligence or machine learning techniques to determine how long to wait before a next execution of a query instance that has not yet been satisfied. For instance, a machine learning model may be trained, based on historical information about prior query instances, to predict optimal scheduled execution times <NUM> that can be used to schedule and/or reschedule query instances <NUM>.

As a non-limiting example, a rescheduling scheme for a query may indicate that, on average, it takes five minutes and thirty seconds for a sub-graph that matches the query criteria of the query to be found in the event graph <NUM>. Accordingly, the rescheduling scheme for the query may indicate that an instance of that query should be scheduled for five minutes and thirty seconds after the trigger event was identified, be rescheduled after an initially unsuccessful first execution attempt for a time that is five minutes and thirty seconds after the trigger event was identified, or be rescheduled for five minutes and thirty seconds after the unsuccessful first execution attempt.

In some examples, rescheduling schemes <NUM> for the queries <NUM> may initially be based on a consistent wait time, an exponential backoff scheme, or any other predefined pattern. However, as actual corresponding query instances <NUM> are attempted over time, and the event query host <NUM> collects corresponding historical data about those query instances <NUM>, the event query host <NUM> may dynamically adjust the rescheduling schemes <NUM> for the queries <NUM>.

As a non-limiting example, the rescheduling scheme 132A may initially cause the query manager <NUM> to execute instance of query 110A every minute until a matching sub-graph is found in the event graph <NUM>. However, after fifty, one hundred, or any other number of instances of query 110A have completed, the query manager <NUM> or another element of the event query host <NUM> may determine that, for <NUM>% of those instances, a matching sub-graph was found within four minutes. Accordingly, the event query host <NUM> may adjust the rescheduling scheme 132A so that future instances of query 110A may be scheduled and/or rescheduled to be executed four minutes after trigger event 126A was identified. Accordingly, the query manager <NUM> may wait four minutes to attempt and/or reattempt an instance of query 110A, rather than attempting the instance of query 110A every minute even though attempts during the first minute, second minute, and third minute may be unlikely to succeed. Accordingly, because the rescheduling schemes <NUM> can be dynamically adjusted and used to determine scheduled execution times <NUM> for query instances <NUM> that may be the most likely to succeed, the rescheduling schemes <NUM> can reduce the number of graph traversal operations performed by the query manager <NUM>, and also reduce the load on the database that stores the event graph <NUM>.

In some examples, the query manager <NUM> may vary the actual times used to determine scheduled execution times <NUM>, in order to obtain additional historical data about how long query instances <NUM> take to succeed and to further refine and adjust the rescheduling schemes <NUM> over time. For example, the query manager <NUM> may determine, based on at least a threshold number of earlier instances of query 110B, that on average it takes five minutes for instances of query 110B to succeed. However, rather than rescheduling every subsequent unsuccessful instance of query 110B within the query queue <NUM> to be re-executed after a wait time of five minutes, the query manager <NUM> may schedule some unsuccessful instances of query 110B to be re-executed at varying wait times within a four to six-minute time window. Attempting to re-execute various instances of query 110B after waiting four minutes, five minutes, six minutes, or other periods of time within the four to six-minute time window, instead of rescheduling only based on the initially-determined average of five minutes, can provide additional historical data that may show that the average success time has decreased, over time, to four and a half minutes. The query manager <NUM> may accordingly refine the rescheduling schemes <NUM> associated with queries <NUM> over time, based at least in part on tracking success times associated with query instances <NUM> and rescheduling unsuccessful query instances <NUM> based on varying wait times within time windows associated with the rescheduling schemes <NUM>.

In addition to scheduled execution times <NUM>, the query instances <NUM> in the query queue <NUM> may be associated with partial query states <NUM>. As discussed above, the query manager <NUM> may execute a query instance at a corresponding scheduled execution time. The query manager <NUM> may identify query criteria <NUM> associated with the query instance, such as a graph that uses vertices and edges to represent a pattern of events and relationships between the events. The query manager <NUM> can accordingly attempt to find a sub-graph, within the event graph <NUM>, that matches the graph associated with the query instance. If the query manager <NUM> does not find a full matching sub-graph within the event graph <NUM>, but does find one or more matching portions of the sub-graph within the event graph <NUM>, the query manager <NUM> may store data associated with the matching portions of the sub-graph as a partial query state associated with the query instance. In some examples, the partial query states <NUM> may include copies of data associated with corresponding vertices and/or edges in the event graph <NUM>, such as copies of database data shown and described below with respect to <FIG>.

Although the partial query state can be stored in association with the query instance, the query instance may not yet be successful because the full query criteria <NUM> associated with the query instance has not yet been found in the event graph <NUM>. The query manager <NUM> may accordingly reschedule the unsuccessful query instance in the query queue <NUM> with a later scheduled execution time, as discussed above. However, during the next execution of the query instance at the later scheduled execution time, the query manager <NUM> may use the stored partial query state to determine which portions of the query criteria <NUM> have already been found in the event graph <NUM>. The query manager <NUM> can accordingly attempt to identify only the remaining portions of the query criteria <NUM> that have not yet been found in the event graph <NUM>, instead of searching for the entire query criteria <NUM> in the event graph <NUM>. For instance, the query manager <NUM> may search for remaining elements of a sub-graph associated with the query instance which, in combination with the stored partial query state, complete the full sub-graph. Accordingly, the partial query states <NUM> can allow the query manager <NUM> to pick up where it left off with respect to individual query instances <NUM> that are attempted more than once.

As a non-limiting example, query criteria <NUM> for query instance 112A may indicate a specific pattern of six events. Upon a first execution of query instance 112A, the query manager <NUM> may identify vertices and edges in the event graph <NUM> may match two of the six events associated with the query criteria <NUM> for query instance 112A. The query manager <NUM> may store a partial query state 134A in association with query instance 112A, and change the scheduled execution time 116A of query instance 112A in the query queue <NUM> so that the query manager <NUM> will execute query instance 112A again five minutes later. When the query manager <NUM> executes query instance 112A again five minutes later, the query manager <NUM> can determine from the stored partial query state 134A that two of the six events associated with the query criteria <NUM> for query instance 112A were already found in the event graph <NUM>. The query manager <NUM> can accordingly attempt to find vertices and edges in the event graph <NUM> that match the remaining four events associated with the query criteria <NUM> for query instance 112A, rather than searching again for the full pattern of six events.

The partial query states <NUM> therefore allow the query manager <NUM> to continue searching for remaining elements of query criteria <NUM> associated with repeated query instances <NUM> that have not yet been found in the event graph <NUM>, rather than searching for the full query criteria <NUM> in part by searching again for elements that have already been found. Accordingly, the query manager <NUM> can use the partial query states <NUM> to efficiently search for the remaining elements of query criteria <NUM>, and thereby avoid using processor cycles, memory, and other computing resources to search again for elements of query criteria <NUM> that have already been found in the event graph <NUM>.

Moreover, the query manager <NUM> may determine, based in part on the partial query states <NUM>, that the query criteria <NUM> for a query instance has been found in the event graph <NUM>, even if some of the elements of the query criteria <NUM> have been deleted from the event graph <NUM>. For example, during a first execution of query instance 112C, the query manager <NUM> may find a first vertex in the event graph <NUM> that matches a first portion of the query criteria <NUM> associated with the query instance 112C, and may store information about the first vertex in the partial query state 134C in association with the query instance 112C. Later, during a subsequent execution of query instance 112C, the query manager <NUM> may find other vertices and/or edges in the event graph <NUM> that, in combination with the first vertex, satisfy the query criteria <NUM> associated with the query instance 112C. In some situations, the first vertex may have been deleted from the event graph <NUM> after the first execution of query instance, for example based on a timestamp of the first vertex exceeding a time-to-live (TTL) value as will be discussed further below. However, because information associated with the first vertex had been stored in the partial query state 134C associated with query instance 112C, the information in the partial query state 134C may allow the query criteria associated with query instance 112C to be satisfied even if the first vertex is no longer present in the event graph <NUM>.

Stored data associated with the query queue <NUM>, including the partial query states <NUM>, can also be used if the event query host <NUM> is restarted. For example, if the event query host <NUM> is upgraded to a new version, is reloaded after an error, or is restarted for any other reason, the query queue <NUM> can be re-initiated based on stored data about the state of the query queue <NUM> and the stored partial query states <NUM>. Accordingly, the stored partial query states <NUM> and/or other stored state data associated with the query queue <NUM> can allow the query manager <NUM> can to pick up where it left off after a restart of the event query host <NUM>.

As discussed above, the event processor <NUM> may be configured to receive the event stream <NUM>, add representations of identified events to the event graph <NUM>, and add new query instances <NUM> to the query queue <NUM> if identified events match trigger events <NUM> for queries <NUM>. The query manager <NUM> may be configured to execute individual query instances <NUM> in the query queue <NUM> at scheduled execution times <NUM>. The query manager <NUM> can also be configured to emit query results <NUM> if the query instances <NUM> are satisfied, or to store partial query states <NUM> and reschedule the query instances <NUM> within the query queue <NUM> if the query instances <NUM> are not yet satisfied. In some examples, the event processor <NUM> and the query manager <NUM> may execute substantially concurrently on a computing system. For instance, the computing system may execute operations of the event processor <NUM> using a first set of parallel threads, while substantially concurrently executing operations of the query manager <NUM> using a second set of parallel threads. Accordingly, the event processor <NUM> may modify the event graph <NUM> based on new event data substantially in real-time, while the query manager <NUM> may execute query instances <NUM> against up-to-date event data in the event graph <NUM> as soon as the event data is received and added to the event graph <NUM> by the event processor <NUM>.

Overall, the event query host <NUM> shown in <FIG> can locally store the event graph <NUM> of event data, such that query instances for event patterns can be locally executed against the event graph <NUM> without latencies that may be introduced by network-based queries to a remote database of event data. Moreover, the local event graph <NUM> can be modified substantially in real-time as new event data is received, and such modifications to the local event graph <NUM> may trigger new query instances <NUM> to be scheduled that are associated with the newly received event data. Accordingly, because the query instances <NUM> are scheduled based on recently received event data, such query instances <NUM> may be more likely to succeed. Additionally, the event query host <NUM> shown in <FIG> can dynamically schedule, and reschedule, individual query instances <NUM> based on historically-determined metrics about how long it may take to satisfy the query instances <NUM>, and thereby avoid repeated query attempts at earlier times that may be unlikely to succeed. The event query host <NUM> shown in <FIG> can also store partial query states <NUM> associated with individual query instances <NUM> that have not yet been satisfied. Accordingly, during a later execution of a rescheduled query instance, a partial query state can be used to identify portions of an event pattern that have already been found in the event graph <NUM>, and a search can be performed for remaining portions of the event pattern instead of a new search for the entire event pattern. The partial query states <NUM> may accordingly lower search times associated with subsequent executions of query instances <NUM>, reduce load on a database that stores the event graph <NUM>, and query instances <NUM> to succeed even if matching event data is removed from the event graph <NUM>.

<FIG> show an example <NUM> of the event graph <NUM>. The event graph <NUM> can include vertices <NUM> that each represent an event that occurred on the computing device <NUM>. The event processor <NUM> can be configured to, substantially in real-time upon identifying an event in the incoming event stream <NUM>, add a vertex to the event graph <NUM> that represents information about the event. As a non-limiting example, if the event stream <NUM> indicates that a "RunDLL32. exe" process was executed on the computing device <NUM> at a certain time, the event processor <NUM> can add a vertex to the event graph <NUM> that identifies the "RunDLL32. exe" process, the time the "RunDLL32. exe" process was executed, and/or any other information about the "RunDLL32. exe" process indicated by the event stream <NUM>.

Vertices <NUM> may also be connected by edges <NUM> in the event graph <NUM>. The edges <NUM> can represent relationships between events represented by the vertices <NUM>. For example, if the event stream <NUM> indicates that the "RunDLL32. exe" process discussed above spawned a "cmd. exe" process as a child process, the event processor <NUM> can add a vertex to the event graph <NUM> that represents the "cmd. exe" process, and add an edge between the vertex associated with the "RunDLL32. exe" process and the edge associated with the "cmd. exe" process. The edge between these two vertices <NUM> can indicate that the "RunDLL32. exe" process spawned the "cmd. exe" process.

In some examples, the event graph <NUM> can be a directed graph. For instance, an edge, between a first vertex representing a parent process and a second vertex representing a child process, can be a directional edge that points from the first vertex to the second vertex to represent the parent-child relationship between the processes.

Data defining entities within the event graph <NUM>, such as the vertices <NUM> and the edges <NUM>, can be stored in a database. For example, data associated with the event graph <NUM> may be stored in "RocksDB" database, or other type of database. The database may store key-value data for each entity, and information about different entities in the event graph <NUM> can be stored in the database using an adjacently list graph representation. An example of data for a particular entity of the event graph <NUM> is shown in <FIG>, and is discussed below with respect to that figure.

In some examples, the database storing the event graph <NUM> may be in local memory at the event query host <NUM>, rather than being stored on a remote server or in a cloud computing environment. As such, the event processor <NUM> can add data to the event graph <NUM> in local memory substantially in real-time as events are identified in the event stream, without transmitting instructions over a data network to add the data to the event graph <NUM>. Similarly, the query manager <NUM> can execute query instances <NUM> and perform graph traversal operations on the locally-stored event graph <NUM>, rather than transmitting query instructions over a data network to a remotely-stored event graph <NUM> and waiting for results to be received over the data network. Accordingly, storing data associated with the event graph <NUM> in local memory at the event query host <NUM> can avoid latencies associated with data transmissions over data networks, and thereby can allow the event graph <NUM> to be updated and searched by elements of the event query host <NUM> more quickly.

As noted above, information about entities, such as vertices <NUM> and edges <NUM>, in the event graph can be stored in a database. For example, the database may have an entry associated with each of the entities. Each database entry may include one or more values, including an entity key and/or other values as discussed with respect to <FIG>.

<FIG> shows an example of an entity key <NUM> associated with an entity in the event graph <NUM>. As described above, data associated with entities in the event graph <NUM>, such as vertices <NUM> and edges <NUM>, can be stored as entries in a database. Each entry in the database may be associated with an entity key, such as the entity key <NUM> shown in <FIG>. The entity keys in the database can uniquely identify each entity in the database. In some examples, the database may sort the entities based on the entity keys. The entity keys may also allow the event processor <NUM> and/or the query manager <NUM> to traverse the event graph <NUM> in part by identifying database entries corresponding to vertices <NUM> and/or edges <NUM> of the event graph <NUM>. Each entry may also have data in one or more other fields in addition to the entity key. For example, an entry associated with a DNS lookup event may have additional data fields that indicate a specific domain name, IP address, and/or other information associated with that DNS lookup event.

In some examples, when the event processor <NUM> identifies an event, or a relationship between events, based on the event stream <NUM>, the event processor <NUM> may add a corresponding entry to the database. In other examples, when the event processor <NUM> identifies an event, or a relationship between events, based on the event stream <NUM>, the event processor <NUM> may determine if the event or relationship is a modification of an event or relationship that is already represented in the event graph. In these examples, the event processor <NUM> may be configured to modify the existing representation of the event in the database. For instance, a new event may be an indication that a process has terminated. If the launch of that process is represented by an entity in the database, the event processor <NUM> may modify the existing entity in the database to indicate that the process, launched earlier, has now terminated. However, in other examples, the event processor <NUM> may be configured to add new entities to the database in association with each new identified event or relationship, even if it is a modification of a previous event or relationship.

The event processor <NUM> may also fill in fields of each database entry, and/or related entries, including fields of the entity key <NUM>. The entity key <NUM> may include a set of fields that can hold data such as a customer identifier (CID) <NUM>, an agent identifier (AID) <NUM>, a source vertex type <NUM>, a source key <NUM>, an edge type <NUM>, a timestamp <NUM>, a destination vertex type <NUM>, a destination key <NUM>, and/or a checksum <NUM>.

The CID <NUM> may indicate a customer number or other identifier associated with the computing device <NUM>. The AID <NUM> may be a number or other identifier associated with the sensor <NUM> executing on the computing device <NUM>. For example, a customer associated with the security service may be a company or other organization that has numerous computing devices, each of which execute a different instance of the sensor <NUM>. The set of computing devices associated with the customer may be associated with a common CID, but each of the sensors on those computing devices may have a unique AID. Accordingly, entities in the database that are associated with a specific customer and/or a specific computing device can be identified using the CIDs and/or AIDs of the entity keys.

The source vertex type <NUM> and the destination vertex type <NUM>, in the entity key <NUM> for an entity, can indicate event types associated with a source vertex and/or a destination vertex in the event graph <NUM> that are associated with the entity. The event types may indicate that a source vertex or a destination vertex represents a DNS lookup, a launch of a process on a computing device, an initiation of a network connection, a particular hardware event, and/or any other type of event. The edge type <NUM> can similarly indicate a type of relationship that may exist between two events, such as that a first process launched a second process as a child process, that a process associated with a first event initiated a second event, or any other relationship between events.

The source key <NUM> and destination key <NUM>, in the entity key <NUM> for an entity, can identify specific entities within the database that are associated with the source vertex and/or destination vertex. For example, multiple entities in the database may be associated with a process execution event type, and each may therefore have entities keys with a shared source vertex type. However, each of those entities may have a distinct source key, such that each of the entities can be uniquely identified.

In some examples, the database may use the same entity key format to represent both vertices and edges of the event graph <NUM>. For example, if an entity is an edge (representing a relationship between a source vertex and a destination vertex), the corresponding entity key <NUM> may have values for the source vertex type <NUM> and the source key <NUM>, as well as values for the destination vertex type <NUM> and the destination key <NUM>. Accordingly, the entity key <NUM> can indicate that the entry is an edge by identifying the source vertex and the destination vertex that are related by the edge. However, if an entity is instead a vertex (representing a particular event), the corresponding entity key <NUM> may have values for the source vertex type <NUM> and/or the source key <NUM>, but omit values for the destination vertex type <NUM> and the destination key <NUM>. The absence of values for the destination vertex type <NUM> and the destination key <NUM> can indicate that the entity is a vertex, and is not an edge.

The timestamp <NUM> may indicate a time associated with the entity. The timestamp <NUM> may indicate a time when the entity was added to the database, or a time when the entity was last accessed or edited. In some examples, the event processor <NUM> may fill in the timestamp <NUM> based on a time reported by the sensor <NUM> in the event stream <NUM>. For instance, the sensor <NUM> may report a time at which a process launched on the computing device <NUM>, or a time at which the sensor <NUM> detected an event, and the event processor <NUM> may use that reported time as the timestamp <NUM>. In other examples, the event processor <NUM> may fill in the timestamp <NUM> based on a time at which the event processor <NUM> identified the entity within the event stream <NUM>, or a time at which the event processor <NUM> added the entity to the event graph <NUM>.

The checksum <NUM> can be a value generated based on one or more elements of the entity key <NUM> and/or other portions of the entity. The event query host <NUM> may use the checksum <NUM> to verify the integrity of the data stored in the entity and/or perform error correction on data stored in the entity. In some examples, the checksum <NUM> may be a cyclic redundancy check (CRC) or CRC-<NUM> value.

Elements of the event query host <NUM>, such as the event processor <NUM> and/or query manager <NUM>, may traverse or search the event graph <NUM> based on entity keys associated with vertices <NUM> and edges <NUM>. In some examples, elements of the event query host <NUM> may use partial entity keys to identify one or more specific entities, or types of entities, in the event graph <NUM>. For example, the event query host <NUM> may search the event graph <NUM> based on a first key prefix that includes the first three elements of the entity keys (the CID <NUM>, the AID <NUM>, and the source vertex type <NUM>) to locate all vertexes associated with a particular customer, a particular sensor, and a particular event type. The event query host <NUM> may also search the event graph <NUM> based on a second key prefix that includes the first four elements of the entity keys (the CID <NUM>, the AID <NUM>, the source vertex type <NUM>, and the source key <NUM>) to locate a specific vertex associated with the source key <NUM>. The event query host <NUM> may also search the event graph <NUM> based on a third key prefix that includes the first five elements of the entity keys (the CID <NUM>, the AID <NUM>, the source vertex type <NUM>, the source key <NUM>, and the edge type <NUM>) to locate all of the edges associated with the vertex identified by the source vertex type <NUM>. The event query host <NUM> may also search the event graph <NUM> based on a fourth key prefix that includes the first six elements of the entity keys (the CID <NUM>, the AID <NUM>, the source vertex type <NUM>, the source key <NUM>, the edge type <NUM>, and the timestamp <NUM>) to identify all of the edges associated with the vertex identified by the source vertex type <NUM>, arranged in time order. The event query host <NUM> may similarly search the event graph <NUM> based on other key prefixes that include larger numbers of elements of the entity keys, and/or other subsets of elements of the entity keys.

The entity keys, and other values, associated with entities of the event graph <NUM> stored in the database using binary packing. For example, rather than storing entity keys as blobs of data that may be hundreds of bytes, binary packing may allow each entity key to be represented using <NUM> bytes, or any other number of bytes. The entity keys and values associated with entities may also be compressed by the event query host <NUM>. In some examples, the event query host <NUM> may use a light compression algorithm to compress data for entities with recent timestamps, but use a heavier compression algorithm to more heavily compress data for older entities with timestamps older than a defined age threshold. Accordingly, older event data that may be less likely to be relevant to a query, and thus may be less likely be accessed by the query manager <NUM>, may be compressed in the event graph <NUM> more heavily than more recent event data.

In some examples, the event query host <NUM> may also be configured to delete or expire entities in the event graph <NUM> after a certain period of time, for instance based on a time-to-live (TTL) period. The event query host <NUM> may be configured to use the timestamps of entity keys to determine which entities can be deleted. As a non-limiting example, the event query host <NUM> may be configured to delete entries from the database that represent vertices or edges that, according to corresponding timestamps, are more than seven days old. Because the event graph <NUM> may be stored in local memory at the event query host <NUM>, as described herein, purging entries with timestamps older than a defined TTL period can limit the size of the event graph <NUM> stored in the local memory.

However, in some examples, the timestamp <NUM> of an entity may be updated by elements of the event query host <NUM>. For example, if a first vertex is added to the event graph <NUM> at a first time, the first time may be indicated in the corresponding timestamp <NUM> for the first vertex. However, if an edge and a second vertex, related to the first vertex, is later added to the event graph at a second time, the timestamp <NUM> of the first vertex may be updated to the second time. If a third vertex that is directly and/or indirectly related to the first vertex is later added to the event graph <NUM> at a third time, the timestamp <NUM> of the first vertex may be updated to the third time.

Accordingly, in some cases, if an entity continues to be related to other entities that were added to the event graph <NUM> more recently, the timestamp of the entity can be updated such that it can be stored in the event graph <NUM> for longer than a defined TTL period. As an example, if a first vertex was initially added to the event graph <NUM> eight days ago, but a related vertex or edge was added to the event graph <NUM> two days ago, the timestamp of the first vertex can have been updated to two days ago. The event query host <NUM> may thus maintain the eight-day-old first vertex in the event graph <NUM> because its timestamp was update to two days ago, even if the event query host <NUM> is configured to delete entities that have timestamps older than seven days. Accordingly, because the older first vertex may be related to the newer vertex or edge, and may potentially be part of event patterns or sub-graphs indicated by query criteria <NUM> for one or more queries <NUM>, the first vertex can be kept in the event graph <NUM> and be analyzed by the query manager <NUM> even if other entities added eight days ago, that were not found to be related to other newer entities, were deleted from the event graph <NUM> after seven days.

Information in the database about entities of the event graph <NUM>, such as the example data shown in <FIG>, may be accessed by the query manager <NUM> when the query manager <NUM> executes query instances <NUM>. For example, the query manager <NUM> may use entity keys, such as the entity key <NUM>, to identity vertices <NUM> that represent events and/or edges <NUM> that represent relationships between such events, as the query manager <NUM> searches the event graph <NUM> for sub-graphs or other query criteria <NUM> associated with query instances.

<FIG> shows an example <NUM> of query criteria <NUM> for a query that can be executed against the event graph <NUM>. As discussed above, the query criteria <NUM> for a query may indicate a pattern of one or more events that are relevant to the query, such as a pattern of events that may indicate malicious behavior on the computing device <NUM>. For example, the query criteria <NUM> may indicate a type of each event in the pattern, relationships between the events in the pattern, timeframes associated with relationships between the events in the pattern, and/or any other information about the pattern of events. This type of information may be expressed in a graph representation, similar to the graph representation of the event graph <NUM> discussed above with respect to <FIG>. For instance, query criteria <NUM> for a query may indicate information about one or more events in a pattern using corresponding vertices of a graph, as shown in <FIG>. Similarly, information about relationships between the events in the pattern can be represented using edges in the graph, as shown in <FIG>.

In example <NUM>, the query criteria <NUM> may be a pattern that includes four events represented in a graph by a first vertex <NUM>, a second vertex <NUM>, a third vertex <NUM>, and a fourth vertex <NUM>. The first vertex <NUM> may represent a first event in which a "RunDLL32. exe" begins executing on the computing device <NUM>. The second vertex <NUM> may represent a second event in which a network connection is opened from the computing device <NUM> to an external IP address. The third vertex <NUM> may represent a third event in which either a "powershell. exe" process or a "cmd. exe" process begins executing on the computing device <NUM>. The fourth vertex <NUM> may represent a fourth event in which any type of child process begins executing on the computing device <NUM>.

In the graph shown in <FIG>, the first vertex <NUM> and the second vertex <NUM> may be linked by a first edge <NUM>, the first vertex <NUM> and the third vertex <NUM> may be linked by a second edge <NUM>, and the third vertex <NUM> and the fourth vertex <NUM> may be linked by a third edge <NUM>. These edges may represent specific relationships between the events represented by the vertices, such as an indication that one event initiated another event. The vertices and/or the edges may also indicate timing criteria associated with the events.

For instance, overall, the graph shown in <FIG> may represent a pattern in query criteria <NUM> for a query that is satisfied if:.

If the query queue <NUM> includes a query instance associated with the graph shown in <FIG>, the query manager <NUM> may execute the query instance by performing graph traversal operations and/or graph isomorphism operations to attempt to find one or more sub-graphs, within the event graph <NUM>, that match the graph shown in <FIG>. For example, the query manager <NUM> may search for a vertex in the event graph <NUM> that indicates a launch of a "RunDLL32. exe" process, determine whether that vertex is linked in the event graph <NUM> by edges to other vertices indicating that the "RunDLL32. exe" process initiated an external network connection within <NUM> hours and also launched either a "powershell. exe" process or a "cmd. exe" process within thirty minutes of initiating the network connection, and also determine whether a vertex representing the "powershell. exe" process or the "cmd. exe" process is linked in the event graph <NUM> by another edge to a vertex representing a child process launched by the "powershell. exe" process or the "cmd. exe" process within thirty minutes of launch of the "powershell. exe" process or the "cmd. exe" process.

One of the events in the query criteria <NUM> may be the trigger event for the associated query that causes the event processor <NUM> to add a corresponding query instance <NUM> to the query queue <NUM>. For example, the "RunDLL32. exe" process event represented by the first vertex <NUM> may be the trigger event for the query shown in <FIG>. Accordingly, if the event processor <NUM> identifies a "RunDLL32. exe" process event in the event stream <NUM>, the event processor <NUM> may add a vertex that represents the "RunDLL32. exe" process event to the event graph <NUM>, and also add a query instance to the query queue <NUM> that is associated with the query criteria <NUM> shown in <FIG>.

In some examples, other elements of the query criteria <NUM> may or may not already be present in the event graph <NUM> when the event processor <NUM> identifies the trigger event and adds the query instance to the query queue <NUM>. For example, if event data arrives out-of-order in the event stream <NUM>, vertices <NUM> corresponding to one or more of the second vertex <NUM>, the third vertex <NUM>, and the fourth vertex <NUM> may already be present in the event graph <NUM> by the time the event processor <NUM> identifies the "RunDLL32. exe" process event in the event stream <NUM>. Accordingly, the query manager <NUM> may successfully locate all of the elements of the query criteria <NUM> in the event graph <NUM> when the query manager <NUM> first executes the query instance. The event query host <NUM> may accordingly output query results <NUM> indicating that a match for the query instance has been found in the event graph <NUM>.

However, if a trigger event arrives in the event stream <NUM> before one or more other elements of the query criteria <NUM>, it may be possible that not all of the other elements of the query criteria <NUM> are present within the event graph <NUM> when the query manager <NUM> executes the query instance at the scheduled execution time indicated in the query queue <NUM>. For example, if the "RunDLL32. exe" trigger event arrives before the events represented by the second vertex <NUM>, the third vertex <NUM>, and the fourth vertex <NUM>, the events represented by one or more of the second vertex <NUM>, the third vertex <NUM>, and the fourth vertex <NUM> may not yet be represented in the event graph <NUM> when the query manager <NUM> first attempts to find the pattern of events shown in <FIG> within the event graph <NUM>. In this situation, the query manager <NUM> may determine which of the elements of the query criteria <NUM> are present within the event graph <NUM>, store information associated with those elements of the query criteria <NUM> as a partial query state associated with the query instance, and reschedule the query instance with a later scheduled execution time in the query queue <NUM>.

For example, during a first execution of a query instance, the query manager <NUM> may find a "RunDLL32. exe" process event in the event graph <NUM> that matches the first vertex <NUM>, find an external network connection event in the event graph <NUM> that matches the second vertex <NUM>, and determine that the two events are related according to a relationship defined by the first edge <NUM>. However, during the first execution of the query instance, the query manager <NUM> may not find events or relationships in the event graph <NUM> that match the third vertex <NUM>, the fourth vertex <NUM>, the second edge <NUM>, and/or the third edge <NUM>. Accordingly, the query manager <NUM> may store partial query state information associated with the query instance indicating that matches for the first vertex <NUM>, the second vertex <NUM>, and the first edge <NUM> have been found in the event graph <NUM>.

Accordingly, when the query manager <NUM> executes the query instance again at the new scheduled execution time, the query manager <NUM> can use the partial query state to avoid searching for the previously found elements of the query criteria <NUM>, and instead search just for the remaining elements of the query criteria <NUM> that have not yet been found. For example, if the partial query state indicates that matches for the first vertex <NUM>, the second vertex <NUM>, and the first edge <NUM> were previously found in the event graph <NUM>, the query manager <NUM> can avoid searching for those elements again in the event graph <NUM>, and can instead search the event graph <NUM> specifically for matches for the third vertex <NUM>, the fourth vertex <NUM>, the second edge <NUM>, and the third edge <NUM>.

As another example, the trigger event for a query may be the child process event represented by the fourth vertex <NUM> shown in <FIG>, instead of the "RunDLL32. exe" process event represented by the first vertex <NUM>, because the full event pattern shown in <FIG> may be more likely to be present in the event graph <NUM> after an entity representing a child process of a "powershell. exe" process or a "cmd. exe" process has been added to the event graph <NUM>. Accordingly, in this example, if the event processor <NUM> identifies an event associated with a child process of a "powershell. exe" process or a "cmd. exe" process in the event stream <NUM>, the event processor <NUM> may add a vertex that represents the child process event to the event graph <NUM>, and also add a query instance to the query queue <NUM> that is associated with the query criteria <NUM> shown in <FIG>. However, if event data arrives out-of-order as discussed above, it may still be possible that not all of the other elements shown in <FIG> are present within the event graph <NUM> when the query manager <NUM> executes the query instance at the scheduled execution time indicated in the query queue <NUM>. For instance, although information about the child process of a "powershell. exe" process or a "cmd. exe" process may have arrived by the scheduled execution time for the query instance, is possible that the event query host <NUM> has not yet received information about a parent "RunDLL32. exe" process event or a corresponding external network connection event. Accordingly, the query manager <NUM> may store partial query state information indicating that some portions of the pattern shown in <FIG> have already been found in the event graph <NUM>, such that the query manager <NUM> can avoid searching for those elements again in the event graph <NUM> during the next execution of the query instance.

If the combination of the partial query state and results of the new search indicate that all of the elements of the query criteria <NUM> are, and/or were, present in the event graph <NUM>, the event query host <NUM> may accordingly output query results <NUM> indicating that a match for the query instance has been found in the event graph <NUM>. If the query manager <NUM> is again unable to find all of the elements of the query criteria <NUM>, the query manager <NUM> may update the partial query state based on any additional elements that were found, and reschedule the query attempt for another later scheduled execution time.

Multiple query instances <NUM> may, in some cases, be associated with query criteria <NUM> that has one or more shared elements. For example, two or more query instances <NUM> may be associated with graphs that may have one or more shared entities. In these examples, if the query manager <NUM> is executing a particular query instance and finds an entity in the event graph <NUM> that matches query criteria <NUM> for that particular query instance, as well as query criteria <NUM> for one or more other query instances <NUM> in the query queue <NUM> that the query manager <NUM> is not currently executing, the query manager <NUM> may be configured to modify partial query states <NUM> of the other query instances <NUM> to indicate that the matching entity has been found. As a non-limiting example, query instance 112A and query instance 112B may both be associated with an event pattern that looks for a "RunDLL32. exe" process, although other elements of the event patterns may differ. In this example, if the query manager <NUM> finds a "RunDLL32. exe" process when executing query instance 112B, the query manager <NUM> may be configured to modify the partial query state 134A for query instance 112A to indicate that the "RunDLL32. exe" process has been found in the event graph <NUM>, even though the query manager <NUM> was not executing query instance 112A. Accordingly, the query manager <NUM> can avoid searching the event graph <NUM> for the "RunDLL32. exe" process again when query instance 112A is later executed.

Although the event query host <NUM> shown in <FIG> may be associated with the computing device <NUM>, in some examples the event query host <NUM> may also be associated with one or more additional computing devices. In some examples, the event query host <NUM> may maintain different event graphs, and/or different query queues, for each of the computing devices. In other examples, the event graph <NUM> may contain event data associated with multiple computing devices. For instance, data associated with entities in the event graph <NUM> may be associated with the CID <NUM> and/or AID <NUM> discussed above to distinguish entities in the event graph <NUM> that are associated with different customers and/or sensors. Accordingly, in some examples, one event query host may process event data associated with multiple computing devices. Additionally, in some examples, multiple event query hosts may each be associated with different sets of computing devices, as discussed below with respect to <FIG>.

<FIG> shows an example <NUM> in which the security system includes multiple event query hosts, such as event query host 102A, event query host 102B, and event query host 102C, as well as a resequencer <NUM> configured to process an input event stream <NUM>. The input event stream <NUM> can include event data sent to the security system by local sensors on one or more computing devices. The local sensors may send the event data to the security system over temporary or persistent connections. A termination service or process of the security system (not shown) can receive event data transmitted by multiple sensors, and can provide the collected event data to the resequencer <NUM> as the input event stream <NUM>.

The event data in the input event stream <NUM> may be in a random or pseudorandom order when it is received by the resequencer <NUM>. For example, event data for different events may arrive at the resequencer <NUM> in the input event stream <NUM> in any order, without regard for when the events occurred on computing devices. As another example, event data from local sensors on different computing devices may be mixed together within the input event stream <NUM> when they are received by the resequencer <NUM>, without being sorted based on sensor identifiers. However, the resequencer <NUM> can perform various operations to sort and route the event data to different event query hosts.

The different event query hosts can be associated with different shards within the security system. Each shard can be a distinct instance that includes a distinct event query host. As discussed above, each distinct event query host can also locally store at least one event graph and locally execute queries <NUM> against the locally-stored event graph. Each shard may be associated with a unique shard identifier.

Each shard, including a distinct event query host, may be associated with a distinct set of computing devices and/or a set of sensors executing on those computing devices. Each of the sensors may be associated with a unique sensor identifier, such as the AID <NUM> discussed above. Each shard, and its event query host, may be associated with a particular range of sensor identifiers or a particular set of sensor identifiers, and accordingly be associated with a set of corresponding computing devices. As such, each individual computing device may be associated with a particular shard, and a particular one of the event query hosts, in the security system. As a non-limiting example, a first computing device may be associated with event query host 102A, and event query host 102A may maintain a first event graph associated with events that occurred on the first computing device. A second computing device may instead be associated with event query host 102B, and event query host 102B may maintain a distinct second event graph associated with events that occurred on the second computing device.

The resequencer <NUM> can be configured to sort and/or route event data from the input event stream <NUM> into distinct shard topics <NUM> associated with the different shards, such as shard topic 506A associated with event query host 102A, shard topic 506B associated with event query host 102B, and shard topic 506C associated with event query host 102C. The shard topics <NUM> can be queues or sub-streams of event data, such as the event stream <NUM> discussed above, that are associated with the corresponding shards. Event data sorted into a shard topic can be processed, as the event stream <NUM>, by the corresponding event query host <NUM>. Accordingly, although the input event stream <NUM> may include event data from numerous computing devices, the resequencer <NUM> can sort the input event stream <NUM> and provide each of the event query hosts with event streams that include data about events that occurred on the specific sets of computing devices associated with each of those event query hosts.

Because the resequencer <NUM> can cause each shard to receive event data from sensors specifically associated with that shard, an event query host in a particular shard can locally store one or more event graphs that represent events that occurred on computing devices associated with that shard. Event data associated with a single computing device can thus be stored in a single event graph associated with a single event query host, for example as shown in <FIG>. Accordingly, each event query host can locally execute query instances against a locally-stored event graph, without transmitting queries over a network to a cloud database or other remote or centralized database of event data.

In some examples, the resequencer <NUM> can determine which shard is associated with an instance of event data in the input event stream based on an AID or other identifier of the sensor that sent the event data. For example, the resequencer <NUM> can perform a modulo operation to divide an AID value, associated with an instance of event data, by the number of shards, find the remainder of the division, and find a shard with an identifier that matches the remainder. As an example, if there are ten thousand shards in the security system, and a remainder of a modulo operation on the AID of a sending sensor is "<NUM>," the resequencer <NUM> can determine that the sending sensor is associated with a shard having an identifier of "<NUM>. " The resequencer <NUM> can route the event data into a shard topic associated with shard "<NUM>," such that the event data can be received and processed by the event query host associated with shard "<NUM>.

The resequencer <NUM> may also, or alternately, use a consistent hashing ring to determine which shard is associated with an instance of event data in the input event stream, as a fallback or alternate option to the modulo operation discussed above. For instance, if the number of shards is changed from a fixed number, the modulo operation performed on a sensor identifier value as discussed above may generate a different remainder, and thus may no longer correspond with an identifier of the shard associated with the sensor. However, even if the number of shards (and thus the number of event query hosts) changes, consistent hashing can be used to identify shard associated with particular sensors.

In some examples, the security system may expand the number of shards, and the number of corresponding event query hosts, by spinning up multiple instances of the security system. Each system instance may have a fixed number of shards, such that the shard associated with a sensor can be identified from a sensor identifier using the modulo operation discussed above. For example, each system instance may have <NUM> shards, such that two system instances may have <NUM> shards in total. Shard identifiers may be unique within each system instance, but may be re-used in different system instances. Accordingly, a particular sensor on a computing device may be associated with a particular instance, as well as a particular shard within that instance. As a non-limiting example, the resequencer <NUM> may be configured to determine that event data in the input event stream <NUM> is associated with a CID and/or AID mapped to a second system instance, and also use a modulo operation to determine that the AID corresponds to shard #<NUM> in the second system instance.

The security network may, in some examples, include a cluster of resequencers that are associated with different shards. A resequencer, within the cluster, that receives or first operates on an instance of event data in the input event stream <NUM> may determine, based on a sensor identifier, whether that resequencer is part of the shard associated with the sensor that sent the event data. If the receiving resequencer is part of the shard associated with the sending sensor, the resequencer can route the event data to the shard topic for that shard. If the resequencer that initially processes the instance of event data instead determines that it is not part of the shard associated with the sending sensor, the resequencer can forward the event data to a different resequencer in the cluster that is part of the shard associated with the sending sensor. In some examples, a resequencer can send event data to another resequencer in the cluster via a remote procedure command (RPC) connection or channel.

In other examples, the security network may have a fleet of resequencer hosts associated with multiple sets of shards and multiple clusters of event query hosts. In these examples, the fleet of resequencer hosts may receive event data, and process a CID associated with the event data to identify which cluster of event query hosts is associated with the CID. The fleet of resequencer hosts may also hash an AID associated with the event data to identify a particular shard associated with the AID within the identified cluster of event query hosts. The fleet of resequencer hosts can accordingly forward the event data as part of the identified shard in association with the identified cluster of event query hosts, such that the event data is received by the particular event query host that corresponds with the shard identified by the AID, in the cluster identified by the CID.

The event query hosts associated with the shards may each locally store event graphs, queries, query queues, and/or other data in local databases. However, in some examples, an event query host associated with one shard may periodically or occasionally transmit a copy of state data associated with the locally-stored information to one or more other event query hosts associated with other shards. State data associated with one event query host may accordingly be stored at one or more other event query hosts for fault tolerance and/or backup purposes.

As a non-limiting example, event query host 102A may provide state data, associated with data stored locally by event query host 102A, to event query host 102B. If event query host 102A goes offline or experiences other errors, event query host 102B or another event query host can be configured as a replacement for event query host 102A, based on the stored state data associated with event query host 102A. For instance, a replacement event query host can instantiate a replacement event graph and a replacement query queue based on the stored state data associated with event query host 102A. The replacement event query host can thus be loaded with a full local copy of the event graph and query queue that had been stored by the event query host 102A, and the replacement event query host can thereby take over for event query host 102A and process new event data in the shard topic 506A.

One or more event query hosts can execute processes associated with the event processor <NUM> and the query manager <NUM>. Examples of such processes are shown and described with respect to <FIG>, <FIG>, and <FIG>.

<FIG> shows a flowchart of an example process <NUM> for modifying the event graph <NUM>, and adding query instances to the query queue <NUM>, substantially in real-time based on the event stream <NUM>. The example process <NUM> shown in <FIG> may be performed by a computing system that executes the event processor <NUM> as part of the event query host <NUM>, such as the computing system shown and described with respect to <FIG>.

At block <NUM>, the event processor <NUM> can identify an event data instance. For example, the event processor <NUM> may identify an event data instance within the event stream <NUM> received by the event query host <NUM>. As discussed above, the event stream <NUM> can be a data stream that indicates events, detected by the sensor <NUM>, that have occurred on the computing device <NUM>. Accordingly, at block <NUM>, the event processor <NUM> can identify an individual instance of event data indicated by information within the event stream <NUM>. In some examples, the event processor <NUM> may receive event streams, associated with multiple computing devices and sensors, within a shard topic, as discussed above with respect to <FIG>. The event processor <NUM> may accordingly identify an event data instance, associated with one of those computing devices, within the shard topic at block <NUM>.

At block <NUM>, the event processor <NUM> can add one or more entities to the event graph <NUM> that are associated with the event data instance identified at block <NUM>. For example, the event processor <NUM> can add a vertex to the event graph <NUM> that represents the event data instance, and/or add an edge to the event graph <NUM> that represents a relationship between events represented vertices <NUM> in the event graph <NUM>. The event processor <NUM> may add an entity to the event graph <NUM> at block <NUM> by adding an entry to a database, as discussed above with respect to <FIG>.

At block <NUM>, the event processor <NUM> can determine whether the event data instance is a trigger event associated with a query. As discussed above, the event query host <NUM> can be configured with query definitions <NUM> for one or more queries <NUM>, including indications of trigger events <NUM> for the queries <NUM>. The event processor <NUM> can accordingly use the query definitions <NUM> to determine whether the event data instance, identified at block <NUM>, matches a trigger event for a query. A trigger event for a query may be associated with an event type, and/or one of more filters, as discussed above.

If the event data instance identified at block <NUM> does not match a trigger event for any of the queries (Block <NUM> - No), the event processor <NUM> can return to block <NUM>, after adding a representation of the event data instance to the event graph <NUM>, and process a subsequent instance of event data within the event stream <NUM>. However, if the event data instance identified at block <NUM> does match a trigger event for a query (Block <NUM> - Yes), the event processor <NUM> can add a corresponding query instance to the query queue <NUM>. The event processor <NUM> may add the new query instance to the query queue <NUM> with a scheduled execution time selected based on a default scheduling configuration, based on a rescheduling scheme associated with the query, or based on any other scheduling configuration. The event processor <NUM> can then return to block <NUM>, and process a subsequent instance of event data within the event stream <NUM>.

Overall, as shown in <FIG>, the event processor <NUM> may add a representation of each identified event data instance, substantially in real-time as the event data is received and processed by the event processor <NUM>. The event processor <NUM> may also, substantially in real-time as the event data is received and processed by the event processor <NUM>, add query instances <NUM> to the query queue <NUM> that are associated with event data instances that correspond to trigger events for queries <NUM>, but avoid adding query instances <NUM> to the query queue <NUM> that are associated with instances of event data that do not correspond to trigger events <NUM> for queries <NUM>. Accordingly, the query instances <NUM> that are scheduled within the query queue <NUM> by the event processor <NUM> at block <NUM> can be likely to be at least partially satisfied when executed by the query manager <NUM>, because event data corresponding to trigger events <NUM> for those query instances <NUM> was added to the event graph <NUM> at block <NUM>.

<FIG> shows a flowchart of an example process <NUM> for executing, at scheduled execution times <NUM>, query instances <NUM> in the query queue <NUM>. The example process <NUM> shown in <FIG> may be performed by a computing system that executes the query manager <NUM> as part of the event query host <NUM>, such as the computing device shown and described with respect to <FIG>.

At block <NUM>, the query manager <NUM> may maintain the query queue <NUM>. As discussed above, the query queue <NUM> may be an ordered list or database of query instances <NUM> sorted by scheduled execution times <NUM>. For example, the highest-priority query instance in the query queue <NUM> may be the query instance with the next scheduled execution time.

At block <NUM>, the query manager <NUM> can determine if it is the scheduled execution time for a query instance in the query queue <NUM>. For example, if it is not yet the scheduled execution time for the highest-priority query instance in the query queue <NUM>, the query manager <NUM> can continue to maintain the query queue <NUM> at block <NUM> until the scheduled execution time for the highest-priority query instance in the query queue <NUM>.

At the scheduled execution time for a query instance in the query queue, the query manager <NUM> may execute the query instance at block <NUM> by traversing the event graph <NUM> and searching for one or more entities in the event graph <NUM> that correspond with the query criteria <NUM> of the query instance. The query criteria <NUM> may be a pattern of one or more events, for instance as described above with respect to the example shown in <FIG>. As a non-limiting example, at block <NUM> the query manager <NUM> can use graph isomorphism principles and/or perform graph traversal operations to search for one or more sub-graphs, within the event graph <NUM>, that match a graph of events associated with the query instance.

In some examples, if the query instance is associated with a partial query state that indicates portions of the query criteria <NUM> previously found in the event graph <NUM>, the query manager <NUM> may avoid searching the event graph <NUM> for the previously found portions of the query criteria <NUM>. The query manager <NUM> may instead attempt to locate other portions of the query criteria <NUM> that have not yet been found in the event graph <NUM>, but would satisfy the query criteria <NUM> in combination with the partial query state.

At block <NUM>, the query manager <NUM> can determine if the query instance has been satisfied. For example, query manager <NUM> can determine if all of the elements of the query criteria <NUM> associated with the query instance have been found in the event graph <NUM>, either based on the search performed at block <NUM> and/or in combination with a prior partial query state associated with the query instance. If all of the elements of the query criteria <NUM> associated with the query instance have been found in the event graph <NUM>, the query manager <NUM> can determine if the query instance has been satisfied (Block <NUM> - Yes) and can output corresponding query results <NUM> at block <NUM>.

However, if the query manager <NUM> determine that the query instance has not yet been satisfied (Block <NUM> - No), the query manager <NUM> may store the partial query state associated with the query instance. For example, if one or more portions of the query criteria <NUM> were found in the event graph <NUM> during the search performed at block <NUM>, the query manager <NUM> may store those portions as a new partial query state associated with the query instance, or add the newly located portions to a previously-stored partial query state associated with the query instance.

At block <NUM>, the query manager <NUM> can reschedule the query instance within the query queue <NUM>, based on the rescheduling scheme associated with the query instance. For instance, if the query instance is associated with query 110A shown in <FIG>, the rescheduling scheme 132A may indicate that <NUM>% of the query instances associated with query 110A have historically been satisfied within the event graph <NUM> within five minutes. Accordingly, in some examples, the query manager <NUM> can be configured to adjust the scheduled execution time of the query instance such that the query instance is scheduled to be re-executed five minutes from the current time, or is scheduled to be re-executed during a window of time surrounding five minutes from the current time. In other examples, the query manager <NUM> can be configured to reschedule the query instance to be re-executed five minutes, or within a window of time surrounding the five-minute mark, after the query instance was initially added to the query queue <NUM>.

The query manager <NUM> can, after rescheduling the query instance at block <NUM>, return to block <NUM> and <NUM> to determine when it is the scheduled execution time for the next query instance in the query queue <NUM>. The query manager <NUM> can accordingly execute query instances <NUM> in the query queue <NUM> at different execution times that are determined based on rescheduling schemes <NUM> associated with the query instances <NUM>.

<FIG> shows a flowchart of an example process <NUM> for determining rescheduling schemes <NUM> associated with queries <NUM>. The example process <NUM> shown in <FIG> may be performed by a computing system that executes the query manager <NUM> as part of the event query host <NUM>, such as the computing device shown and described with respect to <FIG>.

At block <NUM>, the query manager <NUM> can use a default rescheduling scheme associated with a particular query to reschedule any query instances <NUM>, associated with the particular query, that were executed but not satisfied. In some examples, the default rescheduling scheme associated with the particular query may indicate that any query instances that are not satisfied should be re-executed every minute, or on any other consistent basis. In other examples, the default rescheduling scheme associated with the particular query may indicate that any query instances that are not satisfied should be re-executed after varying wait times selected according to an exponential backoff scheme, or any other default rescheduling scheme.

At block <NUM>, the query manager <NUM> can monitor and collect durations of time that it takes for query instances <NUM>, associated with the particular query, to be satisfied. For example, when the query manager <NUM> uses the process <NUM> shown in <FIG> to execute query instances, the query manager <NUM> may determine how long it takes for each of the query instances to be satisfied at block <NUM>, either during an initial execution attempt or after one or more subsequent execution attempts after changes to scheduled execution times <NUM> at block <NUM>.

At block <NUM>, the query manager <NUM> can determine if at least a threshold number of time durations, associated with the query instances, has been collected while looping through block <NUM> and block <NUM>. The threshold number of time durations may be a predefined value, such as <NUM>, <NUM>, <NUM>, <NUM>, or any other number of time durations. If fewer than the threshold number of time durations has been collected (Block <NUM> - No), the query manager <NUM> can continue to reschedule query instances <NUM> associated with the particular query according to the default rescheduling scheme at block <NUM>, and can continue collecting corresponding time durations until those query instances <NUM> are satisfied at block <NUM>.

However, if at least the threshold number of time durations, for the query instances to be satisfied, has been collected (Block <NUM> - Yes), the query manager <NUM> can determine a new rescheduling scheme at block <NUM> based on the historical time durations collected over time. As discussed above, the query manager <NUM> can use statistical analysis, machine learning, and/or any other technique to evaluate the collected historical information about how long it took for prior query instances to be satisfied, and to generate a new rescheduling scheme for the particular query based on that analysis. For example, the query manager <NUM> may determine that it takes three minutes on average for instances of the particular query to be satisfied, or that according to a <NUM>% percentile metric, <NUM>% of prior instances of the particular query were satisfied within five minutes.

Accordingly, at block <NUM>, the query manager <NUM> may reschedule subsequent unsuccessful query instances <NUM> associated with the particular query within a time window associated with the rescheduling scheme determined at block <NUM>. For example, if the query manager <NUM> determined that it takes three minutes on average for instances of the particular query to succeed, the query manager <NUM> can reschedule any additional instances of the particular query based on a time window surrounding the average three-minute success time, such as resetting the scheduled execution times <NUM> of the query instances based on any wait times within a two to four-minute window.

At block <NUM>, the query manager <NUM> can continue to monitor and collect durations of time that it takes for query instances <NUM> to be satisfied, similar to block <NUM>. The query manager <NUM> can also refine the rescheduling scheme at block <NUM>, based on additional historical time durations collected at block <NUM>. Accordingly, after initially determining the rescheduling scheme at block <NUM>, the query manager <NUM> may continue to collect new historical information at block <NUM> about times it takes for query instances to be satisfied. As such, the query manager <NUM> can determine at block <NUM> whether to adjust the rescheduling scheme to be associated with higher or lower wait times, based on the additional historical information collected at block <NUM>.

<FIG> shows an example system architecture <NUM> for a computing system <NUM> associated with the event query host <NUM> described herein. The computing system <NUM> can be a server, computer, or other type of computing device that executes one or more event query hosts. In some examples, the event query host <NUM> can be executed by a dedicated computing system <NUM>. In other examples, the computing system <NUM> can execute one or more event query hosts via virtual machines or other virtualized instances. For instance, the computing system <NUM> may execute multiple event query hosts in parallel, as shown in <FIG>, using different virtual machines, parallel threads, or other parallelization techniques.

The computing system <NUM> can include memory <NUM>. In various examples, the memory <NUM> can include system memory, which may be volatile (such as RAM), non-volatile (such as ROM, flash memory, non-volatile memory express (NVMe), etc.) or some combination of the two. The memory <NUM> can further include non-transitory computer-readable media, such as volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data. System memory, removable storage, and non-removable storage are all examples of non-transitory computer-readable media. Examples of non-transitory computer-readable media include, but are not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile discs (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other non-transitory medium which can be used to store desired information and which can be accessed by the computing system <NUM>. Any such non-transitory computer-readable media may be part of the computing system <NUM>.

The memory <NUM> can store data associated with the event graph <NUM>, the query definitions <NUM>, the query queue <NUM>, the event processor <NUM>, the query manager <NUM>, and/or any other element of the event query host. As discussed above, the event graph <NUM> may be stored locally in the memory <NUM> such that the event processor <NUM> and/or the query manager <NUM> can locally interact with the event graph <NUM>. The memory <NUM> can also store other modules and data <NUM>. The modules and data <NUM> can include any other modules and/or data that can be utilized by the computing system <NUM> to perform or enable performing the actions described herein. Such other modules and data can include a platform, operating system, and applications, and data utilized by the platform, operating system, and applications.

By way of a non-limiting example, the computing system <NUM> that executes the event query host <NUM> may have non-volatile memory, such as an NVMe disk configured to store the event graph <NUM>, the query definitions <NUM>, the query queue <NUM>, and/or other data associated with the event query host. The computing system <NUM> that executes the event query host <NUM> may also have volatile memory, such as synchronous dynamic RAM (SDRAM), double data rate (DDR) SDRAM, DDR2 SDRAM, DDR3 SDRAM, or DD4 SDRAM.

The computing system <NUM> can also have one or more processors <NUM>. In various examples, each of the processors <NUM> can be a central processing unit (CPU), a graphics processing unit (GPU), both a CPU and a GPU, or any other type of processing unit. For example, each the processors <NUM> may be a <NUM>-core CPU, or any other type of processor. Each of the one or more processors <NUM> may have numerous arithmetic logic units (ALUs) that perform arithmetic and logical operations, as well as one or more control units (CUs) that extract instructions and stored content from processor cache memory, and then executes these instructions by calling on the ALUs, as necessary, during program execution. The processors <NUM> may also be responsible for executing computer applications stored in the memory <NUM>, which can be associated with types of volatile and/or nonvolatile memory.

The computing system <NUM> can also have one or more communication interfaces <NUM>. The communication interfaces <NUM> can include transceivers, modems, interfaces, antennas, telephone connections, and/or other components that can transmit and/or receive data over networks, telephone lines, or other connections. For example, the communication interfaces <NUM> can include one or more network cards that can be used to receive the event stream <NUM> and/or output query results <NUM>.

In some examples, the computing system <NUM> can also have one or more input devices <NUM>, such as a keyboard, a mouse, a touch-sensitive display, voice input device, etc., and/or one or more output devices <NUM> such as a display, speakers, a printer, etc. These devices are well known in the art and need not be discussed at length here.

The computing system <NUM> may also include a drive unit <NUM> including a machine readable medium <NUM>. The machine readable medium <NUM> can store one or more sets of instructions, such as software or firmware, that embodies any one or more of the methodologies or functions described herein. The instructions can also reside, completely or at least partially, within the memory <NUM>, processor(s) <NUM>, and/or communication interface(s) <NUM> during execution thereof by the computing system <NUM>. The memory <NUM> and the processor(s) <NUM> also can constitute machine readable media <NUM>.

Claim 1:
A computer-implemented method, comprising:
identifying (<NUM>), by one or more processors (<NUM>) of a computing system (<NUM>, <NUM>), an event that occurred on a computing device (<NUM>);
incorporating (<NUM>), by the one or more processors, information associated with the event into an event graph (<NUM>);
determining (<NUM>), by the one or more processors, that the event corresponds with a trigger event (<NUM>, 126A, 126B) associated with a query (<NUM>, 110A, 110B);
in response to the determining
adding (<NUM>, <NUM>), by the one or more processors, a query instance (<NUM>, 112A, 112B, 112C) associated with the query to a query queue (<NUM>) based on determining that the event corresponds with the trigger event, wherein the query queue (<NUM>) is an ordered list, which comprises a plurality of query instances (<NUM>, 112A, 112B, 112C) sorted based on scheduled execution times (<NUM>, 116A, 116B, 116C); and
executing, by the one or more processors, the query instance at a scheduled execution time associated with the query instance by identifying an event pattern associated with the query, and searching (<NUM>, <NUM>) the event graph for a sub-graph that matches the event pattern.