किसी भी भाषा में इस्तेमाल की जा सकने वाली C-Reduce तकनीक

 (bernsteinbear.com)
1 पॉइंट द्वारा GN⁺ 2024-11-28 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • C-Reduce C compiler bug को reproduce करने वाले कोड को छोटा करने का टूल है, लेकिन अगर deterministic condition, तेज reproduction, और edit किए जा सकने वाले source file हों, तो इसे दूसरी भाषाओं पर भी लागू किया जा सकता है
  • उदाहरण में RustPython में scrapscript चलाते समय आए bug को छोटा करने की प्रक्रिया दिखाई गई है, और interesting.sh किसी खास error message को ढूंढकर तय करता है कि bug reproduce हुआ या नहीं
  • सिर्फ creduce --not-c interesting.sh scrapscript.py चलाने से file size तेजी से कम हुआ, और शुरुआत में ही लगभग 50% reduction की प्रगति देखी जा सकती है
  • --not-c एक ऐसा option है जो C-विशेष reduction passes से बचाता है, इसलिए Python जैसे input पर यह अनावश्यक execution time घटाने में मदद करता है
  • अगर bug reproduce होने की शर्त को एक छोटी script में बदला जा सके, तो C के अलावा दूसरी भाषाओं के bug report भी C-Reduce से छोटे और संभालने में आसान बनाए जा सकते हैं

C-Reduce को C के अलावा दूसरे input पर इस्तेमाल करने की शर्तें

  • C-Reduce Regehr और उनके साथियों द्वारा बनाया गया C compiler bug reproduction code minimization टूल है
  • अगर 10,000 लाइन की कोई C file Clang bug ट्रिगर करती है, तो उस बड़ी file को जस का तस भेजने के बजाय इसे अपने-आप छोटा करने के लिए इस्तेमाल किया जा सकता है
  • यह C-विशेष टूल जैसा दिखता है, लेकिन नीचे दी गई शर्तें हों तो दूसरी भाषाओं के input पर भी इस्तेमाल किया जा सकता है

    • Deterministic condition

      • reproduction का अपेक्षाकृत तेज तरीका, जो reduction speed में मदद करे
      • एक या अधिक edit किए जा सकने वाले source file, जिन्हें C-Reduce छोटा कर सके
      • deterministic condition को loop wrapper का उपयोग करके probabilistic रूप में भी नकल किया जा सकता है

RustPython bug reproduction reduction का उदाहरण

  • RustPython में scrapscript चलाते समय bug आया, और उसकी report के लिए interesting.sh script लिखी गई
  • यह script RustPython binary के absolute path से scrapscript.py चलाने के बाद, standard error सहित output में नीचे दी गई string खोजती है
    • tried to push value onto stack but overflowed max_stackdepth
  • चलाने का command इस प्रकार है
    • creduce --not-c interesting.sh scrapscript.py
  • C-Reduce parallel में interestingness test चलाते हुए file size को तेजी से घटाता है
    • उदाहरण progress 0.5%, 9.2%, 18.1%, 47.5% आदि के रूप में दिखाई जाती है
    • कुछ ही सेकंड में file को लगभग 50% तक घटा देता है
    • लेख समाप्त करते समय यह 96.9% reduction तक पहुंच गया था
  • अगर --not-c का उपयोग न किया जाए, तो C-Reduce C-विशेष passes की बड़ी संख्या चलाता है
    • Python input में ये passes execution time को धीमा कर सकते हैं
    • लेकिन संभव है कि ये वास्तविक परिणाम को खास तौर पर न बदलें
  • संबंधित सामग्री बाद में Delta debugging पेज पर स्थानांतरित कर दी गई

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-11-28
Hacker News टिप्पणियाँ

  • घटाई गई फ़ाइल शेयर नहीं की गई थी, इसलिए मैंने खुद चलाकर देखा। RustPython बिल्ड किया, scrapscript.py लिया, फिर interesting.sh का path बदलकर nix run nixpkgs#creduce -- --not-c interesting.sh scrapscript.py से चलाया। आखिर में यह लगभग 96.4%, 7347 bytes पर आकर रुक गया, और परिणाम यहाँ है: https://gist.github.com/judofyr/47cba8a20cb2cd5798943ef975d0...

    • अचानक ख्याल आया: किसी और ने चिंता जताई थी कि reduction प्रक्रिया में program टूटकर local machine पर destructive operations कर सकता है। अगर reducer को source-to-source Nix derivation के रूप में चलाया जाए, तो क्या जोखिम भरे behavior को रोका जा सकता है और इसे remote builders पर भी आसानी से deploy किया जा सकता है?
    • संदर्भ के लिए, shrinkray करीब 10 मिनट चलाने पर इसे 162 bytes तक घटा देता है: https://gist.github.com/DRMacIver/ee025c90b4867125b382a13aaa...
      ज्यादा देर छोड़ने पर शायद थोड़ा और बेहतर हो, लेकिन यह लगभग रुका हुआ लग रहा था, इसलिए ऊबकर मैंने बंद कर दिया।

  • C-Reduce के लेखक John Regehr भी इस उपयोग के लिए Shrinkray आज़माने की सलाह देते हैं। उनका कहना है कि Shrinkray को format-independent तरीके से काम करने के लिए बनाया गया है, और जिन मामलों में C-Reduce अच्छा नहीं करता, वहाँ यह ठीक बैठने वाला tool है: https://mastodon.social/@regehr/113489759789563570

    • क्या यह repository Shrinkray की official repository है? https://github.com/DRMacIver/shrinkray
    • cvise का भी ज़िक्र करना चाहूँगा: https://github.com/marxin/cvise
      यह एक Python alternative है, जो non-C languages पर भी काफ़ी अच्छा काम करता है।

  • John Regehr और अन्य लेखकों का 2012 का एक paper है, जो बताता है कि यह कैसे काम करता है: https://fsl.cs.illinois.edu/publications/regehr-chen-cuoq-ei...

    • यह paper पढ़ने के बाद भी मुझे अब तक समझ नहीं आ रहा कि यह संभव कैसे है। ऐसा लगता है कि यह किसी भी programming language के लिए tokenization, line merging, token removal वगैरह समझता है; सोच रहा हूँ कि क्या इस algorithm को अलग से समझाने वाला कोई और paper है।
    • यह paper पूरे C-Reduce के बारे में नहीं है, बल्कि project में जोड़े गए 3 domain-specific test case reducers के बारे में है।
      मेरी याद में, C-Reduce की ज़्यादातर domain-agnostic reduction simple brute force जैसी ही है।

  • C-Reduce के बारे में अभी-अभी पहली बार पता चला और मैं पहले ही इसमें खिंच गया हूँ। वैसा ही अनुभव है जैसा पहली बार git bisect खोजने पर हुआ था।
    इसे दिमाग के किसी कोने में रख लेना चाहिए, ताकि कभी सही परिस्थिति मिले तो इस्तेमाल कर सकूँ।

    • कॉलेज के बाद अपनी पहली नौकरी में जब मैं C/C++ compiler team में था, तब हम ऐसा काम manually करते थे। यह देखकर काफ़ी हैरानी होती है कि वही काम automate किया जा सकता है।
    • 6502 processor के लिए C compiler cc65 में मुझे एक ऐसा issue मिला जो compiler bug जैसा लग रहा था। targets C64, NES, Apple 1 जैसे हैं।
      सोच रहा हूँ इसे setup करके देखूँ। VICE host operating system की file में “output” करने की सुविधा support करता है, तो emulator में tests चलाए जा सकते हैं।
    • random test input generator के साथ इस्तेमाल करें तो शानदार है।

  • Delta debugging कोई नया concept नहीं है: https://en.wikipedia.org/wiki/Delta_debugging
    मेरी बनाई delta debugging implementation delta 19 साल से ज्यादा पुरानी है: https://github.com/dsw/delta
    जिस दौर में Microsoft open source को “cancer” कहता था, उस समय Microsoft Research ने मेरे office तक किसी को भेजकर इसे public करने का अनुरोध किया था, इसलिए मैंने इसे open source के रूप में release किया। Latner के LLVM introduction में भी “standard delta debugging tool” का ज़िक्र है, इसलिए यह काफ़ी जाना-पहचाना tool है: https://aosabook.org/en/v1/llvm.html

    • C-Reduce simple delta debugging से थोड़ा ज्यादा sophisticated है। 2012 के paper “Test-Case Reduction for C Compiler Bugs” के abstract के मुताबिक, C-Reduce के results दूसरे reducers या उस समय compiler developers द्वारा सबसे ज़्यादा इस्तेमाल किए जाने वाले reducers की तुलना में औसतन 25 गुना से भी ज्यादा छोटे थे।
      यानी प्रभावी program reduction के लिए simple delta debugging से आगे की चीज़ों की जरूरत होती है। बेशक C-Reduce भी अब 12 साल पुराना tool है।
      साथ ही, linked LLVM tool BugPoint सिर्फ LLVM IR के लिए है, जबकि C-Reduce ज्यादा general दिखता है। automatic test case minimization tools और techniques अभी भी ज़्यादातर developers के लिए अपरिचित हैं, इसलिए इस field में पुरानी और well-known idea होने के बावजूद यह लेख उपयोगी हो सकता है।

  • पहले/बाद के examples वाला एक लेख मिला: https://pramodkumbhar.com/2024/01/c-reduce-systematically-ta...
    फिर भी मुझे अब तक ठीक से समझ नहीं आया कि हर iteration में क्या हटाना है यह इसे कैसे पता चलता है। tokenization कुछ हद तक तो होगा, लेकिन वह कई programming languages में कैसे काम करता है, यह नहीं समझ पा रहा।

  • creduce शानदार है।
    एक obscure LLVM target backend develop करते समय मैंने CSmith से random test programs घंटों तक generate करने वाली test script इस्तेमाल की थी। crash होने पर यह automatically C-Reduce चलाकर जांचने के लिए file छोड़ देती थी, और इससे सचमुच बहुत मदद मिली।

  • SQL में भी अच्छी तरह काम करता है। इसे काम में इस्तेमाल कर रहा हूँ, और https://github.com/sqlancer/sqlancer?tab=readme-ov-file#redu... के जरिए इसके बारे में पता चला

  • अगर यह न बताया जाए कि यह C के अलावा दूसरी भाषाओं में भी क्यों काम करता है, तो इस दावे पर यकीन करना मुश्किल है। मुझे नहीं लगता कि यह झूठ है, लेकिन LLM के बिना ऐसा होना हैरान करता है

    • संक्षेप में कहें तो कुछ reduction passes C-family languages पर काफी हद तक generalize हो जाते हैं, और ये passes सबसे प्रभावी किस्मों में आते हैं
      उदाहरण के लिए, input को C-style में tokenize करके लंबाई 1~13 के आसपास के chunks को randomly हटाने का तरीका, C जैसी अधिकांश languages में मिलते-जुलते tokenization rules होने के कारण गैर-जरूरी qualifiers या attributes हटाने में अच्छा काम करता है। balanced parentheses (), {}, [] units हटाने वाला pass भी लगभग हर language में उपयोगी है। comments और whitespace हटाना भी प्रभावी है, क्योंकि कई languages C जैसे /* */, // style इस्तेमाल करती हैं
      असल में पूरी तरह C/C++-specific passes बहुत ज्यादा नहीं हैं। मेरे अनुभव में creduce की बड़ी कमजोरियों में से एक यह है कि templates हटाने वाला reduction step—यानी ऐसा काम जो अपेक्षाकृत automate करना आसान लगता है—यह सचमुच ठीक से नहीं कर पाता
    • asmeurer द्वारा link किए गए PLDI paper को सरसरी तौर पर पढ़ने की सलाह दूँगा। उसमें अच्छा summary है
      कुछ transformations Clang frontend इस्तेमाल करने वाले काफी C-specific हैं, और कुछ काफी general हैं, इसलिए Algol-family languages में आम तौर पर काम करने की संभावना है। यह modular tool है, इसलिए चाहें तो दूसरी language को समझने वाले transformations भी जोड़ सकते हैं
    • यह पुराने ढंग की computer science के ज्यादा करीब है। उम्मीद है HN ने अभी से ऐसी traditional computer science को भुला नहीं दिया होगा
      यहाँ बात algorithms जैसी चीजों की है, किसी डरावनी machine learning की नहीं। इसमें Prolog को AI में इस्तेमाल करने जैसी चीजें भी शामिल हैं, लेकिन इसमें एक छोटी-सी कमी है कि AI बनाने के मकसद से यह ठीक से काम नहीं करता
    • अगर इसके काम करने का तरीका समझ में न आए, तो पता नहीं कि इसे इस तरह इस्तेमाल करना safe है या नहीं। क्या creduce बदले हुए input script को चलाकर मेरी files delete कर सकता है या मेरा lunch खा सकता है?
    • paper देखे बिना अंदाजा लगाऊँ तो यह input size घटाने की दिशा में mutations apply करने वाले fuzzer जैसा होगा

  • dustmite से तुलना करें तो कैसा है? https://dlang.org/blog/2020/04/13/dustmite-the-general-purpo...