Programmatical النهج في جافا الملف المقارنة

Question

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

وبشكل أكثر تحديدا, ما أود القيام به هو أن تأخذ تمثيل عشري من .ملف exe ومقارنتها ضد سلسلة من التوقيع الفيروس.على هذا النهج في خطة لكسر ملف (exe) عرافة التمثيل في المجموعات الفردية N حرف (ie.10 عرافة حرف) و تفعل الشيء نفسه مع التوقيع الفيروس.انا تهدف إلى إجراء نوع من الاستدلال وبالتالي إحصائيا تحقق ما إذا كان هذا الملف exe X% من التشابه ضد الفيروسات المعروفة التوقيع.

أبسط و من المحتمل جدا بطريقة خاطئة فكرت في القيام بذلك ، مقارنة exe[n, n-1] ضد الفيروسات [n, n-1] حيث كل عنصر في مجموعة دون مجموعة ، وبالتالي exe1[0,9] ضد virus1[0,9].كل مجموعة فرعية سوف تكون متدرجة إحصائيا.

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

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

---

تعريف:متعددة الأشكال الخبيثة (virus, worm, ...) يحافظ على نفس وظائف الحمولة بأنها "الأصلي" نسخة ، في حين يبدو هياكل مختلفة (المتغيرات).وتحقيق ذلك من خلال رمز التشويش وبالتالي تغيير عرافة التوقيع.بعض التقنيات المستخدمة في تعدد الأشكال ؛ شكل التغيير (إدراج إزالة الفراغات) ، متغير إعادة تسمية بيان ترتيب غير المرغوب فيه رمز إلى بيان استبدال (x=1 تغييرات x=y/5 حيث y=5) ، مبادلة السيطرة البيانات.كثيرا مثل تحور فيروس انفلونزا وبالتالي التطعيم ليست فعالة متعددة الأشكال الخبيثة تحور لتجنب الكشف.

---

تحديث: بعد ننصح الرجال أعطاني في ما يتعلق القراءة ؛ فعلت ذلك ولكن هذا الخلط إلى حد ما لي أكثر.لقد وجدت عدة المسافة الخوارزميات التي يمكن أن تنطبق على مشكلتي ، مثل ؛

• أطول subsequence المشترك
• Levenshtein الخوارزمية
• نيدلمان–ونش الخوارزمية
• سميث–الملاح الخوارزمية
• بوير مور الخوارزمية
• أهو Corasick الخوارزمية

ولكن الآن أنا لا أعرف أي استخدام, أنهم جميعا يبدو أن تفعل نفس الشيء بطرق مختلفة.سأواصل البحث حتى أستطيع أن أفهم كل واحد أفضل ؛ ولكن في الوقت نفسه يمكن أن تعطيني رأيك في which might be more suitable حتى أستطيع أن تعطيه الأولوية خلال بحثي إلى دراسة أعمق.

---

تحديث 2: انتهى بي الأمر باستخدام خليط من LCSubsequence, LCSubstring و Levenshtein المسافة.شكرا لكم جميعا على الاقتراحات.

هناك نسخة من ورقة النهائية على جيثب

Answer 1

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

أيضا النظر في الأشكال الخبيثة هذا القطاع ينبغي أن توفر لك الكثير, لأنه في البيولوجيا يبدو كذلك من الصعب الحصول على مطابقة تامة.(للأسف أنا لست على علم المناسبة approximative البحث/خوارزميات مطابقة إلى نقطة لك.)

مثال واحد من هذا الاتجاه التكيف مع شيء من هذا القبيل أهو Corasick خوارزمية من أجل البحث عن العديد من البرمجيات الخبيثة التوقيعات في نفس الوقت.

وبالمثل ، خوارزميات مثل بوير مور خوارزمية تعطيك رائعة البحث أوقات التشغيل وخاصة بالنسبة أطول تسلسل (متوسط حالة O(N/M) لمدة نص حجم N التي كنت تبحث عن نمط من حجم M ، أيالتدرج الشبه خطي البحث مرات).

Answer 2

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

Answer 3

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

تعطي هذه الورقة ملخصًا جيدًا للمشكلة وكذلك بعض الأساليب في الاستشهادات التي تمت تجربتها.

ftp://ftp.computer.org/press/outonge/proceedings/patrick/apsec10/data/426a366.pdf

Answer 4

كما أشار شخص ما ، قد يساعد التشابه مع مشكلة المعروفة والمعلوماتية الحيوية. أطول فرعية مشتركة هشة للغاية ، مما يعني أن الاختلاف يمكن أن يرفع طول هذه السلسلة إلى النصف. تحتاج إلى شكل من أشكال محاذاة السلسلة ، ولكن أكثر كفاءة من Smith-Waterman. سأحاول أن أنظر إلى برامج مثل Blast أو Blat أو Mummer3 لمعرفة ما إذا كان بإمكانها تناسب احتياجاتك. تذكر أن المعلمات الافتراضية ، بالنسبة لهذه البرامج ، تستند إلى تطبيق علم الأحياء (كم يجب معاقبة الإدراج أو الاستبدال على سبيل المثال) ، لذلك ربما يجب أن تنظر في إعادة تقدير المعلمات بناءً على مجال التطبيق الخاص بك ، وربما بناءً على ملف عدة التدريبات. هذه مشكلة معروفة لأنه حتى في علم الأحياء ، تتطلب التطبيقات المختلفة معلمات مختلفة (على سبيل المثال ، على المسافة التطورية لثنين من الجينوم للمقارنة). من الممكن أيضًا أنه حتى في الافتراضي ، قد ينتج عن إحدى هذه الخوارزميات نتائج قابلة للاستخدام. أفضل ما في الأمر هو أن يكون لديك نموذج توليدي لكيفية تغيير الفيروسات والتي يمكن أن توجهك في خيار الأمثل للمسافة والخوارزمية المقارنة.