curl 8.12~8.16, 설정 파일 조합으로 이론상 범용 계산 구현

본문

curl 8.12부터 8.16까지 설정 파일의 변수 조각내기와 다른 설정 파일 포함 기능을 조합하면 이론상 2-카운터 Minsky 프로그램을 표현할 수 있었습니다. Nicolas Seriot의 분석은 무한한 문자열과 실행 단계를 가정한 모델에서 이 구성이 튜링 완전하다고 설명합니다. curl 8.17.0은 설정 파일 포함 깊이를 5단계로 제한해 이 구성의 무제한 반복 경로를 끊었습니다.

변수 값과 파일 이름으로 계산하기

이 구성에서는 카운터 값 n을 문자 x가 n개 들어 있는 변수로 나타냅니다. 변수 확장으로 x를 하나 덧붙이면 카운터가 증가하고, 첫 바이트를 제외한 나머지를 대입하면 감소합니다. 첫 바이트만 뽑아 값이 비었는지를 확인하면 카운터가 0인지 검사할 수 있습니다. 각 명령 상태는 설정 파일 이름으로 표시하고 expand-config가 다음 상태의 파일을 포함합니다. 변수 조작은 카운터 연산을, 설정 파일 포함은 다음 명령으로의 이동을 맡습니다.

분석 글은 curl 8.12.0에서 설정 파일 네 개로 2와 3을 더하는 예를 제시합니다. 출력은 A 변수에 x 다섯 개가 든 형태입니다. 실제 실행에는 자원 한계가 있습니다. 변수 확장 내용은 1천만 바이트로 제한되며, 설정 파일 포함은 중첩 호출을 만들어 각 단계가 끝날 때까지 C 스택 프레임과 파일을 유지합니다. 분석 글이 보고한 curl 8.12의 간단한 카운트다운 실험에서는 8MB 스택으로 922단계 실행한 뒤 세그멘테이션 오류가 났습니다.

curl 8.17.0의 변경은 설정 파일이 자기 자신을 계속 포함하는 재귀를 막기 위한 조치였습니다. curl 프로젝트의 변경 제안은 포함 단계의 상한을 5로 두고 재귀 포함을 오류 처리한다고 설명합니다. 분석 글은 이 제한이 제시한 튜링 완전성 구성의 반복 경로를 끊는다고 짚지만, 공식 변경 제안은 튜링 완전성을 변경 이유로 들지 않습니다.

이 결과는 curl 8.16에서 둠을 실행했다는 기록을 뜻하지 않습니다. 분석 글이 제시한 실행 예는 2와 3을 더하는 구성입니다. 글은 Bash 반복문으로 curl 설정을 단계별 실행하는 방식도 소개합니다. 이때 반복은 Bash가 맡으므로 curl 단독의 계산 구성과는 다릅니다.

자료: Nicolas Seriot / 정리·해설: Trawling

참고 자료

• tool_parsecfg: detect and error on recursive --config use by bagder · Pull Request #19168 · curl/curl — https://github.com/curl/curl/pull/19168
• curl/docs/cmdline-opts/variable.md at curl-8_12_0 · curl/curl · GitHub — https://github.com/curl/curl/blob/curl-8_12_0/docs/cmdline-opts/variable.md
• curl/src/tool_parsecfg.h at curl-8_17_0 · curl/curl · GitHub — https://github.com/curl/curl/blob/curl-8_17_0/src/tool_parsecfg.h
• curl - Changes in 8.17.0 — https://curl.se/ch/8.17.0.html