اختبار العشوائية

الموسوعة الحرة

اختبار العشوائية (أو اختبار العشوائية )، في تقييم البيانات، هو اختبار يُستخدم لتحليل توزيع مجموعة من البيانات لمعرفة ما إذا كان يمكن وصفها بأنها عشوائية (بدون نمط). في النمذجة الاحتمالية ، كما هو الحال في بعض عمليات المحاكاة الحاسوبية ، يمكن التحقق من العشوائية المرجوة لبيانات الإدخال المحتملة، من خلال اختبار رسمي للعشوائية، لإثبات صلاحية البيانات للاستخدام في عمليات المحاكاة. في بعض الحالات، تكشف البيانات عن نمط غير عشوائي واضح، كما هو الحال مع ما يُسمى "التسلسلات في البيانات" (مثل توقع قيم عشوائية من 0 إلى 9، ولكن نجد "4 3 2 1 0 4 3 2 1..." ونادرًا ما تتجاوز القيمة 4). إذا فشلت مجموعة بيانات مُختارة في الاختبارات، فيمكن تغيير المعلمات أو استخدام بيانات عشوائية أخرى تجتاز اختبارات العشوائية.

خلفية

تُعدّ مسألة العشوائية سؤالًا فلسفيًا ونظريًا هامًا. يمكن استخدام اختبارات العشوائية لتحديد ما إذا كانت مجموعة البيانات تحتوي على نمط واضح، مما يشير إلى أن العملية التي ولّدت هذه البيانات غير عشوائية بشكل ملحوظ. في معظم الأحيان، يركز التحليل الإحصائي عمليًا على إيجاد أنماط منتظمة في البيانات أكثر من تركيزه على اختبار العشوائية. العديد من "مولدات الأرقام العشوائية" المستخدمة اليوم مُعرّفة بواسطة خوارزميات، وبالتالي فهي في الواقع مولدات أرقام شبه عشوائية . تُسمى المتتاليات التي تُنتجها هذه المولدات متتاليات شبه عشوائية. لا تُنتج هذه المولدات دائمًا متتاليات عشوائية بالقدر الكافي، بل قد تُنتج متتاليات تحتوي على أنماط. على سبيل المثال، يفشل روتين RANDU سيئ السمعة فشلًا ذريعًا في العديد من اختبارات العشوائية، بما في ذلك الاختبار الطيفي .

استخدم ستيفن وولفرام اختبارات العشوائية على مخرجات القاعدة 30 لدراسة قدرتها على توليد أرقام عشوائية، [ 1 ] على الرغم من أنه تبين أن حجم المفتاح الفعال أصغر بكثير من حجمه الفعلي [ 2 ] وأن أداءها ضعيف في اختبار مربع كاي . [ 3 ] إن استخدام مولد أرقام عشوائية مصمم بشكل سيئ قد يُشكك في صحة التجربة من خلال انتهاك الافتراضات الإحصائية. على الرغم من وجود تقنيات اختبار إحصائية شائعة الاستخدام مثل معايير المعهد الوطني للمعايير والتكنولوجيا (NIST)، فقد أظهر يونغجي وانغ أن معايير NIST غير كافية. علاوة على ذلك، صمم يونغجي وانغ [ 4 ] تقنيات اختبار إحصائية قائمة على المسافة وأخرى قائمة على قانون اللوغاريتم المتكرر. باستخدام هذه التقنية، اكتشف يونغجي وانغ وتوني نيكول [ 5 ] نقاط الضعف في مولدات الأرقام العشوائية الزائفة شائعة الاستخدام، مثل إصدار دبيان المعروف من مولد الأرقام العشوائية الزائفة OpenSSL، والذي تم إصلاحه في عام 2008.

اختبارات محددة للعشوائية

استُخدم عدد قليل نسبيًا من أنواع مولدات الأرقام العشوائية (الزائفة) في التطبيقات العملية. ويمكن الاطلاع عليها في قائمة مولدات الأرقام العشوائية ، وتشمل ما يلي:

تتفاوت هذه المولدات المختلفة في درجات نجاحها في اجتياز مجموعات الاختبارات المعتمدة. تفشل العديد من المولدات الشائعة الاستخدام في الاختبارات بدرجات متفاوتة، بينما تم تجاهل مولدات أخرى "أفضل" وأقدم (بمعنى أنها اجتازت جميع مجموعات الاختبارات الحالية وكانت موجودة بالفعل) إلى حد كبير.

توجد العديد من المقاييس العملية للعشوائية في التسلسلات الثنائية . تشمل هذه المقاييس تلك القائمة على الاختبارات الإحصائية ، والتحويلات ، والتعقيد ، أو مزيج منها. من أشهر مجموعات الاختبارات وأكثرها استخدامًا مجموعة اختبارات Diehard ، التي قدمها مارساجليا، والتي تم توسيعها لاحقًا لتشمل مجموعة TestU01 بواسطة ليكويير وسيمارد. اقترح إس. كاك استخدام تحويل هادامارد لقياس العشوائية ، ثم طوره كل من فيليبس، ويون، وهوبكنز، وبيث وداي، وموند، ومارساجليا وزمان. [ 6 ]

تُقدّم العديد من هذه الاختبارات، ذات التعقيد الخطي، مقاييس طيفية للعشوائية. وقد زعم كلٌّ من ت. بيث وزد. داي إثبات أن تعقيد كولموغوروف والتعقيد الخطي متطابقان عمليًا، [ 7 ] على الرغم من أن واي. وانغ أثبت لاحقًا عدم صحة ادعاءاتهما. [ 8 ] ومع ذلك، فقد برهن وانغ أيضًا على أن تعقيد كولموغوروف بالنسبة لمتتاليات مارتن-لوف العشوائية هو نفسه تقريبًا تعقيدها الخطي.

تُتيح هذه الاختبارات العملية مقارنة عشوائية السلاسل النصية . من الناحية الاحتمالية، تتمتع جميع السلاسل النصية ذات الطول المحدد بنفس درجة العشوائية. مع ذلك، تختلف السلاسل النصية في تعقيد كولموغوروف. على سبيل المثال، لننظر إلى السلسلتين التاليتين.

السلسلة 1:0101010101010101010101010101010101010101010101010101010101010101
السلسلة 2:1100100001100001110111101110110011111010010000100101011110010110

يمكن وصف السلسلة الأولى وصفًا لغويًا موجزًا: "32 تكرارًا للرقم '01'". يتكون هذا الوصف من 22 حرفًا، ويمكن بناؤه بكفاءة باستخدام بعض المتتاليات الأساسية. أما السلسلة الثانية، فلا يوجد لها وصف بسيط واضح سوى كتابة السلسلة نفسها، والتي تتكون من 64 حرفًا، كما لا يوجد لها تمثيل دالة أساسية فعال مماثل . باستخدام اختبارات هادامارد الطيفية الخطية (انظر تحويل هادامارد )، سيتبين أن المتتالية الأولى أقل عشوائية بكثير من الثانية، وهو ما يتوافق مع الحدس.

تطبيقات برمجية بارزة

انظر أيضاً

ملحوظات

  1. ↑ وولفرام، ستيفن (2002). نوع جديد من العلوم . وولفرام ميديا، إنك. الصفحات 975-976 . ISBN  978-1-57955-008-0.
  2. ↑ ويلي ماير؛ أوتمار ستافيلباخ (1991). "تحليل المتتاليات شبه العشوائية المولدة بواسطة الأوتوماتا الخلوية". التطورات في علم التشفير - يورو كريبت 91. سلسلة محاضرات في علوم الحاسوب. المجلد 547. الصفحات 186-199 . doi : 10.1007/3-540-46416-6_17 . ISBN   978-3-540-54620-7.
  3. ↑ موشيه سيبر؛ ماركو توماسيني (1996). "توليد مولدات أرقام عشوائية متوازية باستخدام البرمجة الخلوية". المجلة الدولية للفيزياء الحديثة ج . 7 (2): 181-190 . Bibcode : 1996IJMPC...7..181S . CiteSeerX 10.1.1.21.870 . doi : 10.1142/S012918319600017X . .
  4. ↑ يونغجي وانغ. حول تصميم اختبارات LIL للمولدات (شبه) العشوائية وبعض النتائج التجريبية، http://webpages.uncc.edu/yonwang/ ، 2014
  5. ↑ وانغ، يونغجي؛ نيكول، توني (2014). "الخصائص الإحصائية للمتتاليات شبه العشوائية وتجارب باستخدام PHP و Debian OpenSSL". أمن الحاسوب - ESORICS 2014. سلسلة محاضرات في علوم الحاسوب. المجلد 8712. الصفحات 454-471 . doi : 10.1007/978-3-319-11203-9_26 . ISBN   978-3-319-11202-2.
  6. ↑ تيري ريتر، "اختبارات العشوائية: مسح للأدبيات"، صفحة الويب: CBR-rand .
  7. ↑ بيث، توماس؛ داي، زونغ-دو (1990). "حول تعقيد المتتاليات شبه العشوائية - أو: إذا كان بإمكانك وصف متتالية، فلا يمكن أن تكون عشوائية". التطورات في علم التشفير - يورو كريبت 89. سلسلة محاضرات في علوم الحاسوب. المجلد 434. الصفحات 533-543 . doi : 10.1007/3-540-46885-4_51 . ISBN   978-3-540-53433-4.
  8. ↑ وانغ، يونغجي (1999). "التعقيد الخطي مقابل العشوائية الزائفة: حول نتيجة بيث وداي". التطورات في علم التشفير - ASIACRYPT'99 . سلسلة محاضرات في علوم الحاسوب. المجلد 1716. الصفحات 288-298 . doi : 10.1007/978-3-540-48000-6_23 . ISBN   978-3-540-66666-0.
  9. ↑ ENT: برنامج اختبار تسلسل الأرقام العشوائية الزائفة ، فورميلاب، 2008.
  10. ↑ مجموعة اختبار إحصائية لمولدات الأرقام العشوائية والزائفة لتطبيقات التشفير ، منشور خاص 800-22 مراجعة 1أ، المعهد الوطني للمعايير والتكنولوجيا ، 2010.
  11. ↑ تطبيق مجموعة الاختبارات الإحصائية للمعهد الوطني للمعايير والتكنولوجيا