2025-11-16T07:49:19.632070

Psyzkaller: Learning from Historical and On-the-Fly Execution Data for Smarter Seed Generation in OS kernel Fuzzing

Liu, Zhang, Cheng et al.
Fuzzing has become a cornerstone technique for uncovering vulnerabilities and enhancing the security of OS kernels. However, state-of-the-art kernel fuzzers, including the de facto standard Syzkaller, struggle to generate valid syscall sequences that respect implicit Syscall Dependency Relations (SDRs). Consequently, many generated seeds either fail kernel validation or cannot penetrate deep execution paths, resulting in significant inefficiency. We hypothesize that SDRs can be effectively learned from both historic and present kernel execution data, and that incorporating these learned relations into fuzzing can substantially improve seed validity and diversity. To validate this, we propose an approach that utilizes the N-gram model to mine SDRs from the Dongting dataset-one of the largest Linux kernel execution datasets available-as well as from execution traces collected on the fly during fuzzing. The resulting model is used to continuously augment the Choice Table of Syzkaller to improve its seed generation and demonstrably increases the Shannon Entropy of the Choice Table throughout fuzzing, reflecting more empirically-grounded choices in expanding syscall sequences into valid and diverse seeds. In addition, we introduce a Random Walk strategy that instructs Syzkaller to construct seeds in a bidirectional manner to further diversify the generated seeds. We implement our approach in a prototype, Psyzkaller, built on top of Syzkaller. Experiments on three representative Linux kernel versions show that Psyzkaller improves Syzkaller's code coverage by 4.6%-7.0% in 48-hour fuzzing, while triggering 110.4%-187.2% more crashes. Moreover, our investigation shows that Psyzkaller discovered eight previously unknown kernel vulnerabilities, compared to only one found by Syzkaller.
academic

Psyzkaller: OS कर्नल फ़ज़िंग में स्मार्ट सीड जनरेशन के लिए ऐतिहासिक और ऑन-द-फ्लाई एक्सीक्यूशन डेटा से सीखना

मूल जानकारी

  • पेपर ID: 2510.08918
  • शीर्षक: Psyzkaller: Learning from Historical and On-the-Fly Execution Data for Smarter Seed Generation in OS kernel Fuzzing
  • लेखक: Boyu Liu, Yang Zhang, Liang Cheng, Yi Zhang, Junjie Fan, Yu Fu
  • वर्गीकरण: cs.CR (क्रिप्टोग्राफी और सुरक्षा)
  • प्रकाशन तिथि: 13 अक्टूबर, 2025
  • पेपर लिंक: https://arxiv.org/abs/2510.08918v1

सारांश

फ़ज़िंग ऑपरेटिंग सिस्टम कर्नल में कमजोरियों की खोज और सुरक्षा बढ़ाने के लिए एक मौलिक तकनीक बन गई है। हालांकि, Syzkaller सहित अत्याधुनिक कर्नल फ़ज़र्स निहित सिस्टम कॉल निर्भरताओं (SDRs) का सम्मान करने वाले प्रभावी सिस्टम कॉल अनुक्रमों को उत्पन्न करने में कठिनाई का सामना करते हैं। परिणामस्वरूप, कई उत्पन्न सीड्स या तो कर्नल सत्यापन में विफल होते हैं या गहरे निष्पादन पथों तक नहीं पहुंच सकते, जिससे महत्वपूर्ण अक्षमता होती है। यह पेपर मानता है कि SDRs को ऐतिहासिक और वर्तमान कर्नल निष्पादन डेटा से प्रभावी ढंग से सीखा जा सकता है, और इन सीखी गई संबंधों को फ़ज़िंग में शामिल करने से सीड वैधता और विविधता में उल्लेखनीय सुधार हो सकता है। इसे सत्यापित करने के लिए, लेखकों ने DongTing डेटासेट (Linux कर्नल निष्पादन डेटा के सबसे बड़े डेटासेट में से एक) और फ़ज़िंग प्रक्रिया के दौरान वास्तविक समय में एकत्र किए गए निष्पादन ट्रेस से SDRs को खनन करने के लिए N-gram मॉडल का उपयोग करने की एक विधि प्रस्तावित की है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

ऑपरेटिंग सिस्टम कर्नल आधुनिक कंप्यूटिंग प्लेटफॉर्म का एक महत्वपूर्ण घटक है, और कर्नल-स्तर की सुरक्षा समझौता हमलावरों को सिस्टम पर पूर्ण नियंत्रण प्राप्त करने की अनुमति देता है। वर्तमान कर्नल फ़ज़र्स का सामना करने वाली मुख्य समस्याएं हैं:

  1. सिस्टम कॉल निर्भरता (SDRs) पहचान में कठिनाई: कई उत्पन्न सिस्टम कॉल अनुक्रम (SCSs) SDRs का उल्लंघन करने के कारण अमान्य हैं
  2. सीड जनरेशन में कम दक्षता: अमान्य परीक्षण मामले जल्दी विफल हो जाते हैं, कोड अन्वेषण में बहुत कम योगदान देते हैं
  3. गहरे निष्पादन पथों तक पहुंचना कठिन: सिस्टम कॉल के बीच शब्दार्थ बाधाओं की समझ की कमी

मौजूदा विधियों की सीमाएं

  • Syzkaller: सिस्टम कॉल टेम्पलेट का उपयोग करके वाक्य रचना सही करने को लागू करता है, लेकिन गहरी निर्भरताओं को कैप्चर नहीं कर सकता
  • स्थिर विश्लेषण विधियां: उच्च कम्प्यूटेशनल ओवरहेड, उच्च-थ्रूपुट फ़ज़िंग वातावरण में तैनाती कठिन
  • मौजूदा मशीन लर्निंग विधियां: फ़ज़िंग के दौरान सीमित डेटा उपलब्ध, SDRs को व्यापक रूप से कैप्चर नहीं कर सकते

अनुसंधान प्रेरणा

लेखकों ने कर्नल निष्पादन ट्रेस से सीधे SDRs सीखने का एक नया दृष्टिकोण प्रस्तावित किया है, जो ऐतिहासिक डेटा के व्यापक कवरेज और ऑनलाइन सीखने की अनुकूलनशीलता को जोड़ता है।

मुख्य योगदान

  1. ऐतिहासिक और वास्तविक समय कर्नल निष्पादन डेटा से SDRs सीखने की एक नई रणनीति प्रस्तावित की, जो व्यापक कवरेज और कर्नल संस्करण अनुकूलनशीलता दोनों को जोड़ती है
  2. Psyzkaller प्रोटोटाइप विकसित किया, जो Bigram-आधारित SDR सीखने और RandomWalk रणनीति को Syzkaller वर्कफ़्लो में एकीकृत करता है
  3. सबसे बड़े ऐतिहासिक Linux कर्नल निष्पादन डेटासेट (DongTing) के साथ Bigram मॉडल को पूर्व-प्रशिक्षित किया
  4. तीन प्रतिनिधि Linux कर्नल संस्करणों पर प्रभावशीलता को सत्यापित किया, शाखा कवरेज और कमजोरी पहचान में श्रेष्ठता प्रदर्शित की

विधि विवरण

कार्य परिभाषा

इनपुट: ऐतिहासिक कर्नल निष्पादन डेटासेट C और वास्तविक समय फ़ज़िंग परिणाम आउटपुट: अधिक प्रभावी सिस्टम कॉल अनुक्रम जनरेशन को निर्देशित करने के लिए बढ़ी हुई Choice Table उद्देश्य: सीड वैधता, विविधता और कमजोरी खोज क्षमता में सुधार

मॉडल आर्किटेक्चर

1. N-gram मॉडल चयन

SDRs सीखने के लिए Bigram मॉडल (N=2) को अपनाया गया है, निम्नलिखित विचारों के आधार पर:

  • डेटा दक्षता: DNN मॉडल की तुलना में, N-gram छोटे डेटासेट पर बेहतर प्रदर्शन करता है
  • कम्प्यूटेशनल दक्षता: Bigram मैट्रिक्स को अपडेट करने की कम्प्यूटेशनल लागत न्यूनतम है
  • व्याख्यात्मकता: SDRs को सिस्टम कॉल के बीच संक्रमण संभावनाओं के रूप में दर्शाया जाता है, समझने और जांचने में आसान

Bigram संभावना गणना:

P(wj|wi) = count(wiwj) / count(wi)

2. संबंध संभावना मैट्रिक्स (RPM)

RPM मैट्रिक्स का निर्माण किया जाता है, जहां RPM[i]j सिस्टम कॉल wi के तुरंत बाद wj को कॉल करने की संभावना को रिकॉर्ड करता है।

Algorithm 1: LearnSDR

इनपुट: C (सिस्टम कॉल अनुक्रम कॉर्पस), CallNum (कर्नल में सिस्टम कॉल की कुल संख्या)
आउटपुट: M (C से सीखा गया N-gram मॉडल)

1. मैट्रिक्स M और गणना सरणी Count को प्रारंभ करें
2. कॉर्पस C में प्रत्येक अनुक्रम sc पर पुनरावृत्ति करें:
   - लगातार दिखाई देने वाले सिस्टम कॉल जोड़ी की गणना करें
   - गणना सांख्यिकी को अपडेट करें
3. संक्रमण संभावना की गणना करें: M[i][j] = M[i][j] / Count[i]

3. डेटा स्रोत चयन

दो प्रकार के निष्पादन डेटा को जोड़ा जाता है:

  • ऐतिहासिक डेटा: DongTing डेटासेट (85GB, 18,966 सिस्टम कॉल अनुक्रम)
    • सामान्य अनुक्रम: 6,850 (LTP, Kselftests आदि परीक्षण सूट से)
    • असामान्य अनुक्रम: 12,116 (Syzbot द्वारा रिपोर्ट किए गए क्रैश से)
  • वास्तविक समय डेटा: फ़ज़िंग प्रक्रिया के दौरान एकत्र किए गए निष्पादन ट्रेस

4. बढ़ी हुई Choice Table एकीकरण

बढ़ी हुई Choice Table (ACT) का निर्माण:

ACT[i][j] = CTst[i][j] + CTdyn[i][j] + DTN[i][j] + CorpusN[i][j]

जहां:

  • CTst: स्थिर मान (डेवलपर ज्ञान)
  • CTdyn: गतिशील मान (कर्नल प्रतिक्रिया)
  • DTN: ऐतिहासिक डेटा प्रशिक्षित RPM
  • CorpusN: वास्तविक समय डेटा प्रशिक्षित RPM

5. RandomWalk रणनीति

सीड विविधता बढ़ाने के लिए द्विदिशीय विस्तार रणनीति की शुरुआत की गई:

Algorithm 2: GenRandomWalk

  • आंशिक अनुक्रम w1·w2...wk दिया गया
  • आगे विस्तार कर सकते हैं: w चुनें ताकि ACT[wk]w > 0
  • पीछे विस्तार कर सकते हैं: w चुनें ताकि ACT[w]w1 > 0
  • विस्तार दिशा को यादृच्छिक रूप से चुनें (संभावना प्रत्येक 0.5)

तकनीकी नवाचार बिंदु

  1. दोहरे स्रोत डेटा संलयन: पहली बार ऐतिहासिक बड़े पैमाने पर डेटा और वास्तविक समय सीखने को व्यवस्थित रूप से जोड़ा
  2. Shannon एंट्रॉपी वृद्धि: SDR सीखने के माध्यम से Choice Table की Shannon एंट्रॉपी में उल्लेखनीय वृद्धि (1.50 से 3.30-3.50 बिट्स तक)
  3. वजन संतुलन रणनीति: सामान्य और असामान्य ट्रेस के प्रभाव को संतुलित करने के लिए कॉन्फ़िगर करने योग्य वजन
  4. द्विदिशीय सीड जनरेशन: RandomWalk रणनीति पारंपरिक एकदिशीय विस्तार की सीमा को तोड़ती है

प्रयोगात्मक सेटअप

डेटासेट

  • DongTing डेटासेट: 85GB, Linux 4.13-5.17 संस्करणों को कवर करता है
  • परीक्षण कर्नल संस्करण: Linux 5.19, 6.1, 6.12
  • पूर्व-प्रसंस्करण: Syzkaller प्रारूप में परिवर्तित करने के लिए trace2syz उपकरण का उपयोग

मूल्यांकन मेट्रिक्स

  • शाखा कवरेज: कोड अन्वेषण की गहराई को मापता है
  • क्रैश संख्या: कमजोरी खोज क्षमता का मूल्यांकन करता है
  • Shannon एंट्रॉपी: Choice Table विविधता को मापता है
  • कमजोरी खोज: नई खोजी गई अज्ञात कमजोरियों की संख्या

तुलना विधियां

  • Syzkaller: आधारभूत विधि
  • Healer: अत्याधुनिक SDR सीखने वाला कर्नल फ़ज़र

कार्यान्वयन विवरण

  • प्रयोग अवधि: प्रत्येक 48 घंटे, 3 बार दोहराया गया, औसत लिया गया
  • वजन अनुपात: सामान्य/असामान्य ट्रेस के लिए 1:1, 1:2, 2:1 तीन वजन अनुपात परीक्षण किए गए
  • हार्डवेयर वातावरण: विभिन्न कर्नल संस्करणों के लिए समान सर्वर का उपयोग करके निष्पक्षता सुनिश्चित की गई

प्रयोगात्मक परिणाम

मुख्य परिणाम

शाखा कवरेज में सुधार

  • Syzkaller की तुलना में: 4.6%-7.0% सुधार
  • Healer की तुलना में: Healer के 0.4%-4.0% सुधार से काफी बेहतर

क्रैश पहचान क्षमता

  • क्रैश संख्या में वृद्धि: 110.4%-187.2% (1,206 बनाम 516)
  • PoC जनरेशन: 355 वैध PoC (Syzkaller केवल 70)

कमजोरी खोज

  • नई कमजोरियों की खोज: 8 अज्ञात कमजोरियां (Syzkaller केवल 1)
  • कमजोरी प्रकार: मुख्यतः डेडलॉक संबंधित कमजोरियां (6/8)

Ablation प्रयोग

वजन अनुपात प्रभाव (RQ1)

  • इष्टतम कॉन्फ़िगरेशन: 1:1 वजन अनुपात सभी कर्नल संस्करणों पर सर्वश्रेष्ठ प्रदर्शन करता है
  • संतुलन प्रभाव: समान वजन पथ अन्वेषण और कमजोरी-लक्षित दृष्टिकोण को संतुलित करता है

रणनीति संयोजन प्रभाव (RQ2)

  • सर्वश्रेष्ठ संयोजन: सभी रणनीतियां सक्षम करना (C+R+D) सर्वश्रेष्ठ प्रदर्शन प्राप्त करता है
  • व्यक्तिगत योगदान:
    • वास्तविक समय सीखना (C): उच्च शाखा कवरेज
    • ऐतिहासिक डेटा (D): अधिक क्रैश पहचान
    • RandomWalk (R): सीड विविधता में वृद्धि

केस विश्लेषण

त्रिपक्षीय डेडलॉक कमजोरी

खोजी गई एक विशिष्ट कमजोरी में तीन थ्रेड्स संसाधन लॉक के लिए प्रतिस्पर्धा करते हैं:

  • Thread A: blk_mq_freeze_queue → loop_reconfigure_limits
  • Thread B और C: जटिल लॉक निर्भरता संबंध बनाते हैं
  • ट्रिगर स्थिति: सटीक सिस्टम कॉल क्रम की आवश्यकता

इस प्रकार की जटिल कमजोरियों की खोज Psyzkaller की SDRs सीखने की प्रभावशीलता को प्रदर्शित करती है।

संबंधित कार्य

सिस्टम कॉल विनिर्देश जनरेशन

  • DIFUZE: डिवाइस इंटरफेस विवरण का अनुमान लगाने के लिए स्थिर विश्लेषण
  • SyzGen: गतिशील इंस्ट्रूमेंटेशन और स्थिर विश्लेषण का संयोजन
  • SyzDescribe: कर्नल मॉड्यूल प्राथमिकता का विश्लेषण

SDR निष्कर्षण

  • HFL: कवरेज प्रभाव का मूल्यांकन करने के लिए प्रतीकात्मक निष्पादन के साथ मिश्रित फ़ज़िंग
  • Healer: पुनरावृत्तिपूर्वक सिस्टम कॉल को हटाना और कवरेज प्रभाव का मूल्यांकन करना
  • MOCK: सीड म्यूटेशन को निर्देशित करने के लिए तंत्रिका भाषा मॉडल
  • ACTOR: साझा कर्नल ऑब्जेक्ट पर सिस्टम कॉल निर्भरताओं को सीखना

इस पेपर के लाभ

मौजूदा विधियों की तुलना में, यह पेपर प्रदान करता है:

  • बेहतर व्याख्यात्मकता (संक्रमण संभावना प्रतिनिधित्व)
  • उच्च कम्प्यूटेशनल दक्षता (हल्के मैट्रिक्स संचालन)
  • सूक्ष्म-दानेदार नियंत्रण (सामान्य/असामान्य निष्पादन का सापेक्ष प्रभाव)

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. SDR सीखने की प्रभावशीलता: ऐतिहासिक और वास्तविक समय डेटा से SDRs सीखना फ़ज़िंग प्रभाव में उल्लेखनीय सुधार करता है
  2. डेटा संलयन लाभ: ऐतिहासिक व्यापकता और वास्तविक समय अनुकूलनशीलता को जोड़ने वाली रणनीति इष्टतम है
  3. व्यावहारिकता सत्यापन: वास्तविक कर्नल संस्करणों पर महत्वपूर्ण प्रदर्शन सुधार प्रदर्शित किया

सीमाएं

  1. शब्दार्थ निर्भरता सीमा: Bigram द्वारा कैप्चर किए गए लगातार सिस्टम कॉल संबंध हमेशा वास्तविक शब्दार्थ निर्भरताओं के अनुरूप नहीं होते
  2. कर्नल संस्करण विकास: नए कर्नल संस्करणों पर ऐतिहासिक डेटा की प्रभावशीलता कम हो सकती है
  3. कम्प्यूटेशनल जटिलता: N बढ़ने के साथ, N-gram जटिलता घातीय रूप से बढ़ती है

भविष्य की दिशाएं

  1. बेहतर शब्दार्थ समझ: अधिक सटीक SDRs निकालने के लिए सिस्टम कॉल स्रोत कोड और दस्तावेज़ को जोड़ना
  2. अनुप्रयोग क्षेत्र का विस्तार: सीखे गए SDRs को सीड म्यूटेशन, शेड्यूलिंग आदि अन्य चरणों में लागू करना
  3. सुदृढ़ीकरण सीखने का एकीकरण: सुदृढ़ीकरण सीखने-आधारित फ़ज़िंग रणनीतियों के साथ संयोजन

गहन मूल्यांकन

लाभ

  1. विधि नवाचार शक्तिशाली: पहली बार ऐतिहासिक बड़े पैमाने पर डेटा और वास्तविक समय सीखने को व्यवस्थित रूप से जोड़ा
  2. प्रयोग पूर्ण व्यापक: तीन कर्नल संस्करण, कई कॉन्फ़िगरेशन, विस्तृत ablation प्रयोग
  3. व्यावहारिक मूल्य उच्च: 8 नई कमजोरियों की खोज, वास्तविक सुरक्षा मूल्य प्रदर्शित
  4. सैद्धांतिक आधार दृढ़: Shannon एंट्रॉपी का उपयोग करके सुधार को मापना

कमियां

  1. विधि सीमाएं: लगातार सिस्टम कॉल संबंधों पर निर्भर, लंबी दूरी की निर्भरताओं को छोड़ सकता है
  2. डेटा निर्भरता: DongTing डेटासेट की गुणवत्ता पर गंभीर निर्भरता
  3. स्केलेबिलिटी समस्या: मैट्रिक्स आकार सिस्टम कॉल संख्या के साथ द्विघात रूप से बढ़ता है

प्रभाव

  1. शैक्षणिक योगदान: कर्नल फ़ज़िंग क्षेत्र के लिए नई डेटा-संचालित विधि प्रदान करता है
  2. व्यावहारिक मूल्य: मौजूदा Syzkaller वर्कफ़्लो में सीधे एकीकृत किया जा सकता है
  3. पुनरुत्पादनशीलता: खुले स्रोत उपकरण और सार्वजनिक डेटासेट पर आधारित

लागू परिदृश्य

  • Linux कर्नल सुरक्षा परीक्षण
  • सिस्टम कॉल अनुक्रम जनरेशन अनुकूलन
  • कर्नल फ़ज़िंग उपकरण सुधार
  • ऑपरेटिंग सिस्टम सुरक्षा अनुसंधान

संदर्भ

पेपर में 44 संबंधित संदर्भों का हवाला दिया गया है, जिसमें शामिल हैं:

  • कर्नल फ़ज़िंग उपकरण (Syzkaller, Healer आदि)
  • मशीन लर्निंग विधियां (N-gram, Word2Vec, Transformers)
  • कर्नल निष्पादन डेटासेट (DongTing, ADFA-LD आदि)
  • सिस्टम कॉल निर्भरता निष्कर्षण विधियां

समग्र मूल्यांकन: यह एक उच्च गुणवत्ता का सिस्टम सुरक्षा अनुसंधान पेपर है जो कर्नल फ़ज़िंग में मुख्य समस्याओं को हल करने के लिए एक नवीन डेटा-संचालित विधि प्रस्तावित करता है। प्रयोग डिजाइन कठोर है, परिणाम विश्वास्पद हैं, और इसका महत्वपूर्ण शैक्षणिक मूल्य और व्यावहारिक महत्व है।