टेस्ट केस reducer एक कम आंके गए debugging tool हैं

• बड़े input में समस्या पैदा करने वाले हिस्से को खोजते समय test case reducer input को अपने-आप छोटा करके debugging आसान बनाता है
• reducer program, input और interestingness test लेकर बार-बार यह जांचता है कि छोटा candidate input वही समस्या reproduce करता है या नहीं
• साधारण line-deletion reducer भी /usr/share/dict/words में सिर्फ एक लंबा शब्द छोड़ देता है, और C उदाहरण में 10 सेकंड से कम समय में 78 lines को 54 lines तक घटा देता है
• interestingness test को over-reduction, धीमे execution, अनंत execution, और parallel execution environment के कारण सटीक और तेज़ लिखना पड़ता है
• input length के अलावा error frequency या execution trace length जैसे metrics को interestingness test में शामिल करने से non-deterministic bugs और बड़े trace logs की debugging में मदद मिलती है

---

टेस्ट केस संक्षेपण

• जब बड़े input पर program crash हो और input का कौन-सा हिस्सा कारण है यह पता न हो, तब input छोटा करने से समस्या का कारण समझना आसान हो जाता है
• manual reduction में text editor में input के कुछ हिस्से हटाकर यह देखा जाता है कि वही crash बना रहता है या नहीं
• manual reduction में इंसान कई deletion opportunities आसानी से चूक सकता है, और deletion के बाद program सामान्य रूप से समाप्त हो सकता है या कोई दूसरी सामान्य error दे सकता है
• अगर दूर-दूर मौजूद A और B हिस्सों को साथ हटाने पर ही असर पड़ता हो, तो search space बहुत बढ़ जाता है

टेस्ट केस reducer की बुनियादी संरचना

• test case reducer एक ऐसा tool है जो program, input, और interestingness test लेकर input को छोटा करता है
• interestingness test तब 0 लौटाता है जब घटाया गया input रुचिकर error को reproduce करे, और अन्यथा non-zero value लौटाता है
• test case reducer में 95~99% reduction आम है, और इससे debugging बहुत आसान हो सकती है
• reducer को यह semantic समझने की ज़रूरत नहीं होती कि input के कौन-से हिस्से हटाने चाहिए

• साधारण reducer उदाहरण

  • उदाहरण program file से lines पढ़ता है और यदि कोई line 25 से लंबी हो तो Word too long प्रिंट करता है
  • interestingness test program output में Word too long होने पर 0, और न होने पर 1 लौटाता है
  • साधारण Python reducer input को line unit में पढ़ता है, एक line हटाए हुए candidate input को temporary file में लिखता है, फिर interestingness test चलाता है
  • अगर candidate input interesting हो, तो current input को उसी candidate से बदल दिया जाता है, और जब आगे reduction संभव न हो तो result को stdout पर output किया जाता है
  • /usr/share/dict/words पर चलाने से अंत में सिर्फ antidisestablishmentarianism बचता है

अधिक शक्तिशाली reducers और Shrink Ray

• 78-line C program उदाहरण में FAST=0 और FAST=1 settings पर अलग output आने की समस्या है
• interestingness test दोनों settings से compile करने के बाद तभी pass होता है जब FAST=0 output 0d754a56 हो और FAST=1 output उससे अलग हो
• साधारण reducer 10 सेकंड से कम में 78-line C input को 54 lines तक घटा देता है, यानी lines के हिसाब से लगभग 30% reduction
• हर interesting candidate मिलने पर शुरुआत की line से फिर deletion शुरू कराने के लिए i=0 जोड़ने से execution time लगभग 10 गुना बढ़ जाता है, और 3 lines और घटती हैं
• Shrink Ray कई reduction rules और parallel execution देता है, और --no-clang-delta लगाने पर C के बारे में विशेष ज्ञान का उपयोग नहीं करता
• Shrink Ray ने लगभग 15 मिनट बाद bytes के हिसाब से input को 60% से अधिक घटाया, और दूसरे मामलों में लगभग 20 मिनट बाद 90% reduction ढूँढकर उसे 99% तक और घटाया
• Shrink Ray standard comment syntax को जानता है और शुरुआत में उसे हटाने की कोशिश करता है, साथ ही integers को छोटे values में बदलने की कोशिश भी करता है

interestingness test लिखने की कठिनाई

• test case reducer interestingness test का शाब्दिक पालन करता है, इसलिए अगर test गलती से pass हो जाए तो इच्छित बिंदु से भी अधिक reduction होने वाली over-reduction हो सकती है
• Shrink Ray साफ़ तौर पर यह जांचता है कि interestingness test खाली input को स्वीकार तो नहीं कर रहा, और ऐसी स्थिति काफ़ी बार हो सकती है
• C उदाहरण में अगर सिर्फ यह देखा जाए कि दोनों outputs अलग हैं, तो महत्वहीन या भ्रम पैदा करने वाले output differences भी interesting input माने जा सकते हैं
• test "$slow_out" = "0d754a56" जांच यह सुनिश्चित करती है कि slow version वास्तव में अपेक्षित behavior कर रहा है, जिससे over-reduction की संभावना घटती है

• गति और timeout

  • interestingness test तेज़ हो तो reducer उसे प्रति सेकंड सैकड़ों बार चला सकता है
  • मध्यम आकार के उदाहरण भी reduction की लाखों कोशिशों तक पहुँच सकते हैं, इसलिए interestingness test optimization का कुल समय पर बड़ा असर पड़ता है
  • automatic core dump generation बंद करके interestingness test को लगभग 3 गुना तेज़ करने का एक उदाहरण है
  • reducer i-=1 जैसी line हटाकर terminate होने वाले program को infinite-loop program में बदल सकता है
  • अगर program 0.1 सेकंड में चलता है लेकिन timeout 60 सेकंड रखा जाए, तो पूरी reduction बहुत धीमी हो जाती है
  • तेज़ programs के लिए timeout को 1~2 सेकंड तक ऊपर round करना, और अन्य मामलों में शुरुआती execution time के लगभग 1.5~2 गुना पर रखना एक प्रचलित तरीका है

• parallel execution

  • Shrink Ray जैसे reducers interestingness test को parallel में चलाते हैं
  • Shrink Ray हर interestingness test को temporary directory में चलाता है और उस directory को अपने-आप साफ़ कर देता है
  • सिर्फ temporary directory हमेशा काफ़ी नहीं होती, और ज़रूरी उपाय case-by-case बदलते हैं

interestingness test से determinism लाना

• उदाहरण snippet len([])==0 की वजह से divide-by-zero error बनाता है, लेकिन random.random() < 0.33 condition के कारण समस्या केवल लगभग एक-तिहाई runs में होती है
• non-deterministic bugs में error कभी random तरीके से दिखती है, कभी गायब हो जाती है, जिससे hypothesis verification अधिक कठिन और लंबा हो जाता है
• reducer अगर random.random() call हटा दे या condition expression बदल दे, तो non-deterministic error deterministic error में बदल सकती है
• वास्तविक non-determinism में input के कई हिस्से प्रतिकूल तरीके से interact करते हैं, इसलिए उसे हटाना कठिन हो सकता है
• test case reducer input length को “बेहतर” के proxy metric की तरह उपयोग करने वाले hill-climbing algorithm की तरह काम करता है
• hill-climbing approach local optimum में फँस सकती है, और छोटा input हमेशा bug hunting के लिए बेहतर नहीं होता

• repeated execution तरीका

  • non-deterministic bug से निपटते समय ऐसा interestingness test इस्तेमाल किया जाता है जो input को कई बार चलाता है, और यदि रुचि वाली error कम-से-कम एक बार भी हो जाए तो input को स्वीकार करता है
  • यह तरीका error occurrence frequency बढ़ाने में मदद कर सकता है
  • कम-से-कम एक बार होने पर pass करने वाला test non-deterministic inputs को भी स्वीकार करता है, इसलिए reduction के दौरान non-determinism उल्टा बढ़ भी सकता है
  • अधिक सख़्त तरीका यह है कि test तभी input स्वीकार करे जब n बार के सभी repeats में error हो
  • सख़्त test में शुरुआती input के pass होने की संभावना कम होती है, इसलिए Shrink Ray शुरू करना मुश्किल हो सकता है, और उदाहरण की 3-repeat condition में शुरुआती pass probability 3.6% है
  • एक व्यावहारिक workaround यह है कि पहले “n runs में कम-से-कम 1 error” test से शुरू किया जाए, और जब ऐसा reduced input मिल जाए जिसमें error अधिक बार हो, तब “n लगातार errors” test पर switch किया जाए

global counter और अन्य target metrics

• manual intervention शक्तिशाली है, लेकिन इसके लिए Shrink Ray को देखते रहना पड़ता है और intervention का सही समय चूकना आसान है
• reducer को input length के बजाय किसी और property से guide करना हो, तो उसी property को एक single interestingness test के भीतर enforce किया जा सकता है
• yk debugging में input length से ज़्यादा execution trace length, यानी program द्वारा execute की गई instructions की संख्या के करीब का मान, अधिक महत्वपूर्ण हो सकता है
• YKD_LOG="$t:jit-asm" output text trace IR और machine-code instructions को file में लिखता है, और छोटा jit-asm output debugging को आसान बनाता है
• wc -l log file की line count गिनकर trace length के निकट एक proxy metric की तरह इस्तेमाल होता है
• interestingness test वर्तमान trace line count यदि पिछले best से बड़ा हो तो input को uninteresting मानता है, और best value /tmp/global_best में store की जाती है
• यह तरीका parallel reduction में safe नहीं है और reducer के invocation pattern के बारे में assumptions रखता है, लेकिन throwaway script के लिए इसे स्वीकार्य अपूर्णता माना जाता है
• yk segfault case में सामान्य reduction ने 40K-line trace छोड़ा, लेकिन इस technique ने बड़े reduced input के बजाय 10.1K-line trace बनाया, जिससे 30 मिनट के भीतर root bug समझ आ गया

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

• test case reducers सिर्फ compiler writers के लिए उपयोगी tool नहीं हैं, इन्हें non-compiler समस्याओं में भी इस्तेमाल किया जा सकता है
• input length घटाने के मूल उद्देश्य से आगे बढ़कर error frequency, wall-clock time, non-determinism level, और trace length जैसी properties को interestingness test से guide किया जा सकता है
• interestingness test की accuracy, execution speed, timeout, और parallel-execution safety reducer के वास्तविक प्रभाव को तय करती है
• reducer input और program के अर्थ को लगभग समझे बिना भी समस्या को छोटे रूप में बनाए रखकर debugging productivity बढ़ा सकता है

[GN⁺]

Lobste.rs की रायें

• सच में जिज्ञासा है, क्या कोई automatic test case minimization की value को नहीं मानता? “underrated” शब्द ऐसा सुनाई देता है जैसे कुछ लोग हमेशा test case minimization नहीं चाहते
  भले ही bug को तुरंत pinpoint किया जा सके, regression test के लिए क्या minimized case की ज़रूरत नहीं होती?

  • आम तौर पर developers ने शायद इसे एक technique के रूप में सोचा तक नहीं होगा
  • लेख की पहली पंक्ति है “Test-case reducers are less well known than they should be, [...]”, और कई सालों से लोगों को fuzzing और property-based testing इस्तेमाल करने की सलाह देने वाले के नाते, मेरा अनुभव भी यही रहा है
    दोनों में अक्सर failing cases को minimize करना या “shrinking” जैसी कोई प्रक्रिया शामिल होती है, और इसी वजह से वे कहीं ज़्यादा practical बनते हैं
  • fuzzers में इसका मोटा-मोटा अंदाज़ा होता है। fuzzer failing case ढूँढने के बाद उसे अपने-आप छोटा कर देता है, और वह हिस्सा बहुत अच्छी तरह काम करता है
    लेकिन fuzzing कुल मिलाकर, खासकर AmericanFuzzyLop और AFL++ के साथ मेरे अनुभव में, setup इतना पीड़ादायक रहा है कि मैं आम तौर पर उससे बचता हूँ
    मुझे मिलने वाले ज़्यादातर bugs भी “इस input file को डालो तो गड़बड़ होती है” वाले नहीं होते, बल्कि “कहीं किसी user के लिए कुछ गलत हो जाता है” के ज़्यादा करीब होते हैं। कभी-कभी इसे “कुछ खास conditions में कुछ steps की sequence से गड़बड़ होती है” तक घटाया जा सकता है, लेकिन 1) “user एक-एक करके कुछ करता है” जैसी चीज़ पर automatic test case reducer कैसे लागू करूँ, यह मुझे नहीं पता, और 2) एक बार local में reproduce करने का तरीका मिल जाए तो debugging का 99% काम पूरा मानो
    शायद लेखक मेरे इस रवैये को “underrating” मानेगा
  • शायद test case minimization क्या होता है, यह जानने वाले लोग ही बहुत कम हैं

• यह लेख और इसके examples कहते तो हैं कि reducers का इस्तेमाल non-compiler स्थितियों में भी ज़्यादा होना चाहिए, लेकिन नज़रिया काफ़ी हद तक compiler writer की तरफ झुका हुआ है
  जैसा ~silentbicycle ने लिखा, ज़्यादातर test case reduction fuzzers या property-based testing के संदर्भ में होती है, जहाँ reduction capability किसी बड़े framework के भीतर built-in होती है। compiler उन असामान्य क्षेत्रों में से एक है जहाँ standalone test case reducer उपयोगी होता है। इसके अलावा ऐसे और कौन से मामले हैं जहाँ standalone reducer मदद करे, यह मुझे साफ़ नहीं है
  determinism वाला हिस्सा भी दिलचस्प है। example की शुरुआत bug trigger करने वाली input file, यानी script, से आती है, इसलिए determinism पैदा होता है; यह bug वाले interpreter की अपनी विशेषता से deterministic नहीं है। यह साफ़ नहीं है कि लेख का मतलब यह है कि “interestingness” technique bug वाले program के खुद non-deterministic होने वाली non-compiler स्थितियों में भी काम करती है
  test problems को fuzzing और test case reduction के अनुकूल बनाने के लिए, मैं numbered imperative commands का एक set बनाने की सलाह दूँगा। हर command में test failure पकड़ने के लिए हल्के consistency checks हों, ताकि वे मामले भी पकड़े जाएँ जहाँ तुरंत crash नहीं होता। भारी consistency checks को अलग command में रखना बेहतर है ताकि test की speed ज़्यादा slow न हो। साधारण random testing में test harness बस random commands चुनता रहे जब तक कुछ टूट न जाए, और बाद में fuzzer harness में बदलते समय fuzzy input byte stream से commands चुनवा दो। फिर deterministic regression tests और test case reduction जैसी अच्छी चीज़ें अपने-आप मिल जाती हैं
  मैंने libfuzzer से explicitly test cases reduce करवाने की कोशिश की, लेकिन ख़ास सफलता नहीं मिली; शायद इसलिए कि libfuzzer inputs generate करते समय ही उन्हें पहले से छोटा कर रहा था। इसलिए मुझे यह प्रेरणा नहीं मिली कि general-purpose fuzzer को test case reduction में मदद देने वाले interestingness checks और आज़माऊँ। जानना चाहूँगा कि क्या दूसरों को इसमें सफलता मिली है

  • पूरी तरह सहमत। मैं यह तरीका अक्सर इस्तेमाल करता हूँ। stateful interface की एक symbolic representation बनाओ, फिर आम तौर पर switch-case या match आधारित एक simple interpreter बनाओ, operations की list random generate करके चलाओ, और फिर उन inputs को shrink करो जो pre/post condition violation या internal corruption पकड़ने वाले assert को trigger करते हैं
    चाहे इसे property-based testing कहो, fuzzing कहो, या lightweight model checking, गहरे bugs ढूँढने में यह चौंकाने वाली हद तक असरदार हो सकता है। मैंने बहुत से stateful interfaces देखे हैं जहाँ हर operation अलग-अलग सही होता है, लेकिन उनकी assumptions एक-दूसरे से थोड़ा mismatch करती हैं, और जब ये operations अनपेक्षित तरीक़े से combine होते हैं तो internal corruption तक पहुँच जाते हैं
    operations की list को किसी in-memory hash table या list-based simple implementation के साथ-साथ चलाकर यह जाँचना भी उपयोगी है कि results match करते हैं या नहीं। अगर फ़र्क निकलता है, तो वह अक्सर bug होता है या ऐसा edge case जिसे बेहतर documentation चाहिए
  • मैं कभी-कभी transport optimization पर काम करता हूँ, और अक्सर ऐसे काफ़ी complex scenarios मिलते हैं जहाँ invariants टूट जाते हैं। वहाँ test case reducer होना सच में बहुत अच्छा होता, लेकिन पहले मुझे manual reduction से ही संतोष करना पड़ता था[0]
    दुर्भाग्य से data files इतनी complex हैं कि shrinkray के लिए उन्हें संभालना मुश्किल होगा। यह कई अलग-अलग “files” के tabular data को पढ़ता है, और long-range dependencies भी हैं, इसलिए reduction method के बारे में domain knowledge सीधे encode करनी पड़ेगी
    AI की प्रगति की रफ़्तार देखकर लगता है कि अगली बार ऐसा scenario आया तो मैं एक custom reducer लिखूँगा
    [0] अगर थोड़ी धुंधली ontology की बात करें, तो optimization problem cost को minimize करने वाली search problem है, और वह असल में compiler जैसी ही चीज़ है, इसलिए यह पूरी तरह सही example नहीं है

• इसे pytest में लिखे tests पर कैसे लागू करूँ, यह समझने के लिए मैंने तीन बार पढ़ा
  मैं test suite की complexity कम करना चाहता हूँ, इसलिए काम न होने पर इसे चौथी बार फिर पढ़ने का सोच रहा हूँ

  • अगर आप Python इस्तेमाल करते हैं, तो पहला कदम Hypothesis अपनाना है, जिसमें test case shrinking built-in है

• पिछले साल CI में test execution order की समस्या देखते हुए, मैंने test list को reduce करने में मदद करने वाला एक tool बनाया था
  मूल रूप से यह lines को आधा-आधा काटकर चलाने का तरीका था
  script खुद काफ़ी buggy है, लेकिन 5000 tests की list का सिमटकर लगभग 4 tests की list बन जाना, जो मेरे concurrency bug को trigger करती थी, कमाल का था
  सच में सोचता हूँ कि क्या मेरे मामले में Shrink Ray बस सीधे काम कर जाता। “tests के आधार पर lines के set को reduce करना” ईमानदारी से standard command-line tool bundle का हिस्सा होना चाहिए

• इस विषय से जुड़ा हुआ, property-based testing भी test counterexamples बनाने के लिए generated inputs की state space को “shrink” करने जैसा काफ़ी मिलता-जुलता तरीका अपनाती है
  property-based testing का फ़ायदा यह है कि आप search space को guide और structure कर सकते हैं। आप inputs को transitions के एक set में बदल सकते हैं जो program को model करने वाली state machine को drive करे
  यह देखकर हमेशा हैरानी होती है कि databases और distributed systems जैसे उन क्षेत्रों में भी, जहाँ यह technique ख़ास तौर पर अच्छी तरह फिट बैठती है, इसका अब भी बहुत कम इस्तेमाल होता है। अभी पिछले हफ़्ते ही मैंने $WORK में कुछ घंटों से भी कम समय में ऐसा test बनाया, और जल्दी पता चल गया कि हमारा system converge नहीं करता। test ने एक साफ़ trace भी निकाली, जिसे teammates को दिखाते ही वे तुरंत समझ गए
  मेरे हिसाब से, complex systems को debug करते समय return on investment के लिहाज़ से यह सबसे असरदार testing technique है