First Fit

Reading time: 4 minutes

First Fit

जब आप glibc का उपयोग करके किसी प्रोग्राम में मेमोरी को फ्री करते हैं, तो मेमोरी के टुकड़ों को प्रबंधित करने के लिए विभिन्न "बिन" का उपयोग किया जाता है। यहाँ दो सामान्य परिदृश्यों का एक सरल स्पष्टीकरण है: अनसॉर्टेड बिन और फास्टबिन।

Unsorted Bins

जब आप एक मेमोरी टुकड़ा फ्री करते हैं जो एक फास्ट टुकड़ा नहीं है, तो यह अनसॉर्टेड बिन में चला जाता है। यह बिन एक सूची की तरह कार्य करता है जहाँ नए फ्री किए गए टुकड़े सामने ( "हेड") में जोड़े जाते हैं। जब आप मेमोरी का एक नया टुकड़ा मांगते हैं, तो आवंटक अनसॉर्टेड बिन को पीछे ( "टेल") से देखता है ताकि एक ऐसा टुकड़ा ढूंढ सके जो आपके लिए पर्याप्त बड़ा हो। यदि अनसॉर्टेड बिन से कोई टुकड़ा आपके आवश्यक आकार से बड़ा है, तो इसे विभाजित किया जाता है, जिसमें सामने का भाग वापस किया जाता है और शेष भाग बिन में रहता है।

उदाहरण:

• आप 300 बाइट (a) आवंटित करते हैं, फिर 250 बाइट (b), a को फ्री करते हैं और फिर से 250 बाइट (c) मांगते हैं।
• जब आप a को फ्री करते हैं, तो यह अनसॉर्टेड बिन में चला जाता है।
• यदि आप फिर से 250 बाइट मांगते हैं, तो आवंटक a को टेल में पाता है और इसे विभाजित करता है, आपके अनुरोध के लिए उपयुक्त भाग लौटाते हुए और बाकी को बिन में रखते हुए।
• c पिछले a की ओर इशारा करेगा और a's से भरा होगा।

char *a = malloc(300);
char *b = malloc(250);
free(a);
char *c = malloc(250);

Fastbins

Fastbins छोटे मेमोरी टुकड़ों के लिए उपयोग किए जाते हैं। असंरचित बिन के विपरीत, फास्टबिन नए टुकड़ों को सिर में जोड़ते हैं, जिससे अंतिम-प्रविष्टि-प्रथम-निकासी (LIFO) व्यवहार उत्पन्न होता है। यदि आप मेमोरी का एक छोटा टुकड़ा मांगते हैं, तो आवंटक फास्टबिन के सिर से खींचेगा।

उदाहरण:

• आप चार टुकड़े 20 बाइट प्रत्येक (a, b, c, d) आवंटित करते हैं।
• जब आप उन्हें किसी भी क्रम में मुक्त करते हैं, तो मुक्त किए गए टुकड़े फास्टबिन के सिर में जोड़े जाते हैं।
• यदि आप फिर 20-बाइट का टुकड़ा मांगते हैं, तो आवंटक फास्टबिन के सिर से सबसे हाल ही में मुक्त किया गया टुकड़ा लौटाएगा।

char *a = malloc(20);
char *b = malloc(20);
char *c = malloc(20);
char *d = malloc(20);
free(a);
free(b);
free(c);
free(d);
a = malloc(20);   // d
b = malloc(20);   // c
c = malloc(20);   // b
d = malloc(20);   // a

अन्य संदर्भ और उदाहरण

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Use after free: एक उपयोगकर्ता वस्तु उत्पन्न करें, इसे मुक्त करें, एक वस्तु उत्पन्न करें जो मुक्त किए गए भाग को प्राप्त करती है और इसे लिखने की अनुमति देती है, पिछली स्थिति को ओवरराइट करते हुए user->password। उपयोगकर्ता को पुन: उपयोग करें ताकि पासवर्ड जांच को बायपास किया जा सके
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• कार्यक्रम नोट्स बनाने की अनुमति देता है। एक नोट में नोट की जानकारी malloc(8) में होगी (जिसमें एक फ़ंक्शन का पॉइंटर होगा जिसे कॉल किया जा सकता है) और एक अन्य malloc(<size>) का पॉइंटर होगा जिसमें नोट की सामग्री होगी।
• हमला 2 नोट्स (note0 और note1) बनाने का होगा जिनकी malloc सामग्री नोट की जानकारी के आकार से बड़ी होगी और फिर उन्हें मुक्त करें ताकि वे तेज़ बिन (या tcache) में जा सकें।
• फिर, एक और नोट (note2) बनाएं जिसमें सामग्री का आकार 8 हो। सामग्री note1 में होगी क्योंकि भाग को पुन: उपयोग किया जाएगा, जहां हम फ़ंक्शन पॉइंटर को win फ़ंक्शन की ओर इंगित करने के लिए संशोधित कर सकते हैं और फिर Use-After-Free note1 को नए फ़ंक्शन पॉइंटर को कॉल करने के लिए।
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• कुछ मेमोरी आवंटित करना, इच्छित मान लिखना, इसे मुक्त करना, पुनः आवंटित करना संभव है और चूंकि पिछले डेटा अभी भी वहां है, इसे भाग में नए अपेक्षित संरचना के अनुसार माना जाएगा जिससे मान सेट करना या ध्वज प्राप्त करना संभव होगा।
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• इस मामले में एक विशिष्ट भाग के अंदर 4 लिखना आवश्यक है जो पहला आवंटित किया जा रहा है (यहां तक कि सभी को बलपूर्वक मुक्त करने के बाद भी)। प्रत्येक नए आवंटित भाग में इसका संख्या सरणी अनुक्रमांक में संग्रहीत होता है। फिर, 4 भागों (+ प्रारंभ में आवंटित) को आवंटित करें, अंतिम में 4 होगा, उन्हें मुक्त करें और पहले को पुनः आवंटित करने के लिए मजबूर करें, जो अंतिम मुक्त भाग का उपयोग करेगा जिसमें 4 होगा।