Skip to content

Unbounded recursion / stack exhaustion

Garantili bir sonlanma koşulundan yoksun recursion (veya herhangi bir unbounded stack büyümesi), stack pointer'ı stack'i tüketene kadar aşağı sürer — crash ederek veya stack-clash varyantında, guard page'i atlayıp komşu bir mapping'e atlayarak.

Mechanism

CWE-674 (Uncontrolled Recursion), ne kadar recursion gerçekleştiğini kontrol etmedeki başarısızlıktır, "allocate edilmiş bellek veya program stack'i gibi aşırı kaynak tüketerek". Her call, daha düşük adreslere doğru aşağı büyüyen bir stack'e yeni bir frame (return address, kaydedilmiş register'lar, local'ler) push eder. Güvenilir bir base case olmadan — veya asla true olmayan bir koşulla kapılanmış bir base case ile — stack pointer stack region'ının altını geçerek yürür.

Note

Stack'in altı normalde bir guard page ile korunur: stack ona dokunduğu anda bir page fault (SIGSEGV) tetikleyen, map edilmemiş bir page; tükenmeyi temiz bir crash'e çevirir. Qualys Stack Clash araştırması bu korumanın bir deliği olduğunu gösterdi: "eğer stack-pointer guard-page'in üzerinden 'atlarsa' -- yani guard-page'e erişmeden stack'ten başka bir bellek bölgesine taşınırsa -- o zaman hiçbir page-fault exception'ı oluşmaz." Büyük per-frame local'lere (veya alloca/VLA'lara) sahip derin recursion, stack pointer'ı bir kerede bir page'den fazla ilerletebilir, guard page'in üzerinden adımlayıp doğrudan aşağıdaki heap'e, bir library mapping'ine veya mmap region'ına basabilir — burada sonraki write'lar komşu live veriyi bozar. Düz stack tükenmesi (DoS) ile stack-clash (potansiyel memory corruption / privilege escalation) arasındaki ilişki budur.

Walkthrough

Base case'i ulaşılamaz olan bir recursion (klasik CWE-674 biçimi) stack'i tüketir:

#include <stdio.h>

unsigned long depth = 0;
void recurse(void) {
    char scratch[4096];   // large frame: each call advances %rsp by >4 KiB
    scratch[0] = (char)depth;
    depth++;
    recurse();            // no termination condition -> unbounded
}

int main(void) { recurse(); }

Beklenen davranış: stack pointer guard page'e çarptığında process bir segmentation fault ile ölür.

$ gcc -O0 recurse.c -o recurse
$ ./recurse
Segmentation fault (core dumped)
$ ulimit -s
8192                       # 8 MiB default stack; ~2000 frames of 4 KiB exhaust it

Warning

Bunu salt bir crash yerine tehlikeli kılan şey, büyük char scratch[4096]'dır. Guard page'den (genellikle tek bir 4 KiB page) daha büyük per-frame allocation'lar, %rsp'nin guard'ı tamamen atlamasına izin verir — Stack Clash "jump" adımı. Attacker-controlled recursion derinliği (örn. derinlemesine iç içe JSON/XML, recursive parser'lar, regex), bunu uzaktan tetiklenebilir bir denial of service'e ve yazılabilir bir komşuya indiğinde bir corruption primitive'ine çevirir.

Stack-clash tarzı büyüme

Qualys'in dört adımlı deseni — Clash, Run, Jump, Smash — büyük stack buffer'ları tamamen yazmadan allocate eden routine'lere dayanır (advisory'leri glibc vfprintf(), getaddrinfo(), __dcigettext() ve ld.so token expansion'ını adlandırır). Unbounded recursion, "Jump"ın genel bir kaynağıdır: birçok frame, her biri %rsp'yi tek bir erişim guard page'e inmeyecek kadar uzağa taşır, stack altındaki region ile örtüşene kadar.

Detection

  • Fuzzing ve ASan, recursive crash'te stack-overflow raporlar.
  • Bir depth bound'undan veya her path'te ulaşılabilir bir sonlanma koşulundan yoksun recursive fonksiyonlar için static analysis / code review.
  • Recursion derinliğini süren attacker-controlled input'lara dikkat et (iç içe veri formatları, recursive descent parser'lar).

Mitigation

  • Her recursive routine'e garantili bir exit koşulu ver ve güvenli bir threshold aşıldığında abort eden açık bir depth counter ekle (CWE-674 mitigation'ı).
  • Derin recursion'ı, açık, bounded bir heap stack ile iteration'a çevir.
  • -fstack-clash-protection ile compile et, böylece compiler stack büyümesinin her yeni page'ini prob eder ve guard page'in her zaman dokunulduğu garantisini geri getirir.
  • Stack limitini artırmak (ulimit -s) yalnızca tükenmeyi geciktirir; bir düzeltme değildir.

References