参考教程案例chp06.6-bugsearch

1、Bug SearchXU, Hui August 31, 2022COMP130159.01MotivationBugs have similar patternsIf rules can be extracted:Search possible bugs based on rulesTypical cases are related to exception handlingOtherwiseSearch possible bugs based on a bug repositorySimilarity-based approachBug Avoidance ApproachesBug Av

2、oidanceDynamic analysis Static analysis Search Rule-basedSimilarity-basedCompiler techniquesType checkingAbstract interpretationTestingSymbolic executionFuzzing1. Rule-based ApproachError HandlingIn error handling paths, the driver should release the acquired resources and execute the operations tha

3、t are opposite to its previous execution.Bugs occur if developers forget/fail to handle the errors properly. Liu, Huqiu, et al. PF-Miner: A new paired functions mining method for Android kernel in error paths. ACSAC 2014.An Example 1. request memory (successful)3. return without memory release2. ior

4、emap (fail), goto outA bug found in Android kernel 3.10.0: drivers/ide/au1xxx-ide.cPaired Function MiningSome functions should be used pairwise, e.g.,pci_ioremap, pci_iounmappci_enable_device, pci_disable_deviceBasic idea of PF-Miner:Find paired functions of a target project.Assuming paired function

5、s are unknown in advance.Otherwise, a dictionary of paired functions can be employed. Label paired functions on the control-flow graph;Detect violations by checking all control flows.Liu, Huqiu, et al. PF-Miner: A new paired functions mining method for Android kernel in error paths. ACSAC 2014.How t

6、o Detect Paired Functions?Host FunctionCallee 1Callee 2Callee nStep 1: classify callees into two sets based on their context:Callees of normal paths;Callees of exception paths.Step 2: find paires of callees between the two sets.Find Possible Paired CalleesCallees of normal pathspci_enable_device()pc

7、i_request_regions()pci_iomap()Callees of exception pathspci_disable_device()pci_release_regions() pc_enable_device()pci_request_regions()pci_iomap()pci_disable_device()pci_releason_regions()pci_disable_device() failsuccessfulfailsuccessfulfailsuccessfulEvaluate If Two Callees Can Be PairedPaired fun

8、ctions should operate on the same resource in an opposite manner, e.g., by splitting the identifier of pci_enable_device() and pci_disable_device()Resource: pci_deviceOpposite operation: enable, disableDetect Violationsrequest_mem_region()ioremap()outfailsuccessfulsuccessfulfailViolation condition (

9、no resource release): a route with only one of the paired function that is successfully executed.EvaluationAndroid kernel version 2.6.39 (forked from Linux).81 bugs reported by PF-Miner (all fixed in 3.10.0)26 paired functions50 driversAndroid kernel 3.10.0983 violations from 4225 driversTop 51 are

10、potential bugsNeed to confirm with developers.546 paired functions3. Similarity-based ApproachCode SimilarityTo measure how much two code snippets/functions are alike or different from each other.“Hello World” Compiled with GCC“Hello World” Compiled with Clangpush rbpmov rbp, rsplea rdi, s; Hello Wo

11、rldcall _putsmov eax, 0pop rbpretnvar_8= dword ptr -8var_4= dword ptr -4push rbpmov rbp, rspsub rsp, 10hmov rdi, offset format ; Hello Worldnmov rbp+var_4, 0mov al, 0call _printfxor ecx, ecxmov rbp+var_8, eaxmov eax, ecxadd rsp, 10hpop rbpretnPreliminary Features in BinDiffFunction Matchinghash matc

12、hingname hash matchingaddressstring referencesloop countcall sequenceBasic Block Matchinghash matchingcall reference matchingstring reference matching Problem Definition and IdeasIdea 1:Locate suspicious code snippets, and then compare the similarityPairwise Graph MatchingIdea 2:Create an embedding

13、for each bug (codebook), and then search similar embeddings Graph EmbeddingBug Repobug code 1bug code 2bug code nSearchProblem: searching bugs with a set of bug samples as conditions, which is more difficult than searching documents.Pairwise Graph MatchingStep 1: compute the distance between each ba

14、sic-block pair of Graph-A and Graph-BGenerate a block distance matrixStep 2: match Graph-A and Graph-BBipartite matchingMaximum common subgraphCFG Matching as Bipartite MatchingA1A2A3A4B1B2B3B5B4A1A3A2A4B1B2B3B4B5VSVSA5A5Block Similarity: Edit DistanceRemove the variables/constants of each instructi

15、onCompute edit distanceLongest common subsequence (LCS) distance: allow only insertion and deletion, not substitution.Levenshtein distance: allow deletion, insertion and substitution.push eaxlea eax, esp+11Ch+var_108push eaxcall sub_404F5Elea ecx, esp+118h+var_F0call ds:_imp_?1?$CStringTDCmmUAEXZmov

16、 esi, edi+18hmov edi, edicmp esp+118h+var_108, ebxjz short loc_408D5Fpushlea pushcallleacallmovmovcmpjzstemFind the Longest Common Subsequence pushmovsubmovmovmovcallxormovmovaddpopretnpushmovleacallmovpopretn/sample solution with dynamic programming /a is a sequence with i instructions/b is a seque

17、nce with j instructionsLCS(a,b,i,j) if (i = 0 or j = 0) return 0; if (ai = bj) return LCS(a,b,i-1,j-1)+1 else return max(LCS(a,b,i-1,j),LCS(a,b,i,j-1)Use the length of the longest common subsequence for distance calculation, e.g.,Weighted Bipartite Graph MatchingA1A2A3A4B1B2B3B4Code ACode BB5A5Kuhn-

18、Munkres Algorithm (Matrix View)CostB1B2B3A10.20.350.40A20.400.100.20A30.150.200.70 Hungarian Maximum Matching AlgorithmStep 3: subtract the smallest value in each column from all other values in the column Step 1: Initiate adjacent matrixStep 2: Subtract the smallest value in each row from the other

19、 values in the rowCostB1B2B3A100.150.20A20.30 0 0.10A300.050.55 CostB1B2B3A100.150.10A20.30 0 0A300.050.45 Step 4: Draw lines through the row and columns that have the 0 entries such that the fewest lines possible are drawn. CostB1B2B3A100.150.10A20.30 0 0A300.050.45 Kuhn-Munkres Algorithm (Matrix V

20、iew)Hungarian Maximum Matching AlgorithmStep 5: If there are n lines drawn, an optimal assignment of zeros is possible and the algorithm is finished. If the number of lines is less than n, then the optimal number of zeroes is not yet reached. Go to the next step.CostB1B2B3A100.150.10A20.30 0 0A300.0

21、50.45 CostB1B2B3A100.100.5A20.30 0 0A3000.40 Step 6: Find the smallest entry not covered by any line. Subtract this entry from each row that isnt crossed out, and then add it to each column that is crossed out. Then, go back to Step 4. CostB1B2B3A100.100.5A20.30 0 0A3000.40 CostB1B2B3A10.200.350.40A

22、20.400.100.20A30.150.200.70 CFG Matching as MCSGeneral Maximum Common Subgraph (MCS) Problem: Find the largest subgraph isomorphic to two graphs.Eschweiler et al. discovRE: Efficient Cross-Architecture Identification of Bugs in Binary Code. NDSS. 2016.Weighted Maximum Common Subgraph (MCS) Problem:

23、consider the distance between blocks.McGregor Algorithm for MCS Approximation/incremental search/start with an initial subgraph sWhile(NextPair(s,ai,bj) If(IsFeasible(s,ai,bj) snew=AddPair(s, ai,bj) If (snew is expandable) MCS(snew) BackTrack(snew) A1A2A3A4B1B2B3B5B4A5A2current sB2possible pairsA1B1

24、B5A5feasible pairsA1B1Eschweiler et al. “discovRE: Efficient Cross-Architecture Identification of Bugs in Binary Code.” NDSS. 2016.Wang, et al. A novel efficient algorithm for determining maximum common subgraphs. IV, 2005.Graph EmbeddingAn embedding is a high-dimensional vector for representing the graph.Idea：Create an embedding for each bug.Create an embedding for each function of the target project.Search similar embeddings Xu et al. Neural network-based graph embedding for cross-platform binary code similarity detection. CCS 2017.Generate Attributed Contr