We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

GRAP: define and match graph patterns within binaries

00:00

Formal Metadata

Title
GRAP: define and match graph patterns within binaries
Title of Series
Part Number
10
Number of Parts
20
Author
License
CC Attribution 4.0 International:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language
Production PlaceBrüssel

Content Metadata

Subject Area
Genre
Abstract
Disassembled binary code can be turned into a graph of instructions linked by possible execution flow (Control Flow Graph). Based on academic research on malware detection through graph matching and facing large numbers of similar files to analyze, we aim to provide accurate results to an analyst working on malware families. Our approach is a YARA-like detection tool: GRAP matches user-defined graph patterns against the CFG of a given code. GRAP is a standalone tool that takes patterns and binary files, uses a Capstone-based disassembler to obtain the CFGs from the binaries, then matches the patterns against them. Patterns are user-defined graphs with instruction conditions (“opcode is xor and arg1 is eax”) and repetition conditions (3 identical instructions, basic blocks…). The algorithm solves a simplified version of the subgraph isomorphism problem, allowing the matching to be very quick. It can be used to find generic patterns such as loops and to write signatures to detect malware variants. We also developed a plugin giving IDA the capabilities to detect and browse matches directly within the GUI. Python bindings are available to create scripts based on GRAP and extract valuable information (addresses, instructions) from matched parts. In this talk, we will introduce the algorithms used and then focus on practical use cases: detect common patterns (from the command line or within IDA), create a malware pattern, and extract information from matched instructions. The tool and the plugin will be released under an open source license.
Hacker (term)ArmWordPattern matchingBinary codeSoftware design patternMalwareGraph theoryPlug-in (computing)Multiplication signComputer animationJSON
Regulärer Ausdruck <Textverarbeitung>AlgorithmExclusive orElectronic signatureGraph theoryKeyboard shortcutDepth-first searchMalwareRight angleParameter (computer programming)Functional (mathematics)Control flowEncryptionCoroutineSequencePattern languageWordConfiguration spaceMatching (graph theory)Graph (mathematics)Computer fileSoftware design patternDisassemblerBinary codeCategory of beingSystem callCondition numberSampling (statistics)Software testingExpressionWritingBranch (computer science)FamilyOpen sourceNumberRepresentation (politics)Address spaceRootObject (grammar)Library (computing)Slide ruleProgramming languageProjective planeMereologyComputer programmingConnectivity (graph theory)Mathematical analysisAssembly languageForm (programming)Instance (computer science)Shared memorySeries (mathematics)Presentation of a groupSpacetimeLatent heatGrass (card game)Set (mathematics)Cross-correlation1 (number)Greatest elementElectronic mailing listEquivalence relationServer (computing)SummierbarkeitRevision controlFile viewerState of matterPoint (geometry)MaizeSheaf (mathematics)Covering spaceMultiplication signCone penetration testComputer animation
Address spaceSpecial unitary groupCondition numberGroup actionRight angleControl flowMatching (graph theory)CodeGraph (mathematics)Graph theoryAlgorithmGreatest elementSheaf (mathematics)EncryptionParameter (computer programming)BitNumberGoodness of fitRepresentation (politics)MereologyMultiplication signWordDirected graphCASE <Informatik>Core dumpGenetic programmingProgramming languageFlagArithmetic meanWebsiteInstance (computer science)GodPattern languageFunctional (mathematics)System callForm (programming)Field (computer science)SequenceSelectivity (electronic)Block (periodic table)WeightConstructor (object-oriented programming)TwitterMathematicsMaxima and minimaInsertion lossShared memoryChainDefault (computer science)Point (geometry)DivisorBasis <Mathematik>Software design patternDegree (graph theory)Cone penetration testDifferent (Kate Ryan album)Sampling (statistics)RootLatent heatDot productVariancePolynomialPotenz <Mathematik>CoroutineOpcodeString (computer science)Graph coloringBranch (computer science)Exclusive orCountingWritingComputer fileTraverse (surveying)Computer animation
Computer fileExclusive orBinary codeMatching (graph theory)Sampling (statistics)Software testingPattern languageVariable (mathematics)Graph (mathematics)Revision controlLine (geometry)Function (mathematics)EncryptionSpacetimeSoftware design patternControl flowSpecial unitary groupEuler anglesArea2 (number)Atomic numberDirection (geometry)Fisher's exact testComputer animation
Functional (mathematics)Pattern languageSystem callAlgorithmBlock (periodic table)EncryptionParameter (computer programming)Group actionKernel (computing)RootRevision controlPoint (geometry)Multiplication signControl flowComputer animation
Graph coloringPoint (geometry)System callEncryptionAlgorithmControl flowSoftware design patternExclusive orPattern language1 (number)Sampling (statistics)Constraint (mathematics)Greedy algorithmIntegrated development environmentMatching (graph theory)Computer animationSource codeJSON
Exclusive orAlgorithmBinary codeSampling (statistics)Pattern languageSheaf (mathematics)Service (economics)Boundary value problemMatching (graph theory)Insertion lossControl flowElectronic signatureWorkstation <Musikinstrument>Graph theoryObservational errorGenetic programmingNatural numberDatabaseSpacetimeSpectrum (functional analysis)Computer fileSlide ruleBlock (periodic table)Source codeComputer animation
2 (number)Electronic signatureAtomic numberType theorySampling (statistics)Matching (graph theory)Category of beingSoftware design patternState of matterAreaBinary codePattern languageComputer fileExclusive orComputer animation
Scripting languageResultantSoftware design patternKeyboard shortcutStructural loadSoftware testingGraph theoryPattern languageLibrary (computing)SummierbarkeitWeightGraph (mathematics)Matching (graph theory)Binary codeComputer fileComputer animation
EncryptionSystem callAddress spaceFunctional (mathematics)Matching (graph theory)Point (geometry)Demo (music)String (computer science)InformationCoroutineParameter (computer programming)Control flowGroup actionComputer animation
Graph theoryScripting languageSoftware design patternBinary codeSystem callEncryptionFunctional (mathematics)Computer fileExclusive orPoint (geometry)String (computer science)AlgorithmAddress spaceVarianceConfiguration spaceGodCoroutineSampling (statistics)Moment (mathematics)Inheritance (object-oriented programming)Figurate numberSet (mathematics)Windows RegistryClient (computing)SpacetimeDescriptive statisticsSource codeJSONComputer animation
Graph (mathematics)Plug-in (computing)Software design patternMatching (graph theory)Keyboard shortcutGraph coloringGraph theoryMoving averageFilter <Stochastik>Key (cryptography)Functional (mathematics)Pattern languageControl flowMultiplication sign2 (number)Set (mathematics)NumberMaxima and minimaThresholding (image processing)Rule of inferencePosition operatorDescriptive statisticsRight angleError messageSingle-precision floating-point formatGroup actionMiniDiscForcing (mathematics)Form (programming)Greatest elementEncryptionSpecial unitary groupBit rateMereologyComputer animation
Matching (graph theory)Functional (mathematics)Software design patternPoint (geometry)EncryptionNumberFingerprintFamilyGraph coloringPort scannerComputer animation
Matching (graph theory)AlgorithmElectronic signatureNumberPattern languageInsertion lossMaxima and minimaForm (programming)Attribute grammarCore dumpCASE <Informatik>Branch (computer science)Graph (mathematics)Condition numberInstance (computer science)TwitterElectric generatorContent (media)Position operatorGroup actionPerspective (visual)Block (periodic table)Chaos (cosmogony)CryptographyGoodness of fitSoftware design patternBinary codeVariable (mathematics)Arithmetic meanSummierbarkeitSoftware testingMultiplication signString (computer science)Rule of inferenceParameter (computer programming)Semantics (computer science)Hacker (term)Spherical capSpacetimeRevision controlBitRegulärer Ausdruck <Textverarbeitung>Grass (card game)Point (geometry)Sheaf (mathematics)Atomic numberInformationGravitationAlpha (investment)Open sourcePhysical lawAddress spaceWordGreatest elementVector spaceGame theoryComputer fileSelectivity (electronic)System callIntegerGraph theoryMathematical analysisKeyboard shortcutOpcodeControl flowMeta elementLimit (category theory)Exclusive orOcean currentComputer animation
Physical systemError messageMultiplication sign
Computer animation
Transcript: English(auto-generated)