# US 12,182,256 B1 · Provenance graph-oriented host intrusion detection method and system, and storage medium

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,182,256 B1
- Document ID: US12182256B1
- Status: Granted
- Kind: B1
- Application number: 18/695,628
- Filed: 2023-08-09
- Published: 2025-01-09
- Granted: 2024-12-31
- Earliest claimed: 2023-07-04
- Assignees: Huazhong University of Science and Technology
- Applicants: Huazhong University of Science and Technology
- Inventors: Yulai Xie; Shuangbiao Dai; Dan Feng
- Web page: https://patentgrep.com/patent/US12182256B1

## CPC

- G06F 21/55: Detecting local intrusion or implementing counter-measures
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The present invention discloses a provenance graph-oriented host intrusion detection method and system, and a storage medium, which relates to the field of cyber security. The method includes: S1, acquiring provenance data of a host to be tested, to construct a provenance graph representing user behaviors; S2, mapping nodes in the provenance graph to roles, constructing a node feature matrix composed of feature vectors which can be used to represent attribute features, structural features, and inter-node interactive relationship of the nodes in the provenance graph, and mapping nodes having similar feature vectors to the same role; S3, performing an attention-guided attribute temporal random walk by comprehensively considering attributes of the nodes in the provenance graph, the temporal relationship between edges, and an attention parameter between different roles; and S4, converting the acquired attribute temporal random walk sequence into an embedding vector to extract a feature of the provenance graph, and performing intrusion anomaly detection. The present invention can perform deep representation learning on provenance data, reduce the workload of training a detection model, and improve the accuracy and efficiency of intrusion detection.

## Claims

### Claim 1

A provenance graph-oriented host intrusion detection method, the method comprising:
S1, acquiring provenance data of a host to be tested, and constructing a provenance graph representing user behaviors based on the provenance data;
S2, mapping nodes in the provenance graph to roles, constructing a node feature matrix composed of feature vectors used to represent attribute features, structural features, and inter-node interactive relationship of the nodes in the provenance graph, and mapping nodes in the node feature matrix having similar feature vectors to the same role;
S3, performing an attention-guided attribute temporal random walk on the provenance graph, and generating an attribute temporal random walk sequence the starting point of which is a current node vi, and the length of which is L: ϕ(Xi1), ϕ(Xi2), . . . , ϕ(XiL), where xi is the feature vector of the node vi; Φ(X) represents a function for mapping a node to a role, where (vit, vit+1)∈ET, 1 «t «L and T(vit, vit+1)«T(vit+1, vit+2), and (vit, vit+1) is an edge connected between a node vit and a next node vit+1; ET is a set composed of all edges in the provenance graph; t is a sequence number in the attribute temporal random walk sequence; and T(vit, vit+1)«T(vit+1, vit+2) indicates that a creation time of the edge between nodes vit and vit+1 is earlier than the creation time of the edge between nodes vit+1 and vit+2; and
the current node walks to neighbor nodes corresponding to different roles at different probabilities, the probabilities being an attention parameter between the roles, and being used to reflect the importance between the roles; and
S4, converting the attribute temporal random walk sequence into an embedding vector to extract a feature of the provenance graph, and performing intrusion anomaly detection by inputting the embedding vector to a pretrained intrusion detection model.

### Claim 2 (depends on 1)

The method according to claim 1, wherein in S3, the attention parameter between the roles is represented by means of a role attention matrix M, and an acquisition method of the role attention matrix M comprises:
S301, setting equal transition probabilities of the roles as a current role attention matrix M having element Mij, wherein i represents i-th row and j represents j-th column of the current role attention matrix M;
S302, using the current role attention matrix M to perform the attention-guided attribute temporal random walk to acquire an embedding vector ei of a current node vi and embedding vectors eN corresponding to all neighbor nodes of the current node;
S303, using the embedding vectors ei and eN to update the current role attention matrix M:
M
i
⁢
j
=
softmax
(
δ
⁡
(
w
j
,
w
i
)
)
=
exp
⁢
(
δ
⁡
(
w
j
,
w
i
)
)
∑
w
r
⁢
ϵ
⁢
R
i
⁢
exp
⁢
(
δ
⁡
(
w
r
,
w
i
)
)
δ(wj,wi)=mean({ej,ej∈eN and vj∈Nwj})·ei
where softmax represents a normalization operator, wi represents the role corresponding to the current node vi, wj represents an element in a role set corresponding to all the neighbor nodes' roles of the current node vi, δ(wj, wi) represents the importance of the role wj to the role wi, ei is the embedding vector corresponding to the current node vi, Nwj represents a set of nodes in the neighbor nodes which belongs to the role wj, and the mean function is used to aggregate embedding vectors corresponding to the same type of role in the sequence; and
S304, repeating S302 and S303, until the role attention matrix M becomes stable, thereby acquiring the needed role attention matrix M.

### Claim 3 (depends on 2)

The method according to claim 2, wherein in S304, the number of roles for which the transition probability change exceeds a predefined first threshold is acquired by calculating the distance between two role attention matrices acquired by two consecutive iterations of executing S302 and S303, and if the number is less than a predefined second threshold, the role attention matrix M becomes stable.

### Claim 4 (depends on 1)

The method according to claim 1, wherein in S4, the attribute temporal random walk sequence is inputted to a SkipGram model to calculate an embedding vector of each node.

### Claim 5 (depends on 1)

The method according to claim 1, wherein the function ϕ(x) for mapping nodes to roles is a binary operator or a k-means clustering function.

### Claim 6 (depends on 1)

The method according to claim 1, wherein after the provenance data of the host to be tested is acquired, S1 further comprises: filtering out provenance data unrelated to intrusion behavior, and removing nodes having a same attribute feature.

### Claim 7 (depends on 1)

The method according to claim 1, wherein the nodes in the provenance graph are used to represent data objects of the host to be tested, and the data objects comprise a progress, file, socket, and pipeline.

### Claim 8 (depends on 1)

A provenance graph-oriented host intrusion detection system being configured to perform the method according to claim 1, the system including a host computer and comprising:
a provenance graph construction module configured to acquire provenance data of the host computer to be tested, and to construct a provenance graph representing user behaviors based on the provenance data;
a role mapping module configured to map nodes in the provenance graph to roles, construct a node feature matrix composed of feature vectors used to represent attribute features, structural features, and inter-node interactive relationship of the nodes in the provenance graph, and map nodes in the node feature matrix having similar feature vectors to the same role;
a random walk module configured to perform an attention-guided attribute temporal random walk on the provenance graph, and generate an attribute temporal random walk sequence the starting point of which is a current node vi and the length of which is L: ϕ(Xi1), ϕ(Xi1), . . . , ϕ(XiL), where xi is the feature vector of the node
vi; Φ(X) represents a function for mapping a node to a role, where (vit, vit+1)∈ET, 1«t «L and T(vit, vit+1)«T(vit+1, vit+2), and (vit, vit+1) is an edge connected between a node vit and a next node vit+1; ET is a set composed of all edges in the provenance graph; t is a sequence number in the attribute temporal random walk sequence; and T(vit, vit+1)«T(vit+1, vit+2) indicates that a creation time of the edge between nodes vit and vit+1 is earlier than the creation time of the edge between nodes vit+1 and vit+2; and
the current node walks to neighbor nodes corresponding to different roles at different probabilities, the probabilities being an attention parameter between the roles, and being used to reflect the importance between the roles; and
an anomaly detection module configured to convert the attribute temporal random walk sequence into an embedding vector to extract a feature of the provenance graph, and perform intrusion anomaly detection by inputting the embedding vector to a pretrained intrusion detection model.

### Claim 9 (depends on 1)

A non-transitory computer-readable storage medium, comprising a stored computer program; when executed by a processor, the computer program controls a device in which the computer-readable storage medium is located to perform the provenance graph-oriented host intrusion detection method according to claim 1.