Table of Contents
- Introduction
- Tarjan Algorithm
- SCM_RIGHTS and Garbage Collection
- Unix_streamsendmsg Function
- Unix_accept Function
- Unix_gc Function
- Root-cause Analysis
- Patch
- References
Introduction #
리눅스 커널 6.10 버전에서 Unix Socket garbage collection에 Tarjan algorithm이 적용되었다. 본 취약점은 strongly connected components (SCC) index를 갖는 멤버 변수인 scc_index를 초기화하지 않는 실행 경로가 있어 발생하였다. 본 글에서는 리눅스 커널 버전 6.1.158을 기준으로 이 취약점을 살펴본다[1, 4].
Tarjan Algorithm #
Tarjan algorithm은 이 취약점에서 문제가 되는 strongly connected components를 결정하는 알고리즘이다. 먼저 DFS를 하면서 카운터를 0부터 하나씩 증가시켜나간다. 이를 dfs_num이라고 하자. 이때 low link라고 해서 dfs_low도 정의하는데 이는 한 vertex에서 도달가능한, 가장 낮은 dfs_num이다. 그럼 같은 dfs_low를 갖는 부분 그래프들이 있는 것을 볼 수 있다. 이를 strongly connected components라고 부른다. 이는 어떤 vertex에서 DFS를 시작하느냐에 따라 달라진다. 이를 해결하기 위해 스택을 도입한다[5, 6].
DFS를 할 때 dfs_num과 dfs_low를 같이 증가시켜나가고, 스택에 푸시한다. 그리고 이미 방문한 곳을 다시 방문할 때 두 dfs_num을 비교하여 작은 것으로 dfs_low를 갱신한다. 이 갱신은 매번 수행되는데, 이때 갱신된 dfs_low와 dfs_num이 같다면, 가장 낮은 dfs_num을 찾은 것이므로 우리는 SCC를 발견한 것이다. 그럼 SCC 그룹에 해당하는 것들은 스택에서 팝한다. 이렇게 하면 SCC group을 자동으로 구분하여 관리할 수 있다[5].
SCM_RIGHTS and Garbage Collection #
Unix socket garbage collection (Unix GC)은 한 시스템 내에서 프로세스 간 통신에 사용되는 unix-domain sockets (AF_UNIX)에 대한 garbage collection을 수행한다. Unix-domain sockets는 프로세스 간 통신에 사용된다는 점에서 파이프와 유사하지만, SCM_RIGHTS 제어 메시지를 전송할 수 있다는 점에서 차이가 있다. 이때 SCM_RIGHTS는 이미 열려있는 파일 기술자 (file descriptor)를 전송하는 기능이다. 이를 사용하면 그 대상 파일의 참조 횟수 (reference count)가 증가한다 (참조 횟수가 0이 되면 그 파일은 메모리에서 해제될 수 있음). 그래서 송신자는 파일 전송 후에 도착 여부와 관계없이, 바로 그 파일을 닫을 수 있고, 커널은 전송된 파일을 큐에 추가하고 수신될 때까지 유지한다. 즉, 아래 그림과 같이 파일이 이동하게 된다[2].
1[ Sender ] --> [ Queue ] --> [ Receiver ]
그런데 아래와 같은 상황을 가정해보자.
1[ End point 1 ] [ End point 2 ]
2 - fd1 is opened - fd2 is opened
위 상황에서 End point 1은 End point 2에게 fd1을 (SCM_RIGHTS로) 전송하고, 반대로 End point 2는 End point 1에게 fd2를 전송한다고 하자. 그럼 fd1과 fd2는 참조 횟수가 증가되고 큐에 들어갈 것이다. 이 시점에 End point 1이 fd1을 닫고, End point 2가 fd2를 닫는다면 두 End points는 큐에 있는 파일을 받을 수 없는 상황에 처한다. 이는 두 파일을 닫을 때 커널의 파일 기술자 테이블 (fd table)에서 지워졌기 때문이다. 이 상황을 그림으로 표현하면 다음과 같다[2, 3].
1[ End point 1 ] [ Queue ] [ End point 2 ]
2 - fd1 is closed - fd1 - fd2 is closed
3 - fd2
이렇게 관련 End points에서 접근할 수 없고 (unreachable), 참조 횟수로 인해 해제되지도 않는 파일들이 Unix GC에서 처리하고자 하는 것이다.
Unix_streamsendmsg Function #
송신자 (sender)는 sendmsg 시스템 콜을 사용하여 SCM_RIGHTS를 전송할 수 있고, 이 시스템 콜을 구현하는 것은 unix_streamsendmsg 함수이다. 이 함수는 크게 세 부분으로 나눌 수 있고, 그 구현은 다음과 같다 (net/unix/af_unix에서 발췌)[4].
- Initialize scm_cookie which contains file list of transmitted files ({1})
- Link scm_cookie file list to socket buffer (skb) ({2})
- Present transmitting files as vertices and edges and add it to a specific list for garbage collection ({3})
1static int unix_stream_sendmsg(struct socket *sock, struct msghdr *msg,
2 size_t len)
3{
4 struct sock *sk = sock->sk;
5 struct sock *other = NULL;
6 int err, size;
7 struct sk_buff *skb;
8 int sent = 0;
9 struct scm_cookie scm;
10 bool fds_sent = false;
11 int data_len;
12
13 /* {1} */
14 err = scm_send(sock, msg, &scm, false);
15 if (err < 0)
16 return err;
17
18 wait_for_unix_gc(scm.fp);
19
20 /* ... */
21
22 if (msg->msg_namelen) {
23 err = READ_ONCE(sk->sk_state) == TCP_ESTABLISHED ? -EISCONN : -EOPNOTSUPP;
24 goto out_err;
25 } else {
26 err = -ENOTCONN;
27 other = unix_peer(sk);
28 if (!other)
29 goto out_err;
30 }
31
32 if (READ_ONCE(sk->sk_shutdown) & SEND_SHUTDOWN)
33 goto pipe_err;
34
35 while (sent < len) {
36
37 /* ... */
38
39 skb = sock_alloc_send_pskb(sk, size - data_len, data_len,
40 msg->msg_flags & MSG_DONTWAIT, &err,
41 get_order(UNIX_SKB_FRAGS_SZ));
42 if (!skb)
43 goto out_err;
44
45 /* {2} */
46 /* Only send the fds in the first buffer */
47 err = unix_scm_to_skb(&scm, skb, !fds_sent);
48 if (err < 0) {
49 kfree_skb(skb);
50 goto out_err;
51 }
52 fds_sent = true;
53
54 /* ... */
55
56 maybe_add_creds(skb, sock, other);
57
58 /* {3} */
59 scm_stat_add(other, skb);
60 skb_queue_tail(&other->sk_receive_queue, skb);
61 unix_state_unlock(other);
62 other->sk_data_ready(other);
63 sent += size;
64 }
65
66 /* ... */
67
68 scm_destroy(&scm);
69
70 return sent;
71
72pipe_err_free:
73 unix_state_unlock(other);
74 kfree_skb(skb);
75pipe_err:
76 if (sent == 0 && !(msg->msg_flags&MSG_NOSIGNAL))
77 send_sig(SIGPIPE, current, 0);
78 err = -EPIPE;
79out_err:
80 scm_destroy(&scm);
81 return sent ? : err;
82}
Initialize scm cookie #
unix_streamsendmsg 함수는 아래 콜 트레이스 (call trace)를 거쳐서 스택에 위치한 scm_cookie 구조체를 초기화한다 (net/core/scm.c에서 발췌)[4].
1unix_scm_sendmsg()
2 |
3 |
4 +
5 |
6 |
7 V
8scm_send() /* fill scm_cookie structure to 0x0 */
9__scm_send()
10scm_fp_copy()
1static int scm_fp_copy(struct cmsghdr *cmsg, struct scm_fp_list **fplp)
2{
3 int *fdp = (int*)CMSG_DATA(cmsg);
4 struct scm_fp_list *fpl = *fplp;
5 struct file **fpp;
6 int i, num;
7
8 num = (cmsg->cmsg_len - sizeof(struct cmsghdr))/sizeof(int);
9
10 if (num <= 0)
11 return 0;
12
13 if (num > SCM_MAX_FD)
14 return -EINVAL;
15
16 if (!fpl)
17 {
18 fpl = kmalloc(sizeof(struct scm_fp_list), GFP_KERNEL_ACCOUNT);
19 if (!fpl)
20 return -ENOMEM;
21 *fplp = fpl;
22 fpl->count = 0;
23 fpl->count_unix = 0;
24 fpl->max = SCM_MAX_FD;
25 fpl->user = NULL;
26#if IS_ENABLED(CONFIG_UNIX)
27 fpl->inflight = false;
28 fpl->dead = false;
29 fpl->edges = NULL;
30 INIT_LIST_HEAD(&fpl->vertices);
31#endif
32 }
33 fpp = &fpl->fp[fpl->count];
34
35 if (fpl->count + num > fpl->max)
36 return -EINVAL;
37
38 /*
39 * Verify the descriptors and increment the usage count.
40 */
41
42 for (i=0; i< num; i++)
43 {
44 int fd = fdp[i];
45 struct file *file;
46
47 if (fd < 0 || !(file = fget_raw(fd)))
48 return -EBADF;
49 /* don't allow io_uring files */
50 if (io_is_uring_fops(file)) {
51 fput(file);
52 return -EINVAL;
53 }
54 if (unix_get_socket(file))
55 fpl->count_unix++;
56
57 *fpp++ = file;
58 fpl->count++;
59 }
60
61 if (!fpl->user)
62 fpl->user = get_uid(current_user());
63
64 return num;
65}
위 과정을 거치면 scm_cookie 구조체에서 파일 리스트를 담당하는 부분은 다음 그림과 같이 채워진다.
1scm_cookie: +----------------+
2 | *pid |
3 +----------------+
4 | *fp |--> +----------------+
5 +----------------+ | count |
6 | creds | +----------------+
7 +----------------+ | count_unix |
8 | secid | +----------------+
9 +----------------+ | max=SCM_MAX_FD |
10 +----------------+
11 | inflight=false |
12 +----------------+
13 | dead=false |
14 +----------------+
15 | vertices |
16 +----------------+
17 | *edges=NULL |
18 +----------------+
19 | *user=get_uid()|
20 +----------------+
21 | *fp[SCM_MAX_FD]|-> struct file
22 | ... |-> struct file
23 +----------------+
Link scm_cookie file list to socket buffer #
Unix-domain sockets도 결국 커널 내부적으로는 socket buffer를 통해 전송되므로 unix_streamsendmsg()는 sk_buff 구조체를 할당하고 상기의 파일 리스트를 연결한다. 이때 우리가 관심가지는 sk_buff 구조체의 멤버는 cb 멤버 배열이다. 이 작업은 다음 콜 트레이스를 거친다.
1unix_stream_sendmsg()
2 |
3 |
4 +--------------------+
5 | |2
6 | |
7 |1 V
8 V sock_alloc_send_pskb()
9scm_send() unix_scm_to_skb()
10__scm_send() unix_attach_fds()
11scm_fp_copy() |
12 |
13 |
14 +-----------------+
15 | |
16 |1 |2
17 V V
18 scm_fp_dup() unix_prepare_fpl()
19 get_file()
20 atomic_long_inc() /* increase &f->f_count */
위 콜 트레이스에서 scm_fpdup()는 scm_cookie.fp를 복사하여 new_fpl을 만들고 이를 unix_skbparams.fp에 저장한다. 그리고 각 파일의 참조 횟수를 증가시킨다. 이때 UNIXCB 매크로 함수가 sk_buff 구조체의 cb 멤버 배열을 unix_skbparams 구조체로 형변환한다 (net/core/scm.c에서 발췌)[4].
1struct scm_fp_list *scm_fp_dup(struct scm_fp_list *fpl)
2{
3 struct scm_fp_list *new_fpl;
4 int i;
5
6 if (!fpl)
7 return NULL;
8
9 new_fpl = kmemdup(fpl, offsetof(struct scm_fp_list, fp[fpl->count]),
10 GFP_KERNEL_ACCOUNT);
11 if (new_fpl) {
12 for (i = 0; i < fpl->count; i++)
13 get_file(fpl->fp[i]);
14
15 new_fpl->max = new_fpl->count;
16 new_fpl->user = get_uid(fpl->user);
17#if IS_ENABLED(CONFIG_UNIX)
18 new_fpl->inflight = false;
19 new_fpl->edges = NULL;
20 INIT_LIST_HEAD(&new_fpl->vertices);
21#endif
22 }
23 return new_fpl;
24}
그 다음은 unix_preparefpl()이 unix 파일의 개수만큼 vertices와 edges를 할당한다 (net/unix/garbage.c에서 발췌)[4].
1int unix_prepare_fpl(struct scm_fp_list *fpl)
2{
3 struct unix_vertex *vertex;
4 int i;
5
6 if (!fpl->count_unix)
7 return 0;
8
9 for (i = 0; i < fpl->count_unix; i++) {
10 vertex = kmalloc(sizeof(*vertex), GFP_KERNEL);
11 if (!vertex)
12 goto err;
13
14 list_add(&vertex->entry, &fpl->vertices);
15 }
16
17 fpl->edges = kvmalloc_array(fpl->count_unix, sizeof(*fpl->edges),
18 GFP_KERNEL_ACCOUNT);
19 if (!fpl->edges)
20 goto err;
21
22 return 0;
23
24err:
25 unix_free_vertices(fpl);
26 return -ENOMEM;
27}
위 과정을 거친 후 socket buffer는 다음과 같이 표현할 수 있다.
1sk_buff: +----------------+
2 | ... |
3 +----------------+--------+----------------+
4 | cb[48] | | *pid |
5 +----------------+--+ +----------------+
6 | ... | | | uid |
7 +----------------+ | +----------------+
8 | | gid |
9 | +----------------+
10 | | *fp |--------------+
11 | +----------------+ |
12 | | secid | |
13 | +----------------+ |
14 | | consumed | |
15 +-----+----------------+ |
16 |
17 kmemduped scm_fp_list structure |
18 +----------------+<--------------+
19 | count |
20 +----------------+
21 | count_unix |
22 +----------------+
23 | max=fpl->count |
24 +----------------+
25 | inflight=false |
26 +----------------+
27 | dead=false |
28 +----------------+
29 | vertices |-> vertex-> ...
30 +----------------+
31 | *edges |->[edge][edge] ...
32 +----------------+
33 | *user=get_uid()|
34 +----------------+
35 | *fp[SCM_MAX_FD]|-> struct file
36 | ... |-> struct file
37 +----------------+
Add allocated vertices to a specific list for garbage collection #
이제 상기에 할당했던 vertices와 edges를 Unix GC의 unix_unvisitedvertices에 연결한다. 이는 나중에 garbage collection을 할 때 사용된다. 그리고 socket buffer는 연결된 피어 소켓의 receive queue에 추가된다. 이 작업은 아래 콜 트레이스를 거쳐 진행된다.
1unix_stream_sendmsg()
2 |
3 |
4 +--------------------+---------------------+---------------+
5 | | | |
6 | |2 |3 |4
7 |1 V V V
8 V sock_alloc_send_pskb() scm_stat_add() skb_queue_tail()
9scm_send() unix_scm_to_skb() unix_add_edges()
10__scm_send() unix_attach_fds() unix_add_edge()
11scm_fp_copy() | unix_update_graph()
12 |
13 |
14 +-----------------+
15 | |
16 |1 |2
17 V V
18 scm_fp_dup() unix_prepare_fpl()
19 get_file()
20 atomic_long_inc() /* increase &f->f_count */
위 콜 트레이스에서 unix_addedges()는 unix socket에 대해 edge를 구성한다. 이때 edge는 상기에 할당한 것으로부터 가져온다 (net/unix/garbage.c에서 발췌)[4].
1void unix_add_edges(struct scm_fp_list *fpl, struct unix_sock *receiver)
2{
3 int i = 0, j = 0;
4
5 spin_lock(&unix_gc_lock);
6
7 if (!fpl->count_unix)
8 goto out;
9
10 do {
11 struct unix_sock *inflight = unix_get_socket(fpl->fp[j++]);
12 struct unix_edge *edge;
13
14 if (!inflight)
15 continue;
16
17 edge = fpl->edges + i++;
18 edge->predecessor = inflight;
19 edge->successor = receiver;
20
21 unix_add_edge(fpl, edge);
22 } while (i < fpl->count_unix);
23
24 receiver->scm_stat.nr_unix_fds += fpl->count_unix;
25 WRITE_ONCE(unix_tot_inflight, unix_tot_inflight + fpl->count_unix);
26out:
27 WRITE_ONCE(fpl->user->unix_inflight, fpl->user->unix_inflight + fpl->count);
28
29 spin_unlock(&unix_gc_lock);
30
31 fpl->inflight = true;
32
33 unix_free_vertices(fpl);
34}
위 코드에서 구성한 각 edge에 대해 unix_addedge()를 호출하여 상기에 할당했던 vertex를 구성한다. 그런데 초기에는 vertex가 없을 것이므로 이를 kmemdup로 복사했던 scm_fplist 구조체의 vertices 리스트에서 가져온다. 그리고 이를 unix_unvisitedvertices 리스트로 옮긴다. 그래서 작업이 끝나면 kmemdup로 복사했던 scm_fplist 구조체의 vertices는 비어있게 된다 (net/unix/garbage.c에서 발췌)[4].
1static void unix_add_edge(struct scm_fp_list *fpl, struct unix_edge *edge)
2{
3 struct unix_vertex *vertex = edge->predecessor->vertex;
4
5 if (!vertex) {
6 vertex = list_first_entry(&fpl->vertices, typeof(*vertex), entry);
7 vertex->index = unix_vertex_unvisited_index;
8 vertex->out_degree = 0;
9 INIT_LIST_HEAD(&vertex->edges);
10 INIT_LIST_HEAD(&vertex->scc_entry);
11
12 list_move_tail(&vertex->entry, &unix_unvisited_vertices);
13 edge->predecessor->vertex = vertex;
14 }
15
16 vertex->out_degree++;
17 list_add_tail(&edge->vertex_entry, &vertex->edges);
18
19 unix_update_graph(unix_edge_successor(edge));
20}
위 함수는 호출될 때마다 unix_graphmaybecyclic과 unix_graphgrouped 변수를 갱신한다. 이는 나중에 Unix GC의 동작을 결정할 때 사용된다. 이때 그래프를 갱신하는 방법이 edge->successor->vertex를 검사하는 것인 이유는 unix_updategraph 함수는 cyclic 여부를 갱신하기 위한 것이기 때문이다. 지금까지의 과정을 살펴보면 edge->successor->vertex에는 아무런 대입 연산도 하지 않았다. 그런데 vertex에 값이 존재한다면 이는 edge->predecessor와 edge->successor가 같음을, 즉 cyclic한 부분이 있음을 의미한다 (net/unix/garbage.c에서 발췌)[4].
1static void unix_update_graph(struct unix_vertex *vertex)
2{
3 /* If the receiver socket is not inflight, no cyclic
4 * reference could be formed.
5 */
6 if (!vertex)
7 return;
8
9 unix_graph_maybe_cyclic = true;
10 unix_graph_grouped = false;
11}
Unix_accept Function #
수신자 (receiver)가 accept 시스템 콜을 사용하여 SCM_RIGHTS로 전송된 것을 받고자 하면 unix_accept 함수가 호출되어 작업을 수행한다. 이 함수는 아래 콜 트레이스를 거쳐 receive queue에서 수신할 소켓 버퍼를 가져온다. 그리고 이 소켓 버퍼에서 sock 구조체를 추출하여 garbage collection을 위해 그래프 정보를 갱신한다 (net/unix/af_unix.c에서 발췌)[4].
1unix_accept()
2 |
3 |
4 +-------------------------------+
5 | |
6 |1 |2
7 V V
8skb_recv_datagram() unix_update_edges()
9__skb_recv_datagram() /* receive queue is passed */
10__skb_try_recv_datagram()
11__skb_try_recv_from_queue()
12__skb_unlink()
1static int unix_accept(struct socket *sock, struct socket *newsock, int flags,
2 bool kern)
3{
4 struct sock *sk = sock->sk;
5 struct sk_buff *skb;
6 struct sock *tsk;
7 int err;
8
9 err = -EOPNOTSUPP;
10 if (sock->type != SOCK_STREAM && sock->type != SOCK_SEQPACKET)
11 goto out;
12
13 err = -EINVAL;
14 if (sk->sk_state != TCP_LISTEN)
15 goto out;
16
17 /* If socket state is TCP_LISTEN it cannot change (for now...),
18 * so that no locks are necessary.
19 */
20
21 skb = skb_recv_datagram(sk, (flags & O_NONBLOCK) ? MSG_DONTWAIT : 0,
22 &err);
23 if (!skb) {
24 /* This means receive shutdown. */
25 if (err == 0)
26 err = -EINVAL;
27 goto out;
28 }
29
30 tsk = skb->sk;
31 skb_free_datagram(sk, skb);
32 wake_up_interruptible(&unix_sk(sk)->peer_wait);
33
34 /* attach accepted sock to socket */
35 unix_state_lock(tsk);
36 unix_update_edges(unix_sk(tsk));
37 newsock->state = SS_CONNECTED;
38 unix_sock_inherit_flags(sock, newsock);
39 sock_graft(tsk, newsock);
40 unix_state_unlock(tsk);
41 return 0;
42
43out:
44 return err;
45}
Unix_gc Function #
Unix_gc 함수는 __unixgc 함수로 작업을 시작하며 다음과 같은 콜 트레이스를 거친다.
1__unix_gc()
2 |
3 |
4 +------------------------------+
5 |unix_graph_grouped != true |unix_graph_grouped == true
6 V V
7unix_walk_scc() unix_walk_scc_fast()
8__unix_walk_scc()
그리고 이 함수는 hitlist에 garbage를 모아서 처리한다. 그 구현은 다음과 같다 (net/unix/garbage.c에서 발췌)[4].
1static void __unix_gc(struct work_struct *work)
2{
3 struct sk_buff_head hitlist;
4 struct sk_buff *skb;
5
6 spin_lock(&unix_gc_lock);
7
8 if (!unix_graph_maybe_cyclic) {
9 spin_unlock(&unix_gc_lock);
10 goto skip_gc;
11 }
12
13 __skb_queue_head_init(&hitlist);
14
15 if (unix_graph_grouped)
16 unix_walk_scc_fast(&hitlist);
17 else
18 unix_walk_scc(&hitlist);
19
20 spin_unlock(&unix_gc_lock);
21
22 skb_queue_walk(&hitlist, skb) {
23 if (UNIXCB(skb).fp)
24 UNIXCB(skb).fp->dead = true;
25 }
26
27 __skb_queue_purge(&hitlist);
28skip_gc:
29 WRITE_ONCE(gc_in_progress, false);
30}
31
32static DECLARE_WORK(unix_gc_work, __unix_gc);
33
34void unix_gc(void)
35{
36 WRITE_ONCE(gc_in_progress, true);
37 queue_work(system_unbound_wq, &unix_gc_work);
38}
위 코드에서 unix_walksccfast 함수는 SCC가 결정된 상태에서 호출되고, unix_walkscc 함수는 SCC를 결정해야 하는 상황에서 호출된다. 즉, Tarjan 알고리즘은 unix_walkscc()에서 사용하고 SCC가 결정되었음을 표시한다 (unix_graphgrouped = true). 이 두 함수는 결정된 SCC에 대해 dead 여부를 판단하기 위해 unix_vertexdead()를 호출한다. 이 함수의 구현은 다음과 같다 (net/unix/garbage.c에서 발췌)[4].
1static bool unix_vertex_dead(struct unix_vertex *vertex)
2{
3 struct unix_edge *edge;
4 struct unix_sock *u;
5 long total_ref;
6
7 list_for_each_entry(edge, &vertex->edges, vertex_entry) {
8 struct unix_vertex *next_vertex = unix_edge_successor(edge);
9
10 /* The vertex's fd can be received by a non-inflight socket. */
11 if (!next_vertex)
12 return false;
13
14 /* The vertex's fd can be received by an inflight socket in
15 * another SCC.
16 */
17 if (next_vertex->scc_index != vertex->scc_index)
18 return false;
19 }
20
21 /* No receiver exists out of the same SCC. */
22
23 edge = list_first_entry(&vertex->edges, typeof(*edge), vertex_entry);
24 u = edge->predecessor;
25 total_ref = file_count(u->sk.sk_socket->file);
26
27 /* If not close()d, total_ref > out_degree. */
28 if (total_ref != vertex->out_degree)
29 return false;
30
31 return true;
32}
위 코드에 의해 dead로 판명나면 그 SCC로 묶인 요소들은 hitlist로 이동된다.
이러한 garbage collection은 다음 두 가지 상황에서 호출된다[4].
-
전송된 파일의 개수가 너무 많을 때 (net/unix/garbage.c에서 발췌)
1void wait_for_unix_gc(struct scm_fp_list *fpl) 2{ 3 /* If number of inflight sockets is insane, 4 * force a garbage collect right now. 5 * 6 * Paired with the WRITE_ONCE() in unix_inflight(), 7 * unix_notinflight(), and __unix_gc(). 8 */ 9 if (READ_ONCE(unix_tot_inflight) > UNIX_INFLIGHT_TRIGGER_GC && 10 !READ_ONCE(gc_in_progress)) 11 unix_gc(); 12 13 /* Penalise users who want to send AF_UNIX sockets 14 * but whose sockets have not been received yet. 15 */ 16 if (!fpl || !fpl->count_unix || 17 READ_ONCE(fpl->user->unix_inflight) < UNIX_INFLIGHT_SANE_USER) 18 return; 19 20 if (READ_ONCE(gc_in_progress)) 21 flush_work(&unix_gc_work); 22} -
Unix 소켓을 닫는 작업 수행 중 전송 상태인 파일이 있을 때 (net/unix/af_unix.c에서 발췌)
1static void unix_release_sock(struct sock *sk, int embrion) 2{ 3 /* ... */ 4 5 if (READ_ONCE(unix_tot_inflight)) 6 unix_gc(); /* Garbage collect fds */ 7}
Root-cause Analysis #
이 취약점은 결론적으로 unix_walksccfast 함수가 호출되는 경로에서 scc_index에 대한 초기화가 없어서 발생하였다. 즉, 이전에 처리되었던 garbage의 scc_index가 다시 사용될 수 있고, 이것이 unix_vertexdead()의 오동작을 초래한다는 것이다[1].
상기에 다룬 unix_streamsendmsg 함수와 unix_walksccfast 함수에서는 scc_index 멤버에 대한 초기화를 하지 않는다. 이제 patch에 제시된 시나리오 [1]를 살펴보자. 먼저 하나의 순환 참조 (cyclic reference) 형태를 이루는 많은 unix 소켓을 열고 닫아서 unix_gc()가 트리거되도록 만든다. 이는 unix_walkscc()를 통해 초기화된 scc_index 멤버가 있는, 많은 메모리를 만든다.
이 상태에서 한 unix 소켓 A (이하 sk-A)를 또다른 unix 소캣 B (이하 sk-B)로 전송한다. 그럼 sk-A는 refcount가 2, outdegree가 1이 된다. 그리고 순환 참조 형태를 갖는 unix 소켓 X (이하 sk-X)를 X에게 전송한 후에 더미 unix 소켓을 하나 닫는다. 이 더미 소켓은 unix_gc()를 트리거하기 위한 것으로, sk-A와 sk-X를 전송한 것 때문에 __unixgc()가 호출될 것이다. 그럼 두 그룹으로 SCC가 결정된다 (sk-A -> sk-B, sk-X -> sk-X). 즉, 이때 unix_graphgrouped는 true가 되고, 두 그룹의 scc_index는 각각 다음과 같다.
- sk-A -> sk-B: 2 (= UNIX_VERTEXINDEXSTART)
- sk-X -> sk-X: 3
이제 sk-B에서 sk-A를 accept()한다. 그 다음 sk-B를 또다른 unix 소켓 C (이하 sk-C)로 전송하고 sk-A를 닫는다. 이는 sk-A의 refcount를 1로 감소시키고, unix_gc()를 트리거 하는데 이때 unix_walksccfast()가 호출된다. 이 함수는 다음과 같이 sk-A, sk-B, sk-X를 순회한다 (net/unix/garbage.c에서 발췌).
1static void unix_walk_scc_fast(struct sk_buff_head *hitlist)
2{
3 unix_graph_maybe_cyclic = false;
4
5 while (!list_empty(&unix_unvisited_vertices)) {
6 struct unix_vertex *vertex;
7 struct list_head scc;
8 bool scc_dead = true;
9
10 vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry);
11 list_add(&scc, &vertex->scc_entry);
12
13 list_for_each_entry_reverse(vertex, &scc, scc_entry) {
14 list_move_tail(&vertex->entry, &unix_visited_vertices);
15
16 if (scc_dead)
17 scc_dead = unix_vertex_dead(vertex);
18 }
19
20 if (scc_dead)
21 unix_collect_skb(&scc, hitlist);
22 else if (!unix_graph_maybe_cyclic)
23 unix_graph_maybe_cyclic = unix_scc_cyclic(&scc);
24
25 list_del(&scc);
26 }
27
28 list_replace_init(&unix_visited_vertices, &unix_unvisited_vertices);
29}
그런데 sk-A와 sk-B의 scc_index가 같고, refcount와 outdegree도 같아서 sk-A가 dead로 결정된다.
Patch #
패치는 unix_addedge에 scc_index 멤버에 대한 초기화 코드를 추가하는 방식으로 진행되었다[1].
1
2diff --git a/net/unix/garbage.c b/net/unix/garbage.c
3index 01e2b9452c75b..358fcaba9a732 100644
4--- a/net/unix/garbage.c
5+++ b/net/unix/garbage.c
6@@ -145,6 +145,7 @@ enum unix_vertex_index {
7 };
8
9 static unsigned long unix_vertex_unvisited_index = UNIX_VERTEX_INDEX_MARK1;
10+static unsigned long unix_vertex_max_scc_index = UNIX_VERTEX_INDEX_START;
11
12 static void unix_add_edge(struct scm_fp_list *fpl, struct unix_edge *edge)
13 {
14@@ -153,6 +154,7 @@ static void unix_add_edge(struct scm_fp_list *fpl, struct unix_edge *edge)
15 if (!vertex) {
16 vertex = list_first_entry(&fpl->vertices, typeof(*vertex), entry);
17 vertex->index = unix_vertex_unvisited_index;
18+ vertex->scc_index = ++unix_vertex_max_scc_index;
19 vertex->out_degree = 0;
20 INIT_LIST_HEAD(&vertex->edges);
21 INIT_LIST_HEAD(&vertex->scc_entry);
22@@ -489,10 +491,15 @@ prev_vertex:
23 scc_dead = unix_vertex_dead(v);
24 }
25
26- if (scc_dead)
27+ if (scc_dead) {
28 unix_collect_skb(&scc, hitlist);
29- else if (!unix_graph_maybe_cyclic)
30- unix_graph_maybe_cyclic = unix_scc_cyclic(&scc);
31+ } else {
32+ if (unix_vertex_max_scc_index < vertex->scc_index)
33+ unix_vertex_max_scc_index = vertex->scc_index;
34+
35+ if (!unix_graph_maybe_cyclic)
36+ unix_graph_maybe_cyclic = unix_scc_cyclic(&scc);
37+ }
38
39 list_del(&scc);
40 }
41@@ -507,6 +514,7 @@ static void unix_walk_scc(struct sk_buff_head *hitlist)
42 unsigned long last_index = UNIX_VERTEX_INDEX_START;
43
44 unix_graph_maybe_cyclic = false;
45+ unix_vertex_max_scc_index = UNIX_VERTEX_INDEX_START;
46
47 /* Visit every vertex exactly once.
48 * __unix_walk_scc() moves visited vertices to unix_visited_vertices.
References #
- Kuniyuki Iwashima, "af_unix: Initialise scc_index in unix_addedge()." git.kernel.org, Accessed: Apr. 01, 2026. [Online]. Available: https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/commit/?id=1aa7e40ee850c9053e769957ce6541173891204d
- Jonathan Corbet, "io_uring, SCM_RIGHTS, and reference-count cycles." lwn.net, Accessed: Apr. 01, 2026. [Online]. Available: https://lwn.net/Articles/779472/
- Xingyu Jin, "The quantum state of Linux kernel garbage collection CVE-2021-0920 (Part I)." projectzero.google, Accessed Apr. 01, 2026. [Online]. Available: https://projectzero.google/2022/08/the-quantum-state-of-linux-kernel.html
- Linux torvalds et al., "Linux kernel", (Version 6.1.158) [Source Code]. https://github.com/torvalds/linux
- HeadEasyLabs, Tarjan's Algorithm | Strongly Connected Components. (Oct. 21, 2023). Accessed: Apr. 01, 2026. [Online Video]. Available: https://www.youtube.com/watch?v=_1TDxihjtoE
- Robert Tarjan, "DEPTH-FIRST SEARCH AND LINEAR GRAPH ALGORITHMS," SIAM Journal on Computing, vol. 1, no. 2, Jun. 1972. Accessed: Apr. 01, 2026. [Online]. Available: https://web.archive.org/web/20170829214726/http://www.cs.ucsb.edu/~gilbert/cs240a/old/cs240aSpr2011/slides/TarjanDFS.pdf