Non-Transitive Comparators Explained: لما الـ Sorting يمشي برا الـ Array بهدوء

بتدي لـ sorting routine قائمة أرقام ودالة مقارنة. هو بيوعدك إنه هيرتب كل حاجة. اللي بيحصل فعليًا تحت ظروف معينة إنه بيمشي بعد نهاية الـ array ويبدأ يكتب في اللي بعده على الـ stack.

دي قوة الـ non-transitive comparator الهادية.

معظم المطورين بيتعاملوا مع دوال المقارنة كأنها علاقات رياضية نقية. بيفترضوا إن لو a < b و b < c يبقى بالضرورة a < c. لما المقارنة تتنفذ كطرح signed بسيط، الافتراض ده بيموت أول ما الأرقام تكبر وتسبب overflow. الـ sorting algorithm مش بياخد باله. بيفضل ماشي على الشمال واثق إنه هيلقى حد سفلي مناسب، وفي الآخر بيتعامل مع الذاكرة المجاورة كأنها جزء من الـ array.

المقال ده بيمشي مع الفكرة من الأول، بيوري إزاي الـ overflow بيخلق السلوك غير الـ transitive، وبيعرض مسار استغلال عملي بيحول الـ write لـ leak وبعدين لـ code execution، وبيخلص بدفاعات عملية.

---

إيه هو الـ Non-Transitive Comparator أصلًا؟

العلاقة تكون transitive لما الشرط ده يتحقق دايمًا:

لو a < b و b < c، يبقى a < c

معظم خوارزميات الـ sorting في الكتب معتمدة على الخاصية دي (مع الـ reflexivity والـ totality) عشان تضمن الترتيب الصحيح، والأهم، عشان تفضل جوه حدود الـ array.

دلوقتي شوف comparator C تقليدي:

int compar(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

على الورق بيرجع قيمة سالبة لما a < b، صفر لما يكونوا متساويين، وموجبة لما a > b. في الواقع، لما الفرق يعدي نطاق الـ signed integer، النتيجة بتعمل wrap around. العلاقة الرياضية بتنهار.

مثال عملي مع 32-bit signed integers:

a =  2_000_000_000
b = -2_000_000_000
c =  1_000_000_000

• a - b بيعمل overflow ويبقى سالب → الـ comparator بيقول a < b
• b - c بيعمل underflow ويبقى موجب → الـ comparator بيقول b > c
• a - c بيفضل موجب → الـ comparator بيقول a > c

دلوقتي عندك a < b و b > c ومع ذلك a > c. العلاقة مش transitive تاني.

نفس النمط بيظهر مع 64-bit longs. الأرقام بس بتبقى أكبر قبل ما تعمل wrap. الفكرة الأساسية واحدة: الطرح signed مش ترتيب كلي بمجرد ما الـ overflow ممكن.

ليه خوارزميات الـ sorting بتهتم

في glibc الـ qsort (في الإصدارات القديمة واللسه شائعة) فيه مرحلة insertion-sort cleanup بعد شغل الـ quicksort الأساسي. المرحلة دي بتمشي على الشمال من العنصر الحالي بتدور على مكان الإدراج الصح. الـ loop بيفترض إن الحد الشمالي للـ array هيقفها في الآخر. لما الـ comparator يقدر يرجع “أقل من” حتى للحد الشمالي الحقيقي، المشي بيستمر في أي ذاكرة قاعدة قبل الـ array.

الـ insertion loop شكله تقريبًا كده:

tmp_ptr = run_ptr - size;
while ((*cmp)((void *)run_ptr, (void *)tmp_ptr) < 0)
    tmp_ptr -= size;

لو الـ cmp فضل يرجع قيم سالبة حتى لما tmp_ptr خلاص طلع من الـ array، الـ pointer بيفضل يتحرك. كل خطوة بتبقى write محتمل لما الخوارزمية بعد كده تعمل swap أو shift للعناصر.

ده الـ primitive كله: مشي متحكم فيه بعد بداية الـ array، مدفوع بقيم مختارة بعناية بتسبب overflow في الـ comparator.

---

ليه الموضوع يهمك؟

الـ sorting موجود في كل حتة. قواعد بيانات، language runtimes، network stacks، loaders للإعدادات، game engines، وخدمات utility صغيرة كلها بتستدعي routines ترتيب. ناس كتير لسه بتقبل custom comparators مكتوبة كـ arithmetic بسيط.

الـ out-of-bounds write الناتج غالبًا بيكون على الـ stack، جنب:

• Saved return addresses
• Function pointers (بما فيهم جدول الـ comparators نفسه)
• Arguments بتاعة format strings بتستخدم في طباعة النتائج
• Buffers محلية تانية ممكن تتنقل لمنطقة الرؤية

لما تتحكم في write خارج الحدود نسبة لـ array معروف، الـ primitives الكلاسيكية بتبقى متاحة:

• Partial pointer overwrites بتطلع leaks
• GOT overwrites بتحول library call لاحق لـ function عشوائية
• Stack pivots أو function-pointer corruption بتوصل لـ code execution

باختصار، باج “بريء” في المقارنة يقدر يبقى primitive كامل لـ memory corruption من غير مجهود إضافي كبير من المهاجم. الـ sorting routine هو اللي بيحمل الجزء التقيل.

اختيار التصميم	الخطر الأساسي
طرح signed عادي في الـ comparator	ترتيب غير transitive، مشي برا الحدود
عدد عناصر كبير تحت ذاكرة منخفضة	بيجبر مسار الـ insertion-sort
Array جنب pointers على الـ stack	الـ pointers المجاورة بتبقى writable
طباعة بعد الـ sorting	بتحول الـ pointers المتنقلة لـ leaks
GOT قابل للكتابة + libc معروف	بتحول الـ leaks لـ code execution

الفرق المهم بين زيادة تكلفة التحليل ونقل القرار فعليًا برا الـ client. الـ non-transitive comparator بيزود التكلفة بس لحد ما حد يرسم خريطة الـ overflow.

---

مثال عملي / Scenario

تخيل خدمة صغيرة بتخلي المستخدمين يرتبوا arrays من integers أو longs تحت memory limit قابل للتعديل. الخدمة فيها ميزتين مهمتين:

1. خيار تقليل الذاكرة بيخفض address-space limit بتاع الـ process (RLIMIT_AS).
2. endpoint للـ sorting بياخد حجم الـ array واتجاه (ascending أو descending) والقيم نفسها.

لما الـ memory limit يتظبط منخفض كفاية، الـ malloc جوه qsort بيفشل. الـ glibc ساعتها بيروح لمسار بيستخدم الـ stack للتخزين المؤقت وفي الآخر بيشغل insertion-sort cleanup. المسار ده هو الكود الضعيف.

اكتشاف الـ primitive

بتلاحظ إن الـ comparators طرح signed بسيط. وبتلاحظ كمان إن الخدمة بتديك تحكم في القيم جوه الـ array وفي الـ memory limit. لما تزبط RLIMIT_AS ضيق، بتجبر المسار البطيء. لما تغذي الـ sorter بـ array متظبط من قيم “موجبة” و”سالبة” (مختارة عشان الـ overflow يطلع نتائج غير transitive)، مرحلة الـ insertion بتمشي بعد بداية الـ array.

كل خطوة في المشي بتعمل write. بالتحكم في القيم بتتحكم في مسافة المشي وفي الداتا اللي بتتكتب.

الإعداد النموذجي شكله كده:

1. خفض RLIMIT_AS عشان malloc يفشل
2. جهز array أول عنصر فيه هو القيمة اللي عايز تزرعها
3. املأ باقي الـ array بقيم تجبر الـ comparator
   يفضل ماشي على الشمال (الـ "negative" companions اللي بتسبب overflow)
4. استدعي الـ sorter
5. لاحظ إن بيانات الـ stack المجاورة اتكتب فوقها

مسافة المشي بتتحدد بعدد المرات اللي الـ comparator بيرجع فيها سالب قبل ما يرجع غير سالب في الآخر. ده تحت سيطرة المهاجم بالكامل.

تحويل الـ write لـ leak

الـ array عايش على الـ stack جنب جدول من function pointers (الـ comparators نفسها) وpointers بتاعة format strings بتستخدم في طباعة النتائج. بالمشي مسافة قصيرة تقدر تعمل overwrite لـ low byte من pointer، تنقله لمنطقة تحت سيطرتك، وبعدين تطلب من الخدمة تطبع الـ array. القيمة المسربة بتديك PIE base.

تسلسل عملي:

- اعمل overwrite لـ low byte عشان function pointer معروف يتحرك لمنطقة الطباعة
- اطلب dump مرتب لشريحة صغيرة من الـ array
- فسر القيمة المطبوعة
- اطرح الـ offset المعروف للدالة دي عشان تسترجع base الـ binary

لأن الخدمة أصلًا بتطبع النتائج المرتبة، مش محتاج ثغرة information leak منفصلة. مسار الطباعة هو مسار الـ leak.

التصعيد لـ code execution

مع PIE base في إيدك تقدر تستهدف الـ Global Offset Table. overwrite لـ GOT entry (مثلًا printf) بعنوان libc معروف بيحول عملية print لاحقة لـ call عشوائي. overwrite تاني بيزرع system وpointer للـ string "/bin/sh". sort إضافي بيشغل الـ call ويبقى عندك shell.

السلسلة كلها جوه الـ process الأصلي؛ مفيش ثغرات جديدة مطلوبة بعد الـ write غير الـ transitive الأول.

السلسلة عالية المستوى:

non-transitive OOB write
        ↓
partial pointer overwrite → PIE leak
        ↓
GOT overwrite (printf → system أو مشابه)
        ↓
زرع "/bin/sh" والاستدعاء
        ↓
shell

أفكار مجاورة ومتغيرات

• نفس الـ overflow بيشتغل على 32-bit و 64-bit integers؛ الثوابت بس بتتغير.
• الـ descending comparators (b - a) بتطلع الصورة المعكوسة لنفس الباج.
• لو الخدمة بتديك تختار حجم العنصر (char، short، int، long)، كل حجم بيدي stride مختلف للمشي وبالتالي مجموعة مختلفة من offsets الـ stack اللي توصلها.
• حدود موارد غير RLIMIT_AS ممكن كمان تجبر مسارات fallback في مكتبات تانية؛ النمط مش خاص بـ glibc qsort بس.

---

أمثلة كود ضعيفة

Comparator مكسور (C)

/* Vulnerable: signed subtraction بيعمل overflow وبيكسر الـ transitivity */
int broken_compar(const void *pa, const void *pb) {
    int a = *(const int *)pa;
    int b = *(const int *)pb;
    return a - b;   /* undefined behavior on overflow */
}

ليه خطر: أي caller بيفترض ترتيب كلي transitive (بما فيهم مرحلة insertion-sort في تطبيقات qsort كتير) ممكن يتأجبر يعدي حدود الـ array.

بدائل أأمن

/* Safe: مقارنة صريحة بتجنب الـ overflow */
int safe_compar(const void *pa, const void *pb) {
    int a = *(const int *)pa;
    int b = *(const int *)pb;
    if (a < b) return -1;
    if (a > b) return  1;
    return 0;
}

/* كمان safe: طرح unsigned أو استخدام checked arithmetic من <stdckdint.h> */
#include <stdckdint.h>

int checked_compar(const void *pa, const void *pb) {
    int a = *(const int *)pa;
    int b = *(const int *)pb;
    int diff;
    if (ckd_sub(&diff, a, b)) {
        /* حصل overflow؛ ارجع للـ relational operators */
        if (a < b) return -1;
        if (a > b) return  1;
        return 0;
    }
    return diff;
}

النسخة المصلحة مش بتعمل wrap أبدًا؛ العلاقة الرياضية بتفضل transitive على كل نطاق int.

إجبار المسار الضعيف (مفهومي)

/* خفض address-space limit عشان malloc جوه qsort يفشل */
struct rlimit rl = { .rlim_cur = 8192, .rlim_max = 8192 };
setrlimit(RLIMIT_AS, &rl);

/* دلوقتي استدعي qsort بعدد عناصر كافي والـ comparator المكسور.
   الـ glibc هيروح لمسار الـ insertion-sort اللي بيمشي برا الحدود. */
qsort(array, count, sizeof(*array), broken_compar);

harness بسيط بيوضح المشي

/* مفهومي فقط — مش exploit كامل */
long array[128];
array[0] = TARGET_VALUE;          /* القيمة اللي عايز تزرعها */
for (int i = 1; i < 128; i++)
    array[i] = NEGATIVE_COMPANION; /* بيجبر استمرار المشي على الشمال */

qsort(array, 128, sizeof(long), broken_compar);
/* slots الـ stack المجاورة اتكتبت فوقها دلوقتي */

---

الدفاع / إزاي تصلح

1. متنفذش comparators بطرح signed عادي. استخدم relational operators صريحة أو checked arithmetic. السطر الواحد return a - b; هو الـ foot-gun الكلاسيكي.

2. راجع كل call site لـ qsort و heapsort و mergesort ومقابلاتهم في الـ language runtimes. دور على custom comparators بتعمل arithmetic على القيم اللي بتتقارن. ركز خصوصًا على الكود اللي كمان بيلعب في حدود الموارد.

3. اتعامل مع RLIMIT_AS (وحدود الموارد المشابهة) كسطح هجوم. الكود اللي بيخفضها عن قصد محتاج يتراجع عشان مسارات الـ fallback اللي بتبقى أخطر تحت ذاكرة منخفضة. الجمع بين limit ضيق و sort كبير علامة حمراء.

4. فعل compiler warnings و sanitizers. -fsanitize=undefined و -Wsign-compare بيمسكوا ناس كتير من الباجز دي وقت البناء أو الاختبار. AddressSanitizer كمان هيفلج الـ out-of-bounds access النهائي بمجرد ما المشي يحصل.

5. فضل comparison helpers اللي المكتبة بتوفرها لما تكون موجودة (مثلًا std::less في C++ أو دوال المقارنة في معايير C الحديثة). أقل احتمال إنها تخبي overflow bugs.

6. فكر في استبدال qsort بخوارزميات مش معتمدة على مراحل insertion-sort cleanup، أو بتطبيقات اتحصنت ضد non-transitive comparators. بعض المكتبات الحديثة بتوثق إنها بتطلب strict weak ordering وهتوقف أو تتصرف غلط لو مش موجود؛ اعتبر ده ميزة مش باج.

7. افشل بالإغلاق على حدود موارد مشبوهة. لو process عمدًا حط RLIMIT_AS منخفض جدًا قبل sort كبير، سجلها وفكر ترفض العملية.

---

Testing / Audit Points

What to look for	Why it matters
الـ comparator بيستخدم a - b أو arithmetic مشابه	الـ overflow يقدر يكسر الـ transitivity
الخدمة بتوفر تحكم في memory limit	يقدر يجبر مسار الـ insertion-sort
أعداد عناصر كبيرة مقبولة	مطلوبة عشان نوصل للمسار البطيء
الـ array عايش على الـ stack جنب pointers	الـ OOB write بيبقى مفيد
النتائج بتتطبع بعد الـ sorting	بتحول الـ pointers المتنقلة لـ leaks
GOT قابل للكتابة + مكتبة معروفة	بتحول الـ leaks لـ code execution

أسئلة مراجعة سريعة:

1. هل أي comparator بيعمل arithmetic على القيم المتقارنة؟
2. هل المهاجم يقدر يأثر على حدود موارد بتأثر على الـ allocation جوه الـ sorter؟
3. هل الـ array المرتب جنب بيانات stack مهمة؟
4. هل الخدمة بتطبع النتائج بطريقة تكشف pointers متفسدة؟
5. هل إعادة كتابة مقارنة واحدة صريحة هتشيل كل فئة الباج دي؟

لو الإجابات نعم ونعم ونعم ونعم ونعم، لقيت مراسم شكلها sorting وبتتصرف كـ write primitive.

---

Common Myths

“الـ sorting آمن؛ هو بس بيرتب داتا.”

لا. الـ sorting بيرتب داتا حسب comparison function. لو الدالة دي بتكذب، الخوارزمية هترتب ذاكرة برا الـ array كمان.

“الـ integer overflow في comparator مجرد undefined behavior، مش قابل للاستغلال.”

الـ undefined behavior هو بالظبط اللي بيخلي الـ compiler والـ runtime يطلعوا النتائج غير الـ transitive اللي بتدفع المشي. في الممارسة الـ wrap-around موثوق كفاية إنه يتسكرپت.

“الـ glibc الحديث صلح الموضوع.”

في hardening اتضاف على السنين، بس أنظمة كتير لسه شغالة على إصدارات مسار الـ insertion-sort فيها ممكن يتأجبر. حتى لما المسار يختفي، نفس باج الـ comparator لسه يقدر يطلع نتائج غلط أو undefined behavior تاني.

“محتاج information leak منفصل.”

مش دايمًا. لو الخدمة أصلًا بتطبع الـ array المرتب، pointer متنقل بعناية بيبقى leak مجاني.

---

خلاصة

الـ sorting شكله من أأمن العمليات اللي برنامج ممكن يعملها. اديه comparison function بتكذب في ترتيب الأرقام الكبيرة والخوارزمية هتمشي برا نهاية الـ array بكل سرور. الـ write الناتج هادي، محدد بمجرد ما تفهم الـ overflow، وقوي كفاية إنه يحول خدمة بسيطة لـ compromise كامل.

البرنامج بيديك comparator. الـ sorter بيحول الـ comparator لمشي. الـ stack بيحول المشي لـ leak. الـ GOT بيحول الـ leak لـ shell.

أأمن comparator هو اللي مش بيعمل arithmetic على القيم اللي بيقارنها أصلًا.

---

References

• C standard, section on integer overflow and undefined behavior
• glibc source for qsort / _quicksort (historical insertion-sort path)
• OWASP – Integer Overflow
• CERT C Secure Coding – INT32-C (Ensure that operations on signed integers do not result in overflow)
• CWE-190: Integer Overflow or Wraparound
• CWE-787: Out-of-bounds Write