Property-Preserving Hashing for $\ell_1$-Distance Predicates: Applications to Countering Adversarial Input Attacks

ملخص تقني لورقة بحثية بعنوان: "التجزئة الحافظة للخصائص لمسند مسافة $\ell_1$: تطبيقات لمواجهة هجمات المدخلات العدائية" من إعداد أسغار، وتشانغ، وكافار.

1. بيان المشكلة

السياق: تُستخدم التجزئة الإدراكية (Perceptual hashing) على نطاق واسب في الكشف عن الصور المتشابهة (مثل حماية حقوق الطبع والنشر، أو التعرف على الوجوه، أو الإشراف على المحتوى) من خلال توليد ملخصات تجزئة مدمجة تحافظ على التشابه البصري.
الثغرة الأمنية: تُظهر الدراسات الحديثة أن التجزئة الإدراكية عرضة لـ هجمات التهرب العدائية (adversarial evasion attacks). حيث يمكن للمهاجمين إدخال اضطرابات صغيرة غير محسوسة على الصورة (غالباً ما يتم تحسينها باستخدام مسافة $\ell_2$) بحيث تبدو الصورة الناتجة متطابقة تماماً بالنسبة للإنسان، ولكنها تنتج ملخص تجزئة مختلفاً تماماً، مما يؤدي إلى التهرب من الكشف.
الفجوة: تعتمد التجزية الإدراكية القياسية على ضمانات تشابه احتمالية، مما يعني وجود احتمال غير ضئيل بأن تنتج صور متشابهة ملخصات تجزئة مختلفة. هذا "خطأ الصحة" (correctness error) يوفر للمهاجم المساحة اللازمة لصياغة الأمثلة العدائية.
الهدف: يهدف المؤلفون إلى بناء مخطط تجزئة حافظ للخصائص (PPH) مخصص لـ مسافة $\ell_1$ المسندية ( $\ell_1$-distance predicates). وخلافاً للتجزئة القياسية، يضمن نظام PPH أنه إذا استوفت مدخلان خاصية معينة (على سبيل المثال، المسافة $\le t$)، فإن ملخصات التجزئة الخاصة بهما ستُقيم دائماً بـ "صحيح" (true) مع خطأ ضئيل جداً، حتى في وجود مهاجم يعرف معاملات دالة التجزئة.

2. المنهجية

الحل المقترح هو بناء مبتكر لـ PPH يعتمد على المسافة غير المتماثلة لـ $\ell_1$ وأكواد تصحيح الأخطاء المستمدة من الجبر متعدد الحدود.

أ. المسند (The Predicate)

يحدد المخطط مسند مسافة $\ell_1$ غير متماثل $P_{as}(x, y)$ لمتجهين من الصور (متجهات) $x, y \in \mathbb{Z}_q^n$:
$$P_{as}(x, y) = 1 \iff \|y \dot{-} x\|_1 < t_+ \text{ and } \|x \dot{-} y\|_1 \le t_- - \delta$$
حيث:

• $x \dot{-} y$ هي العملية العنصرية $x_i - y_i$ (بأخذ القيمة صفر إذا كانت سالبة).
• $\| \cdot \|_1$ هي معيار $\ell_1$ القياسي.
• $t_+ + t_- = t$ هو العتبة الإجمالية.
• $\delta$ هو معامل عدد صحيح صغير لتقليل الإيجابيات الكاذبة في الإعداد غير القوي.
• هذا التعريف غير المتماثل أمر بالغ الأهمية لأنه يرتبط مباشرة بمعيار $\ell_2$ (المسافة الإقليدية) المستخدم في معظم الهجمات العدائية عبر المتراجحة $\|x-y\|_2 \le \|x-y\|_1 \le \sqrt{n}\|x-y\|_2$.

ب. البناء (الرسم متعدد الحدود - Polynomial Mapping)

يقوم جوهر المخطط برسم متجه الصورة $x$ إلى متعدد حدود $\sigma_x(z)$ فوق حقل منتهٍ $\mathbb{Z}_p$ (حيث $p > n$ عدد أولي):
$$\sigma_x(z) = \prod_{i=1}^n (1 - a_i z)^{x_i} \pmod{z^{t+1}}$$
حيث $a = (a_1, \dots, a_n)$ هو متجه من العناصر المختلفة غير الصفرية من $\mathbb{Z}_p$.

الخصائص الرياضية الرئيسية:

1. معادلة المفتاح: بناءً على أعمال تاليني وروز، يستخدم المخطط المتطابقة:
   $$\sigma_x(z) \cdot \sigma_{y \dot{-} x}(z) = \sigma_y(z) \cdot \sigma_{x \dot{-} y}(z)$$
2. خوارزمية التقييم (evalh): للتحقق مما إذا كان $P_{as}(x, y) = 1$:
   • حساب $\tilde{\sigma}_{x,y}(z) = \sigma_x^{-1}(z) \cdot \sigma_y(z) \pmod{z^{t+1}}$.
   • تشغيل خوارزمية إقليدس الممتدة (EEA) على المدخلات $z^{t+1}$ و $\tilde{\sigma}_{x,y}(z)$.
   • التوقف عندما يكون درجة الباقي $r_k(z)$ أقل من أو تساوي $t_+$.
   • تخرج الخوارزمية القيمة 1 إذا كانت درجة المعامل المساعد $u_k(z)$ أقل من أو تساوي $t_- - \delta$.
   • هذا يتحقق فعلياً مما إذا كانت درجات متعددات الحدود "الخطأ" $\sigma_{y \dot{-} x}$ و $\sigma_{x \dot{-} y}$ تقع ضمن العتبات، وهو ما يتوافق مع شرط مسافة $\ell_1$.

ج. النموذج الأمني

• المتانة (Robustness): المخطط قوي ضد الأخطاء أحادية الجانب (الأخطاء السلبية: $P(x,y)=1$ ولكن evalh تعطي 0). وهذا أمر بالغ الأهمية لمنع الهجمات العدائية.
• مقاومة التصادم: بينما يمكن نظرياً حدوث أخطاء صفرية الجوانب (الإيجابيات الكاذبة)، أظهر المؤلفون أن احتمال حدوث ذلك ضئيل جداً ($p^{-\delta}$) للمعاملات العملية.
• مقاومة الانعكاس: استعادة الصورة الأصلية $x$ من ملخص التجزئة (معاملات متعدد الحدود) يتطلب حل نظام من المعادلات الذي يستحيل حسابياً ($O(q^n)$) بدون المتجه السري $a$.

3. المساهمات الرئيسية

1. أول PPH لمسافة $\ell_1$: هذا هو أول بناء لتجزئة حافظة للخصائص لمسند مسافة $\ell_1$ غير المتماثلة. كانت الأعمال السابقة محدودة بمسافة هامينج (Hamming distance).
2. الحدود النظرية: اشتق المؤلفون حدوداً دنيا لنسبة الضغط (حجم ملخص التجزئة $m$). وأظهروا أن مخططهم يحقق ضغطاً قريباً من الحد الأدنى النظري ($m \approx t \log_2 n$)، وهو أصغر بكثير من حجم الصورة ($n \log_2 q$).
3. تحليل الجدوى: أثبتوا أن فك ترميز قائمة المتلازمات (syndrome list decoding) (وهي تقنية شائعة لتجزئات مسافة هامينج) ليس ممكناً لمسافة $\ell_1$ لأن حجم كرة $\ell_1$ ينمو بشكل أسي، مما يجعل قائمة المرشحين المحتملين كبيرة جداً. يتجاوز نهجهم القائم على كثيرات الحدود هذه المشكلة.
4. آلية الدفاع العدائي: من خلال فرض عتبة صارمة لمسافة $\ell_1$، يُجبر المخطط المهاجمين على إدخال ضوضاء كبيرة بما يكفي لانتهاك العتبة للتهرب من الكشف. هذه الضوضاء ستؤدي حتماً إلى تدهور جودة الصورة (زيادة نسب LPIPS وتغير البكسلات) إلى مستوى ملحوظ للبشر، مما يبطل مفعول الهجمات "غير المحسوسة".

4. النتائج التجريبية

قام المؤلفون بتنفيذ المخطط باستخدام مكتبة galois في بايثون واختبروه على مجموعة بيانات Imagenette (9,459 صورة RGB، بحجم $224 \times 224$).

• الكفاءة:
  • الصور الصغيرة (28x28): وقت التقييم حوالي 0.078 ثانية.
  • الصور الكبيرة (224x224): من خلال تقسيم الصور إلى 1,000 كتلة، يبلغ وقت التقييم حوالي 0.0128 ثانية لكل كتلة (قابل للتوازي بشكل كبير).
  • التعقيد: توليد التجزئة هو $O(nt^2)$، والتقييم هو $O(t^2)$.
• مقاومة الهجوم العدائي:
  • تم الاختبار ضد هجمات FGSM و PGD.
  • للتهرب من الكشف (أي لجعل مسافة $\ell_1$ تتجاوز العتبة $t$)، يجب على المهاجم زيادة معامل الضوضاء $\epsilon$.
  • النتيجة: عند العتبة التي ينجح فيها الهجوم في التهرب من التجزئة، ترتفع درجة LPIPS (تشابه رقعة الصورة الإدراكية المتعلمة) بشكل كبير (مثلاً > 0.5)، وتصبح نسبة تغير البكسلات كبيرة. هذا يعني أن الصورة "المتهربة" لم تعد متشابهة إدراكياً مع الأصلية، مما يهزم الغرض من الهجوم.
• المتانة تجاه التحويلات: يقاوم المخطط أيضاً التحويلات البسيطة (السطوع، التباين) ما لم تكن التغييرات شديدة بما يكفي لتغيير مسافة $\ell_1$ بشكل كبير.

5. الأهمية والخاتمة

• تحول في النموذج: ينتقل البحث من التجزئة الإدراكية الاحتمالية إلى الحفاظ الحتمي للخصائص مع معدلات خطأ ضئيلة، مما يغلق الفجوة التي تستغلها الهجمات العدائية.
• المنفعة العملية: النظام كفء بما يكفي للنشر في العالم الحقيقي (تقييم أقل من ثانية) ويمكن موازاته بسهولة.
• الآثار الأمنية: يوضح العمل أنه من الممكن تصميم أنظمة تحقق من الصور حيث تكون الأمن (مقاومة التهرب) والمنفعة (جودة الصورة) مرتبطتين مباشرة. لا يمكن للمهاجم إخفاء تعديل ضار دون جعل التعديل واضحاً بصرياً.
• العمل المستقبلي: يشير المؤلفون إلى أنه بينما يتعامل المخطط مع مسافة $\ell_1$ غير المتماثلة بقوة، فإن توسيع ذلك ليشمل مسافة $\ell_1$ الدقيقة أو المسافة الإقليدية ($\ell_2$) مع القوة الكاملة يظل مشكلة مفتوحة. بالإضافة إلى ذلك، فإن إثبات أن المخطط "خفي بشكل مثبت" (أي لا يمكن تمييزه عن العشوائي) هو هدف مستقبلي.

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