Table of Contents
- Introduction
- Tarjan Algorithm
- SCM_RIGHTS and Garbage Collection
- Unix_stream_sendmsg 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].
[ Sender ] --> [ Queue ] --> [ Receiver ]
그런데 아래와 같은 상황을 가정해보자.
[ End point 1 ] [ End point 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].
[ End point 1 ] [ Queue ] [ End point 2 ]
- fd1 is closed - fd1 - fd2 is closed
- fd2
이렇게 관련 End points에서 접근할 수 없고 (unreachable), 참조 횟수로 인해 해제되지도 않는 파일들이 Unix GC에서 처리하고자 하는 것이다.
Unix_stream_sendmsg Function #
송신자 (sender)는 sendmsg 시스템 콜을 사용하여 SCM_RIGHTS를 전송할 수 있고, 이 시스템 콜을 구현하는 것은 unix_stream_sendmsg 함수이다. 이 함수는 크게 세 부분으로 나눌 수 있고, 그 구현은 다음과 같다 (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})
static int unix_stream_sendmsg(struct socket *sock, struct msghdr *msg, size_t len) { struct sock *sk = sock->sk; struct sock *other = NULL; int err, size; struct sk_buff *skb; int sent = 0; struct scm_cookie scm; bool fds_sent = false; int data_len;
/* {1} */ err = scm_send(sock, msg, &scm, false); if (err < 0) return err; wait_for_unix_gc(scm.fp); /* ... */ if (msg->msg_namelen) { err = READ_ONCE(sk->sk_state) == TCP_ESTABLISHED ? -EISCONN : -EOPNOTSUPP; goto out_err; } else { err = -ENOTCONN; other = unix_peer(sk); if (!other) goto out_err; } if (READ_ONCE(sk->sk_shutdown) & SEND_SHUTDOWN) goto pipe_err; while (sent < len) { /* ... */ skb = sock_alloc_send_pskb(sk, size - data_len, data_len, msg->msg_flags & MSG_DONTWAIT, &err, get_order(UNIX_SKB_FRAGS_SZ)); if (!skb) goto out_err; /* {2} */ /* Only send the fds in the first buffer */ err = unix_scm_to_skb(&scm, skb, !fds_sent); if (err < 0) { kfree_skb(skb); goto out_err; } fds_sent = true; /* ... */ maybe_add_creds(skb, sock, other); /* {3} */ scm_stat_add(other, skb); skb_queue_tail(&other->sk_receive_queue, skb); unix_state_unlock(other); other->sk_data_ready(other); sent += size; } /* ... */ scm_destroy(&scm); return sent;pipe_err_free: unix_state_unlock(other); kfree_skb(skb); pipe_err: if (sent == 0 && !(msg->msg_flags&MSG_NOSIGNAL)) send_sig(SIGPIPE, current, 0); err = -EPIPE; out_err: scm_destroy(&scm); return sent ? : err; }
Initialize scm cookie #
unix_stream_sendmsg 함수는 아래 콜 트레이스 (call trace)를 거쳐서 스택에 위치한 scm_cookie 구조체를 초기화한다 (net/core/scm.c에서 발췌)[4].
unix_scm_sendmsg()
|
|
+
|
|
V
scm_send() /* fill scm_cookie structure to 0x0 */
__scm_send()
scm_fp_copy()
static int scm_fp_copy(struct cmsghdr *cmsg, struct scm_fp_list **fplp)
{
int *fdp = (int*)CMSG_DATA(cmsg);
struct scm_fp_list *fpl = *fplp;
struct file **fpp;
int i, num;
num = (cmsg->cmsg_len - sizeof(struct cmsghdr))/sizeof(int);
if (num <= 0)
return 0;
if (num > SCM_MAX_FD)
return -EINVAL;
if (!fpl)
{
fpl = kmalloc(sizeof(struct scm_fp_list), GFP_KERNEL_ACCOUNT);
if (!fpl)
return -ENOMEM;
*fplp = fpl;
fpl->count = 0;
fpl->count_unix = 0;
fpl->max = SCM_MAX_FD;
fpl->user = NULL;
#if IS_ENABLED(CONFIG_UNIX)
fpl->inflight = false;
fpl->dead = false;
fpl->edges = NULL;
INIT_LIST_HEAD(&fpl->vertices);
#endif
}
fpp = &fpl->fp[fpl->count];
if (fpl->count + num > fpl->max)
return -EINVAL;
/*
* Verify the descriptors and increment the usage count.
*/
for (i=0; i< num; i++)
{
int fd = fdp[i];
struct file *file;
if (fd < 0 || !(file = fget_raw(fd)))
return -EBADF;
/* don't allow io_uring files */
if (io_is_uring_fops(file)) {
fput(file);
return -EINVAL;
}
if (unix_get_socket(file))
fpl->count_unix++;
*fpp++ = file;
fpl->count++;
}
if (!fpl->user)
fpl->user = get_uid(current_user());
return num;
}
위 과정을 거치면 scm_cookie 구조체에서 파일 리스트를 담당하는 부분은 다음 그림과 같이 채워진다.
scm_cookie: +----------------+
| *pid |
+----------------+
| *fp |--> +----------------+
+----------------+ | count |
| creds | +----------------+
+----------------+ | count_unix |
| secid | +----------------+
+----------------+ | max=SCM_MAX_FD |
+----------------+
| inflight=false |
+----------------+
| dead=false |
+----------------+
| vertices |
+----------------+
| *edges=NULL |
+----------------+
| *user=get_uid()|
+----------------+
| *fp[SCM_MAX_FD]|-> struct file
| ... |-> struct file
+----------------+
Link scm_cookie file list to socket buffer #
Unix-domain sockets도 결국 커널 내부적으로는 socket buffer를 통해 전송되므로 unix_stream_sendmsg()는 sk_buff 구조체를 할당하고 상기의 파일 리스트를 연결한다. 이때 우리가 관심가지는 sk_buff 구조체의 멤버는 cb 멤버 배열이다. 이 작업은 다음 콜 트레이스를 거친다.
unix_stream_sendmsg()
|
|
+--------------------+
| |2
| |
|1 V
V sock_alloc_send_pskb()
scm_send() unix_scm_to_skb()
__scm_send() unix_attach_fds()
scm_fp_copy() |
|
|
+-----------------+
| |
|1 |2
V V
scm_fp_dup() unix_prepare_fpl()
get_file()
atomic_long_inc() /* increase &f->f_count */
위 콜 트레이스에서 scm_fp_dup()는 scm_cookie.fp를 복사하여 new_fpl을 만들고 이를 unix_skb_params.fp에 저장한다. 그리고 각 파일의 참조 횟수를 증가시킨다. 이때 UNIXCB 매크로 함수가 sk_buff 구조체의 cb 멤버 배열을 unix_skb_params 구조체로 형변환한다 (net/core/scm.c에서 발췌)[4].
struct scm_fp_list *scm_fp_dup(struct scm_fp_list *fpl)
{
struct scm_fp_list *new_fpl;
int i;
if (!fpl)
return NULL;
new_fpl = kmemdup(fpl, offsetof(struct scm_fp_list, fp[fpl->count]),
GFP_KERNEL_ACCOUNT);
if (new_fpl) {
for (i = 0; i < fpl->count; i++)
get_file(fpl->fp[i]);
new_fpl->max = new_fpl->count;
new_fpl->user = get_uid(fpl->user);
#if IS_ENABLED(CONFIG_UNIX)
new_fpl->inflight = false;
new_fpl->edges = NULL;
INIT_LIST_HEAD(&new_fpl->vertices);
#endif
}
return new_fpl;
}
그 다음은 unix_prepare_fpl()이 unix 파일의 개수만큼 vertices와 edges를 할당한다 (net/unix/garbage.c에서 발췌)[4].
int unix_prepare_fpl(struct scm_fp_list *fpl)
{
struct unix_vertex *vertex;
int i;
if (!fpl->count_unix)
return 0;
for (i = 0; i < fpl->count_unix; i++) {
vertex = kmalloc(sizeof(*vertex), GFP_KERNEL);
if (!vertex)
goto err;
list_add(&vertex->entry, &fpl->vertices);
}
fpl->edges = kvmalloc_array(fpl->count_unix, sizeof(*fpl->edges),
GFP_KERNEL_ACCOUNT);
if (!fpl->edges)
goto err;
return 0;
err:
unix_free_vertices(fpl);
return -ENOMEM;
}
위 과정을 거친 후 socket buffer는 다음과 같이 표현할 수 있다.
sk_buff: +----------------+
| ... |
+----------------+--------+----------------+
| cb[48] | | *pid |
+----------------+--+ +----------------+
| ... | | | uid |
+----------------+ | +----------------+
| | gid |
| +----------------+
| | *fp |--------------+
| +----------------+ |
| | secid | |
| +----------------+ |
| | consumed | |
+-----+----------------+ |
|
kmemduped scm_fp_list structure |
+----------------+<--------------+
| count |
+----------------+
| count_unix |
+----------------+
| max=fpl->count |
+----------------+
| inflight=false |
+----------------+
| dead=false |
+----------------+
| vertices |-> vertex-> ...
+----------------+
| *edges |->[edge][edge] ...
+----------------+
| *user=get_uid()|
+----------------+
| *fp[SCM_MAX_FD]|-> struct file
| ... |-> struct file
+----------------+
Add allocated vertices to a specific list for garbage collection #
이제 상기에 할당했던 vertices와 edges를 Unix GC의 unix_unvisited_vertices에 연결한다. 이는 나중에 garbage collection을 할 때 사용된다. 그리고 socket buffer는 연결된 피어 소켓의 receive queue에 추가된다. 이 작업은 아래 콜 트레이스를 거쳐 진행된다.
unix_stream_sendmsg()
|
|
+--------------------+---------------------+---------------+
| | | |
| |2 |3 |4
|1 V V V
V sock_alloc_send_pskb() scm_stat_add() skb_queue_tail()
scm_send() unix_scm_to_skb() unix_add_edges()
__scm_send() unix_attach_fds() unix_add_edge()
scm_fp_copy() | unix_update_graph()
|
|
+-----------------+
| |
|1 |2
V V
scm_fp_dup() unix_prepare_fpl()
get_file()
atomic_long_inc() /* increase &f->f_count */
위 콜 트레이스에서 unix_add_edges()는 unix socket에 대해 edge를 구성한다. 이때 edge는 상기에 할당한 것으로부터 가져온다 (net/unix/garbage.c에서 발췌)[4].
void unix_add_edges(struct scm_fp_list *fpl, struct unix_sock *receiver)
{
int i = 0, j = 0;
spin_lock(&unix_gc_lock);
if (!fpl->count_unix)
goto out;
do {
struct unix_sock *inflight = unix_get_socket(fpl->fp[j++]);
struct unix_edge *edge;
if (!inflight)
continue;
edge = fpl->edges + i++;
edge->predecessor = inflight;
edge->successor = receiver;
unix_add_edge(fpl, edge);
} while (i < fpl->count_unix);
receiver->scm_stat.nr_unix_fds += fpl->count_unix;
WRITE_ONCE(unix_tot_inflight, unix_tot_inflight + fpl->count_unix);
out:
WRITE_ONCE(fpl->user->unix_inflight, fpl->user->unix_inflight + fpl->count);
spin_unlock(&unix_gc_lock);
fpl->inflight = true;
unix_free_vertices(fpl);
}
위 코드에서 구성한 각 edge에 대해 unix_add_edge()를 호출하여 상기에 할당했던 vertex를 구성한다. 그런데 초기에는 vertex가 없을 것이므로 이를 kmemdup로 복사했던 scm_fp_list 구조체의 vertices 리스트에서 가져온다. 그리고 이를 unix_unvisited_vertices 리스트로 옮긴다. 그래서 작업이 끝나면 kmemdup로 복사했던 scm_fp_list 구조체의 vertices는 비어있게 된다 (net/unix/garbage.c에서 발췌)[4].
static void unix_add_edge(struct scm_fp_list *fpl, struct unix_edge *edge)
{
struct unix_vertex *vertex = edge->predecessor->vertex;
if (!vertex) {
vertex = list_first_entry(&fpl->vertices, typeof(*vertex), entry);
vertex->index = unix_vertex_unvisited_index;
vertex->out_degree = 0;
INIT_LIST_HEAD(&vertex->edges);
INIT_LIST_HEAD(&vertex->scc_entry);
list_move_tail(&vertex->entry, &unix_unvisited_vertices);
edge->predecessor->vertex = vertex;
}
vertex->out_degree++;
list_add_tail(&edge->vertex_entry, &vertex->edges);
unix_update_graph(unix_edge_successor(edge));
}
위 함수는 호출될 때마다 unix_graph_maybe_cyclic과 unix_graph_grouped 변수를 갱신한다. 이는 나중에 Unix GC의 동작을 결정할 때 사용된다. 이때 그래프를 갱신하는 방법이 edge->successor->vertex를 검사하는 것인 이유는 unix_update_graph 함수는 cyclic 여부를 갱신하기 위한 것이기 때문이다. 지금까지의 과정을 살펴보면 edge->successor->vertex에는 아무런 대입 연산도 하지 않았다. 그런데 vertex에 값이 존재한다면 이는 edge->predecessor와 edge->successor가 같음을, 즉 cyclic한 부분이 있음을 의미한다 (net/unix/garbage.c에서 발췌)[4].
static void unix_update_graph(struct unix_vertex *vertex)
{
/* If the receiver socket is not inflight, no cyclic
* reference could be formed.
*/
if (!vertex)
return;
unix_graph_maybe_cyclic = true;
unix_graph_grouped = false;
}
Unix_accept Function #
수신자 (receiver)가 accept 시스템 콜을 사용하여 SCM_RIGHTS로 전송된 것을 받고자 하면 unix_accept 함수가 호출되어 작업을 수행한다. 이 함수는 아래 콜 트레이스를 거쳐 receive queue에서 수신할 소켓 버퍼를 가져온다. 그리고 이 소켓 버퍼에서 sock 구조체를 추출하여 garbage collection을 위해 그래프 정보를 갱신한다 (net/unix/af_unix.c에서 발췌)[4].
unix_accept()
|
|
+-------------------------------+
| |
|1 |2
V V
skb_recv_datagram() unix_update_edges()
__skb_recv_datagram() /* receive queue is passed */
__skb_try_recv_datagram()
__skb_try_recv_from_queue()
__skb_unlink()
static int unix_accept(struct socket *sock, struct socket *newsock, int flags,
bool kern)
{
struct sock *sk = sock->sk;
struct sk_buff *skb;
struct sock *tsk;
int err;
err = -EOPNOTSUPP;
if (sock->type != SOCK_STREAM && sock->type != SOCK_SEQPACKET)
goto out;
err = -EINVAL;
if (sk->sk_state != TCP_LISTEN)
goto out;
/* If socket state is TCP_LISTEN it cannot change (for now...),
* so that no locks are necessary.
*/
skb = skb_recv_datagram(sk, (flags & O_NONBLOCK) ? MSG_DONTWAIT : 0,
&err);
if (!skb) {
/* This means receive shutdown. */
if (err == 0)
err = -EINVAL;
goto out;
}
tsk = skb->sk;
skb_free_datagram(sk, skb);
wake_up_interruptible(&unix_sk(sk)->peer_wait);
/* attach accepted sock to socket */
unix_state_lock(tsk);
unix_update_edges(unix_sk(tsk));
newsock->state = SS_CONNECTED;
unix_sock_inherit_flags(sock, newsock);
sock_graft(tsk, newsock);
unix_state_unlock(tsk);
return 0;
out:
return err;
}
Unix_gc Function #
Unix_gc 함수는 __unix_gc 함수로 작업을 시작하며 다음과 같은 콜 트레이스를 거친다.
__unix_gc()
|
|
+------------------------------+
|unix_graph_grouped != true |unix_graph_grouped == true
V V
unix_walk_scc() unix_walk_scc_fast()
__unix_walk_scc()
그리고 이 함수는 hitlist에 garbage를 모아서 처리한다. 그 구현은 다음과 같다 (net/unix/garbage.c에서 발췌)[4].
static void __unix_gc(struct work_struct *work)
{
struct sk_buff_head hitlist;
struct sk_buff *skb;
spin_lock(&unix_gc_lock);
if (!unix_graph_maybe_cyclic) {
spin_unlock(&unix_gc_lock);
goto skip_gc;
}
__skb_queue_head_init(&hitlist);
if (unix_graph_grouped)
unix_walk_scc_fast(&hitlist);
else
unix_walk_scc(&hitlist);
spin_unlock(&unix_gc_lock);
skb_queue_walk(&hitlist, skb) {
if (UNIXCB(skb).fp)
UNIXCB(skb).fp->dead = true;
}
__skb_queue_purge(&hitlist);
skip_gc:
WRITE_ONCE(gc_in_progress, false);
}
static DECLARE_WORK(unix_gc_work, __unix_gc);
void unix_gc(void)
{
WRITE_ONCE(gc_in_progress, true);
queue_work(system_unbound_wq, &unix_gc_work);
}
위 코드에서 unix_walk_scc_fast 함수는 SCC가 결정된 상태에서 호출되고, unix_walk_scc 함수는 SCC를 결정해야 하는 상황에서 호출된다. 즉, Tarjan 알고리즘은 unix_walk_scc()에서 사용하고 SCC가 결정되었음을 표시한다 (unix_graph_grouped = true). 이 두 함수는 결정된 SCC에 대해 dead 여부를 판단하기 위해 unix_vertex_dead()를 호출한다. 이 함수의 구현은 다음과 같다 (net/unix/garbage.c에서 발췌)[4].
static bool unix_vertex_dead(struct unix_vertex *vertex)
{
struct unix_edge *edge;
struct unix_sock *u;
long total_ref;
list_for_each_entry(edge, &vertex->edges, vertex_entry) {
struct unix_vertex *next_vertex = unix_edge_successor(edge);
/* The vertex's fd can be received by a non-inflight socket. */
if (!next_vertex)
return false;
/* The vertex's fd can be received by an inflight socket in
* another SCC.
*/
if (next_vertex->scc_index != vertex->scc_index)
return false;
}
/* No receiver exists out of the same SCC. */
edge = list_first_entry(&vertex->edges, typeof(*edge), vertex_entry);
u = edge->predecessor;
total_ref = file_count(u->sk.sk_socket->file);
/* If not close()d, total_ref > out_degree. */
if (total_ref != vertex->out_degree)
return false;
return true;
}
위 코드에 의해 dead로 판명나면 그 SCC로 묶인 요소들은 hitlist로 이동된다.
이러한 garbage collection은 다음 두 가지 상황에서 호출된다[4].
-
전송된 파일의 개수가 너무 많을 때 (net/unix/garbage.c에서 발췌)
void wait_for_unix_gc(struct scm_fp_list *fpl) { /* If number of inflight sockets is insane, * force a garbage collect right now. * * Paired with the WRITE_ONCE() in unix_inflight(), * unix_notinflight(), and __unix_gc(). */ if (READ_ONCE(unix_tot_inflight) > UNIX_INFLIGHT_TRIGGER_GC && !READ_ONCE(gc_in_progress)) unix_gc(); /* Penalise users who want to send AF_UNIX sockets * but whose sockets have not been received yet. */ if (!fpl || !fpl->count_unix || READ_ONCE(fpl->user->unix_inflight) < UNIX_INFLIGHT_SANE_USER) return; if (READ_ONCE(gc_in_progress)) flush_work(&unix_gc_work); } -
Unix 소켓을 닫는 작업 수행 중 전송 상태인 파일이 있을 때 (net/unix/af_unix.c에서 발췌)
static void unix_release_sock(struct sock *sk, int embrion) { /* ... */ if (READ_ONCE(unix_tot_inflight)) unix_gc(); /* Garbage collect fds */ }
Root-cause Analysis #
이 취약점은 결론적으로 unix_walk_scc_fast 함수가 호출되는 경로에서 scc_index에 대한 초기화가 없어서 발생하였다. 즉, 이전에 처리되었던 garbage의 scc_index가 다시 사용될 수 있고, 이것이 unix_vertex_dead()의 오동작을 초래한다는 것이다[1].
상기에 다룬 unix_stream_sendmsg 함수와 unix_walk_scc_fast 함수에서는 scc_index 멤버에 대한 초기화를 하지 않는다. 이제 patch에 제시된 시나리오 [1]를 살펴보자. 먼저 하나의 순환 참조 (cyclic reference) 형태를 이루는 많은 unix 소켓을 열고 닫아서 unix_gc()가 트리거되도록 만든다. 이는 unix_walk_scc()를 통해 초기화된 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를 전송한 것 때문에 __unix_gc()가 호출될 것이다. 그럼 두 그룹으로 SCC가 결정된다 (sk-A -> sk-B, sk-X -> sk-X). 즉, 이때 unix_graph_grouped는 true가 되고, 두 그룹의 scc_index는 각각 다음과 같다.
- sk-A -> sk-B: 2 (= UNIX_VERTEX_INDEX_START)
- 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_walk_scc_fast()가 호출된다. 이 함수는 다음과 같이 sk-A, sk-B, sk-X를 순회한다 (net/unix/garbage.c에서 발췌).
static void unix_walk_scc_fast(struct sk_buff_head *hitlist)
{
unix_graph_maybe_cyclic = false;
while (!list_empty(&unix_unvisited_vertices)) {
struct unix_vertex *vertex;
struct list_head scc;
bool scc_dead = true;
vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry);
list_add(&scc, &vertex->scc_entry);
list_for_each_entry_reverse(vertex, &scc, scc_entry) {
list_move_tail(&vertex->entry, &unix_visited_vertices);
if (scc_dead)
scc_dead = unix_vertex_dead(vertex);
}
if (scc_dead)
unix_collect_skb(&scc, hitlist);
else if (!unix_graph_maybe_cyclic)
unix_graph_maybe_cyclic = unix_scc_cyclic(&scc);
list_del(&scc);
}
list_replace_init(&unix_visited_vertices, &unix_unvisited_vertices);
}
그런데 sk-A와 sk-B의 scc_index가 같고, refcount와 outdegree도 같아서 sk-A가 dead로 결정된다.
Patch #
패치는 unix_add_edge에 scc_index 멤버에 대한 초기화 코드를 추가하는 방식으로 진행되었다[1].
diff --git a/net/unix/garbage.c b/net/unix/garbage.c
index 01e2b9452c75b..358fcaba9a732 100644
--- a/net/unix/garbage.c
+++ b/net/unix/garbage.c
@@ -145,6 +145,7 @@ enum unix_vertex_index {
};
static unsigned long unix_vertex_unvisited_index = UNIX_VERTEX_INDEX_MARK1;
+static unsigned long unix_vertex_max_scc_index = UNIX_VERTEX_INDEX_START;
static void unix_add_edge(struct scm_fp_list *fpl, struct unix_edge *edge)
{
@@ -153,6 +154,7 @@ static void unix_add_edge(struct scm_fp_list *fpl, struct unix_edge *edge)
if (!vertex) {
vertex = list_first_entry(&fpl->vertices, typeof(*vertex), entry);
vertex->index = unix_vertex_unvisited_index;
+ vertex->scc_index = ++unix_vertex_max_scc_index;
vertex->out_degree = 0;
INIT_LIST_HEAD(&vertex->edges);
INIT_LIST_HEAD(&vertex->scc_entry);
@@ -489,10 +491,15 @@ prev_vertex:
scc_dead = unix_vertex_dead(v);
}
- if (scc_dead)
+ if (scc_dead) {
unix_collect_skb(&scc, hitlist);
- else if (!unix_graph_maybe_cyclic)
- unix_graph_maybe_cyclic = unix_scc_cyclic(&scc);
+ } else {
+ if (unix_vertex_max_scc_index < vertex->scc_index)
+ unix_vertex_max_scc_index = vertex->scc_index;
+
+ if (!unix_graph_maybe_cyclic)
+ unix_graph_maybe_cyclic = unix_scc_cyclic(&scc);
+ }
list_del(&scc);
}
@@ -507,6 +514,7 @@ static void unix_walk_scc(struct sk_buff_head *hitlist)
unsigned long last_index = UNIX_VERTEX_INDEX_START;
unix_graph_maybe_cyclic = false;
+ unix_vertex_max_scc_index = UNIX_VERTEX_INDEX_START;
/* Visit every vertex exactly once.
* __unix_walk_scc() moves visited vertices to unix_visited_vertices.
References #
- Kuniyuki Iwashima, "af_unix: Initialise scc_index in unix_add_edge()." 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