CoBRA

Coगुणांक-Bआधारित Rपुनर्निर्माण Aअंकगणित — एक मिश्रित बूलियन-अंकगणित अभिव्यक्ति सरलीकरणकर्ता।

CoBRA उन अभिव्यक्तियों को डीऑब्स्केट करता है जो अंकगणितीय (+, -, *) को बिटवाइज़ (&, |, ^, ~) और शिफ्ट (<<, >>) ऑपरेटरों के साथ मिलाती हैं — यह एक ऐसी तकनीक है जिसका उपयोग सॉफ्टवेयर ऑब्स्केशन में आमतौर पर किया जाता है।

$ cobra-cli --mba "(x&y)+(x|y)"
x + y

$ cobra-cli --mba "((a^b)|(a^c)) + 65469 * ~((a&(b&c))) + 65470 * (a&(b&c))" --bitwidth 16
67 + (a | b | c)

$ cobra-cli --mba "((a^b)&c) | ((a&b)^c)"
c ^ a & b

$ cobra-cli --mba "(x&0xFF)+(x&0xFF00)" --bitwidth 16
x

$ cobra-cli --mba "(x ^ 0x10) + 2 * (x & 0x10)"
16 + x

$ cobra-cli --mba "x << 3"
8 * x

और उदाहरण

$ cobra-cli --mba "~x"
~x

$ cobra-cli --mba "(x^y)*(x&y) + 3*(x|y)"
(x ^ y) * (x & y) + 3 * (x | y)

$ cobra-cli --mba '-357*(x&~y)*(x&y)+102*(x&~y)*(x&~y)+374*(x&~y)*~(x^y)
  -306*(x&~y)*~(x|y)-17*(x&~y)*~(x|~y)-105*~(x|~y)*(x&y)+30*~(x|~y)*(x&~y)
  +110*~(x|~y)*~(x^y)-90*~(x|~y)*~(x|y)-5*~(x|~y)*~(x|~y)+34*(x&~y)*~x
  -85*(x&~y)*~y+10*~(x|~y)*~x-25*~(x|~y)*~y'
22 * (x & y) + -17 * x + -5 * y

यह कैसे काम करता है

CoBRA अभिव्यक्तियों को सरल करने के लिए एक कार्यसूची-आधारित ऑर्केस्ट्रेटर का उपयोग करता है। प्रत्येक इनपुट एक कार्य आइटम के रूप में कार्यसूची में प्रवेश करता है जिसे एक राज्य प्रकार के साथ टैग किया जाता है। एक शेड्यूलर आइटम की स्थिति, पूर्वापेक्षा निर्भरताओं और एक प्रयास कैश के आधार पर अगला पास चुनता है जो अनावश्यक कार्य को रोकता है।

36 अलग-अलग पास परिवारों में व्यवस्थित हैं: AST प्रसंस्करण, हस्ताक्षर-आधारित तकनीकें, अर्धरेखीय तकनीकें, अपघटन, और लिफ्टिंग। कुछ पास स्थानीय विकल्प या चाइल्ड समाधान उत्पन्न करते हैं जो प्रतियोगिता समूहों द्वारा हल किए जाते हैं; उन समूहों के बाहर, कार्यसूची पहले पूरी तरह से सत्यापित शीर्ष-स्तरीय उम्मीदवार लौटाती है। सभी परिणाम यादृच्छिक इनपुट (डिफ़ॉल्ट) या Z3 समतुल्यता प्रमाण (--verify) के माध्यम से स्पॉट-चेक करके सत्यापित किए जाते हैं।

Input Expression
       |
  [Worklist Scheduler]
       |
  Work items flow through state kinds:
       |
  kFoldedAst ──> AST processing passes
       |         (classify, lower, rewrite)
       |
       +──> kSignatureState ──> Signature techniques
       |    (pattern match, CoB, ANF, polynomial recovery)
       |
       +──> kSemilinearNormalizedIr ──> Semilinear techniques
       |    (normalize, recover structure, refine, reconstruct)
       |
       +──> kCoreCandidate / kRemainderState ──> Decomposition
       |    (extract core, classify residual, solve)
       |
       +──> kLiftedSkeleton ──> Lifting
       |    (virtual variable substitution, outer solve)
       |
       +──> kCandidateExpr ──> Verification
            (spot-check or Z3 proof)
       |
  Simplified Expression

हस्ताक्षर-आधारित तकनीकें सभी बूलियन इनपुट पर अभिव्यक्ति का मूल्यांकन करके एक हस्ताक्षर वेक्टर प्राप्त करती हैं। एक CoB बटरफ्लाई ट्रांसफॉर्म AND-उत्पाद आधार गुणांक पुनर्प्राप्त करता है। पैटर्न मिलान, ANF और बहुपद पुनर्प्राप्ति विभिन्न जटिलता स्तरों को संभालती है।

अर्धरेखीय तकनीकें स्थिर मास्क वाली अभिव्यक्तियों (जैसे x & 0xFF) को संभालती हैं। अभिव्यक्ति को भारित बिटवाइज़ परमाणुओं में विघटित किया जाता है, फिर संरचना पुनर्प्राप्ति और पद शोधन मध्यवर्ती प्रतिनिधित्व को सरल करते हैं, और बिट-विभाजित OR-असेंबली अंतिम परिणाम का पुनर्निर्माण करती है।

अपघटन बिटवाइज़ उप-अभिव्यक्तियों के गुणनफल वाली मिश्रित अभिव्यक्तियों को लक्षित करता है। एक बहुपद कोर निकाला जाता है, फिर अवशेषों को वर्गीकृत और हल किया जाता है (बहुपद, बूलियन-नल/घोस्ट, या टेम्पलेट फॉलबैक)।

लिफ्टिंग जटिल उप-अभिव्यक्तियों को आभासी चरों से बदलता है, सरलीकृत बाहरी कंकाल को हल करता है, फिर वापस प्रतिस्थापित करता है।

विशेषताएँ

रैखिक MBA सरलीकरण — हस्ताक्षर वेक्टर और CoB ट्रांसफॉर्म के माध्यम से बिटवाइज़ परमाणुओं के भारित योग
स्केल किया गया पैटर्न मिलान — 4-5 चर बूलियन अभिव्यक्तियों के लिए शैनन अपघटन के साथ k * f(vars) + c
अर्धरेखीय समर्थन — स्थिर-मास्क वाले परमाणु जिनमें XOR/OR/NOT-AND स्थिर निम्नीकरण, संरचना पुनर्प्राप्ति, पद शोधन, बिट-विभाजित पुनर्निर्माण शामिल हैं
बहुपद पुनर्प्राप्ति — गुणांक विभाजन और परिमित अंतरों के माध्यम से बहुरैखिक पद और एकल घात
मिश्रित गुणनफल प्रबंधन — कोर निष्कर्षण, अवशेष समाधान और घोस्ट अवशेष वर्गीकरण के साथ अपघटन इंजन
उप-अभिव्यक्ति लिफ्टिंग — समस्या आयाम को कम करने के लिए जटिल उप-वृक्षों को आभासी चरों से बदलें
कार्यसूची ऑर्केस्ट्रेटर — डीडुप्लिकेशन और बाधित खोज के साथ DAG-जागरूक पास शेड्यूलिंग
प्रतियोगिता समूह — स्थानीय वैकल्पिक शाखाएँ और चाइल्ड समाधान निरंतरताओं के साथ लागत-आधारित विजेता चयन का उपयोग करते हैं
स्थिर शिफ्ट — << को गुणन में विस्तारित किया जाता है, >> को अर्धरेखीय तकनीकों द्वारा सरल किया जाता है
ANF सफाई — अवशोषण, सामान्य-घन गुणनखंडन और OR पहचान
कॉन्फ़िगर करने योग्य बिटचौड़ाई — 1-बिट से 64-बिट मॉड्यूलर अंकगणित
सहायक चर उन्मूलन — जब पद रद्द हो जाते हैं तो चरों की संख्या कम हो जाती है
Z3 सत्यापन — सरलीकृत आउटपुट की वैकल्पिक समतुल्यता जाँच
स्पॉट-चेक स्व-परीक्षण — जब Z3 उपलब्ध न हो तो हल्का यादृच्छिक-इनपुट मान्यकरण
LLVM पास प्लगइन — संकलक पाइपलाइनों में सीधे एकीकृत करें (LLVM 19-22 आवश्यक)

निर्माण

पूर्ण विवरण के लिए BUILD.md देखें जिसमें वैकल्पिक निर्भरताएँ (LLVM, Z3) शामिल हैं।

# Build dependencies (Abseil, Highway; optionally GoogleTest, LLVM, Z3)
cmake -S dependencies -B build-deps -DCMAKE_BUILD_TYPE=Release
cmake --build build-deps

# Build CoBRA
cmake -S . -B build \
  -DCMAKE_PREFIX_PATH=$(pwd)/build-deps/install \
  -DCMAKE_BUILD_TYPE=Release
cmake --build build

# (Optional) Build and run tests
cmake -S dependencies -B build-deps -DCMAKE_BUILD_TYPE=Release -DCOBRA_BUILD_TESTS=ON
cmake --build build-deps
cmake -S . -B build \
  -DCMAKE_PREFIX_PATH=$(pwd)/build-deps/install \
  -DCMAKE_BUILD_TYPE=Release \
  -DCOBRA_BUILD_TESTS=ON
cmake --build build
ctest --test-dir build --output-on-failure

LLVM पास प्लगइन के साथ

cmake -S . -B build \
  -DCMAKE_PREFIX_PATH=$(pwd)/build-deps/install \
  -DCOBRA_BUILD_LLVM_PASS=ON \
  -DCMAKE_BUILD_TYPE=Release
cmake --build build

उपयोग

# Basic simplification
cobra-cli --mba "(x&y)+(x|y)"

# Specify bitwidth
cobra-cli --mba "(x&0xFF)+(x&0xFF00)" --bitwidth 16

# Enable Z3 equivalence verification
cobra-cli --mba "(a^b)+(a&b)+(a&b)" --verify

# Verbose output (show intermediate pipeline steps)
cobra-cli --mba "(x&y)+(x|y)" --verbose

विकल्प

परियोजना संरचना

lib/core/                मुख्य सरलीकरण इंजन (~50 स्रोत फ़ाइलें)
  Orchestrator             कार्यसूची अनुसूचक, स्थिति मशीन, मुख्य सरलीकरण लूप
  OrchestratorPasses       39-पास रजिस्ट्री DAG-जागरूक शेड्यूलिंग के साथ
  CompetitionGroup         बहु-तकनीक दौड़ और विजेता चयन
  ContinuationTypes        पास संरचना के लिए विलंबित पुनर्संयोजन डेटा
  JoinState                संरचनात्मक पुनर्लेखन के लिए बहु-संकार्य जॉइन ट्रैकिंग
  SignatureSimplifier      हस्ताक्षर-आधारित तकनीकें (CoB, पैटर्न मिलान, ANF)
  SignatureVector          {0,1}^n इनपुट पर अभिव्यक्ति का मूल्यांकन
  AuxVarEliminator         रद्दीकरण का पता लगाकर चर संख्या कम करना
  PatternMatcher           बिटवाइज़ पैटर्न पहचानें (2-var/3-var तालिकाएँ, स्केल किया गया)
  CoeffInterpolator        गुणांक पुनर्प्राप्ति के लिए बटरफ्लाई इंटरपोलेशन
  CoBExprBuilder           CoB गुणांकों से अभिव्यक्तियों का पुनर्निर्माण
  AnfTransform             बीजगणितीय सामान्य रूप रूपांतरण
  AnfCleanup               अवशोषण, गुणनखंडन, OR पहचान
  CoefficientSplitter      बिटवाइज़ बनाम अंकगणितीय योगदानों को अलग करना
  ArithmeticLowering       अंकगणितीय खंड को बहुपद IR में निम्न करना
  PolyNormalizer           बहुपद अभिव्यक्तियों के लिए विहित रूप
  SingletonPowerRecovery   परिमित अंतरों के माध्यम से x^k पदों का पता लगाना
  DecompositionEngine      निकालें-हल करें लूप: बहुपद कोर + अवशेष समाधान
  GhostBasis               घोस्ट प्रिमिटिव लाइब्रेरी (mul_sub_and, mul3_sub_and3)
  GhostResidualSolver      बूलियन-नल वर्गीकरण और घोस्ट अवशेष समाधान
  WeightedPolyFit          बहुपद भागफलों के लिए 2-एडिक भारित रैखिक समाधान
  MixedProductRewriter     बिटवाइज़ गुणनफलों को रैखिक योगों में विस्तारित करना
  TemplateDecomposer       मिश्रित अभिव्यक्तियों के लिए बाधित टेम्पलेट मिलान
  ProductIdentityRecoverer योगों के गुणनफल पहचानों को पुनर्प्राप्त करना
  SemilinearNormalizer     भारित बिटवाइज़ परमाणुओं में विघटित करना
  SemilinearSignature      प्रति-बिट हस्ताक्षर मूल्यांकन और रैखिक शॉर्टकट
  StructureRecovery        XOR पुनर्प्राप्ति, मास्क उन्मूलन, पद सहसंयोजन
  TermRefiner              मृत-बिट मास्क कमी, समान-गुणांक विलय
  BitPartitioner           बिट स्थितियों को अर्थपूर्ण प्रोफ़ाइल द्वारा समूहित करना
  MaskedAtomReconstructor  असंयुक्त मास्कों के लिए OR-पुनर्लेखन के साथ पुनः संयोजन
  Evaluator                संकलित अभिव्यक्ति मूल्यांकक

lib/llvm/                LLVM पास प्लगइन (CobraPass, MBADetector, IRReconstructor)
lib/verify/              Z3-आधारित समतुल्यता सत्यापन
include/cobra/           सार्वजनिक शीर्षलेख
tools/cobra-cli/         CLI फ्रंटएंड और अभिव्यक्ति पार्सर
test/                    63 परीक्षण फ़ाइलों में 1195 परीक्षण

परीक्षण

CoBRA में 1195 परीक्षण हैं जो इकाई, एकीकरण और डेटासेट बेंचमार्क को कवर करते हैं:

# सभी परीक्षण चलाएँ
ctest --test-dir build --output-on-failure

# एक विशिष्ट परीक्षण सूट चलाएँ
ctest --test-dir build -R test_simplifier --output-on-failure

# विस्तृत आउटपुट के साथ चलाएँ
ctest --test-dir build -V

डेटासेट बेंचमार्क कई स्वतंत्र स्रोतों से वास्तविक-विश्व ऑब्फस्केटेड अभिव्यक्तियों के विरुद्ध मान्य करते हैं। पूर्ण बेंचमार्क रिपोर्ट के लिए DATASETS.md देखें — 7 स्वतंत्र स्रोतों से 35 डेटासेट फ़ाइलों में 75,126 अभिव्यक्तियाँ।

ज्ञात सीमाएँ

गहराई से मिश्रित बहुपद MBA — शेष असमर्थित अभिव्यक्तियाँ मुख्य रूप से बड़ी, भारी दोहराए गए AST हैं जिनमें अंतःस्थित अंकगणितीय और बिटवाइज़ ऑपरेटर होते हैं। प्रभाव-क्रमांकित उप-अभिव्यक्ति लिफ्टिंग इनमें से कई को पुनर्प्राप्त करती है, लेकिन जो अभिव्यक्तियाँ लिफ्टिंग के बाद कार्यसूची बजट समाप्त कर देती हैं वे असमर्थित रहती हैं
बूलियन-डोमेन पुनर्निर्माण विचलन — बहुत कम अभिव्यक्तियाँ CoB उम्मीदवार उत्पन्न करती हैं जो {0,1} इनपुट पर सही होते हैं लेकिन पूर्ण चौड़ाई पर गलत होते हैं (AND-उत्पाद आधार बनाम अंकगणितीय गुणन)। इन्हें पहचाना जाता है और विफल-सत्यापित के रूप में सही ढंग से रिपोर्ट किया जाता है
कोई सामान्य तर्क न्यूनीकरण नहीं — CoBRA लालची बीजगणितीय पुनर्लेखन का उपयोग करता है, Quine-McCluskey/Espresso/BDD का नहीं

आभार

Bas Zweers और Back Engineering टीम को उनकी प्रेरणा और मार्गदर्शन के लिए धन्यवाद जिसने इस परियोजना को आकार देने में मदद की। अनुशंसित देखने के लिए: उनका re//verse 2026 टॉक एक वास्तविक-विश्व बाइनरी ऑब्फस्केटर का डीऑब्फस्केशन।

Jack Royer, Matteo Favaro, Arnau Gàmez और अन्य गुमनाम योगदानकर्ताओं को निरंतर समीक्षा और परीक्षण के लिए अतिरिक्त धन्यवाद।

लाइसेंस

Apache-2.0। test/datasets/ में परीक्षण डेटासेट तृतीय-पक्ष अनुसंधान परियोजनाओं से उनके मूल लाइसेंसों (मुख्यतः GPL-3.0) के तहत पुनर्वितरित किए जाते हैं। विवरण के लिए THIRD_PARTY_LICENSES देखें।

`--mba <expr>`		सरल करने के लिए अभिव्यक्ति
`--bitwidth <n>`	64	मॉड्यूलर अंकगणित की चौड़ाई (1-64)
`--max-vars <n>`	16	अधिकतम चर संख्या
`--verify`	बंद	Z3 समतुल्यता जाँच
`--verbose`	बंद	पाइपलाइन आंतरिक प्रिंट करें

CoBRA

सबसे लोकप्रिय

CoBRA

यह कैसे काम करता है

विशेषताएँ

निर्माण

LLVM पास प्लगइन के साथ

उपयोग

विकल्प

परियोजना संरचना

परीक्षण

ज्ञात सीमाएँ

आभार

लाइसेंस