ابحث عن التسلسلات المطابقة في ملفين ثنائيين

Question

اسمحوا لي أن أبدأ مع القليل من الخلفية.

هذا الصباح، أبلغ أحد مستخدمينا أن ملف إعداد Testuff قد تم الإبلاغ عن إصابته بفيروس بواسطة برنامج مكافحة الفيروسات CA.ولكوني واثقًا من أن هذه نتيجة إيجابية كاذبة، بحثت على الويب ووجدت أن مستخدمي برنامج آخر (SpyBot) أبلغوا عن نفس المشكلة.

والآن، بالنسبة للسؤال الفعلي.

بافتراض أن برنامج مكافحة الفيروسات يبحث عن توقيع ثنائي محدد في الملف، أود العثور على التسلسلات المطابقة في كلا الملفين، وآمل أن أجد طريقة لتعديل برنامج الإعداد لمنع ظهور هذا التسلسل.

لقد جربت ما يلي في بايثون، لكنه يعمل منذ فترة طويلة وكنت أتساءل عما إذا كانت هناك طريقة أفضل أو أسرع.

from difflib import SequenceMatcher

spybot = open("spybotsd160.exe", "rb").read()
testuff = open("TestuffSetup.exe", "rb").read()

s = SequenceMatcher(None, spybot, testuff)
print s.find_longest_match(0, len(spybot), 0, len(testuff))

هل هناك مكتبة أفضل لبيثون أو لغة أخرى يمكنها القيام بذلك؟نرحب أيضًا بطريقة مختلفة تمامًا لمعالجة المشكلة.

Answer 1

يرى أطول مشكلة فرعية مشتركة.أعتقد أن difflib يستخدم حل DP، وهو بالتأكيد بطيء جدًا لمقارنة الملفات التنفيذية.يمكنك أن تفعل ما هو أفضل بكثير باستخدام الأشجار/المصفوفات اللاحقة.

باستخدام بيرل الشجرة::لاحقة قد يكون الحل الأسهل.يبدو أنه يعطي جميع السلاسل الفرعية الشائعة في نطاق طول محدد:

@lcs = $tree->lcs;
@lcs = $tree->lcs($min_len, $max_len);
@lcs = $tree->longest_common_substrings;

Answer 2

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

Answer 3

لماذا لا تتصل بـ CA وتطلب منهم إخبارهم بما يبحثون عنه، عن هذا الفيروس؟

أو يمكنك نسخ الملف وتغيير كل بايت على حدة حتى يختفي التحذير (قد يستغرق بعض الوقت حسب الحجم).

من الممكن أن يكون اكتشاف الفيروس أكثر تعقيدًا من مجرد البحث عن سلسلة ثابتة.

Answer 4

ومن الأفضل ألا نتساءل عن التعقيد والوقت الذي تحتاجه هذه الأنواع من الخوارزميات.

إذا كان لديك اهتمام بهذا - هنا وثيقة .ps مرتبطة هنا يمكنك العثور على مقدمة جيدة لهذا الموضوع.

إذا كان هناك تطبيق جيد لهذه الخوارزميات، لا أستطيع أن أقول ذلك.

Answer 5

أظن أن البحث عن سلاسل ثنائية لن يساعدك.من المحتمل أن يقوم برنامج التثبيت ببعض الأشياء "المشبوهة".

ربما تحتاج إلى التحدث إلى CA وspybot حول إدراج برنامج التثبيت الخاص بك في القائمة البيضاء، أو حول سبب تشغيل التنبيه.