هل يشكل Quicksort خطرًا أمنيًا محتملاً؟
https://stackoverflow.com/questions/1527136
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لقد تساءلت للتو عما إذا كان (مع بعض جنون العظمة الخطير وفي ظل ظروف معينة) استخدام فرز سريع يمكن اعتبار الخوارزمية بمثابة خطر أمني في التطبيق.
يتميز كل من التنفيذ الأساسي والإصدارات المحسنة مثل 3-median-quicksort بخصوصية التصرف المنحرف لبعض بيانات الإدخال، مما يعني أن وقت التشغيل يمكن أن يزيد بشكل كبير في هذه الحالات (مع وجود O(n^2) التعقيد) ناهيك عن إمكانية تجاوز سعة المكدس.
ومن ثم أرى إمكانية إلحاق الضرر من خلال توفير بيانات تم فرزها مسبقًا لبرنامج يجعل الخوارزمية تتصرف على هذا النحو، الأمر الذي قد يكون له عواقب غير متوقعة على سبيل المثال.تطبيق ويب متعدد العملاء.
هل هذه الحالة الغريبة تستحق أي اعتبار أمني (وبالتالي ستجبرنا على استخدام مقدمة- أو فرز الدمج بدلاً من)؟
يحرر: أعلم أن هناك طرقًا لمنع أسوأ حالات Quicksort، ولكن ماذا عن عمليات الفرز اللغوية المتكاملة (مثل الوسيط الثلاثي لـ .NET).هل سيكونون من المحرمات؟
المحلول
نعم، إنه مخاطر أمنية - DOS، لتكون محددة - والتي يتم تخفيفها بشكل تافه عن طريق إضافة فحص عمق العودية في QuickSort، والتبديل إلى شيء آخر بدلا من ذلك، إذا تم الوصول إلى عمق معين. إذا قمت بالتبديل إلى HeApsort، فستحصل خلع, ، ما هو ما يستخدمه العديد من تطبيقات STL في الواقع.
بدلا من ذلك، أنت فقط عشوائي اختيار عنصر المحور.
نصائح أخرى
يتم تنفيذ العديد من تطبيقات QuickSort باستخدام نسخة عشوائية من الخوارزمية. وبعد هذا يعني أ. هجوم دوس مع المدخلات المصنوعة خصيصا غير ممكن.
أيضا، حتى بدون هذا، فإن معظم مجموعات البيانات بسيطة للغاية بالنسبة إلى O (NLOG) مقابل O (N ^ 2). يجب أن يكون حجم المجموعة الفرز كبيرا جدا لتأثيره. حتى مع بضعة ملايين عنصر، فإن الفارق الزمني من المحتمل ألا يكون كبيرا جدا.
بشكل عام، أي تطبيق على شبكة الإنترنت معينة باستخدام QuickSort هو أكثر عرضة للغاية للحصول على الآخر الأمان عيوب.
نلقي نظرة على هذا السؤال (والجواب المحدد) الذي يناقش طرق تقليل أسواه QuickSort:
إذا كان الأداء أمرًا مهمًا، فقد يبدو QuickSort خيارًا سيئًا في معظم الظروف، سواء كان ذلك بسبب المخاوف الأمنية أم لا.هل هناك شيء يجعلك تخجل من الخوارزميات مثل Heapsort أو Mergesort؟
أعتقد أن هذا هو سؤال كبير جدا حيث كنت تستخدم الفرز السريع. باستخدام خوارزميات O (n ^ 2) على ما يرام تماما عند عملك مع صفائف من 5 عناصر، على سبيل المثال. من ناحية أخرى، عندما تكون هناك فرصة لأن البيانات يمكن أن تكون كبيرة بشكل كبير، خوفا من DOS ليست هي المشكلة الأولى التي ستواجهها - ستتوفر المشكلة الأولى طريقة أداء سيئة قبل أن تواجه مشكلة حقيقية. بالنظر إلى العدد الكبير من الخوارزميات الأخرى المتاحة، فقط استبدالها إذا كانت في موقع أساسي.
إنه، ولكن فقط في الحالات غير المرجحة للغاية - كلها سهلة لتجنب خوارزمية مصممة بشكل صحيح.
ولكن إذا كنت تريد أن تكون آمنة فائقة، فقد ترغب في استخدام شيء مثل خلع, ، الذي يبدأ ك QuickSort ولكن يتم تحويله إلى كومة الترتيب إذا كان يكتشف من عمق العودية التي بدأت الخوارزمية في الربعين.
تعديل: أرى بافل فازني على خلل.
ردا على سؤال تم تحريره: لم أختبر شخصيا كل مكتبة QuickSort الخاصة به، لكنني أشعر بالمراهنة المأمونة أن كلها قد تحقق منها جميعا في مكانها لتجنب أسوأ الحالات.
