计算机科学 ›› 2015, Vol. 42 ›› Issue (9): 171-176.doi: 10.11896/j.issn.1002-137X.2015.09.033

• 软件与数据库技术 • 上一篇    下一篇

基于存储访问模型的细粒度存储变量识别算法

井靖,蒋烈辉,何红旗,张媛媛   

  1. 信息工程大学计算机科学与技术学院 郑州450000,信息工程大学计算机科学与技术学院 郑州450000;数学工程与先进计算国家重点实验室 郑州450000,信息工程大学计算机科学与技术学院 郑州450000;数学工程与先进计算国家重点实验室 郑州450000,72495部队自动化站 郑州450002
  • 出版日期:2018-11-14 发布日期:2018-11-14
  • 基金资助:
    本文受国家自然科学基金项目(61272489)资助

Fine-grained Variable Entity Identification Algorithm Based on Memory Access Model

JING Jing, JIANG Lie-hui, HE Hong-qi and ZHANG Yuan-yuan   

  • Online:2018-11-14 Published:2018-11-14

摘要: 现阶段对变量的识别通常采用基于特定编译习惯及内存访问地址模式匹配的方法,或基于内存模型和抽象解释的分析方法。前者针对性太强,不具备普适性;后者通常采用损失算法精度的方法来得到结果,这往往会造成识别变量粒度过大、漏识别和误识别率较高。首先定义一种存储访问模型,对存储操作进行细粒度的模拟;然后给出基于存储访问模型的抽象状态生成算法,实现了基于高级中间语言HBRIL的细粒度数据信息(抽象状态)的跟踪和记录;基于这些抽象状态设计了存储区域内的细粒度变量实体识别算法;最后通过测试给出变量识别的细化比例和识别率。由测试结果可以看出,该算法在动态分配变量的识别率方面具有明显优势。

关键词: 细粒度内存访问模型,存储环境,存储操作模拟,变量实体,抽象状态

Abstract: There are two popular methods for variable identification.One is based on specific compiler habits and matching on memory address access mode,another is based on memory model and abstract interpretation technology.The former method is applicable to some specific compliers;the latter one often gets coarse-grained variables and higher wrong identification rate,because it has to consider the balance of accurate and time costs.In this paper,a fine-grained memory access model was defined firstly,which can simulate the fine-grained memory operation.And an abstract-state generation algorithm was given based on this model,which can track and record the fine-grained data information for advanced intermediate language HBRIL.Then a novel variable entity identification algorithm on memory region was designed according to data information.At last,the variables’ refinement proportion and recognition rate were given.The test results show that our approach gets higher identification ratio for dynamic allocated variables.

Key words: Fine-grained memory access model,Memory environment,Memory operation simulate,Variant entity,Abstract state

[1] Lin Zhi-qiang.Reverse engineering of data structures from binary[D].West Lafayette:Purdue University,2011
[2] Van Emmerik M.Single Static Assignment for Decompilation[D].Queensland:University of Queensland,2006
[3] 孙维新.二进制翻译中基本数据类型分析的研究与实现[D].郑州:解放军信息工程大学,2007 Sun Wei-xin.Study and implementation basic data type analysis in static binary translation[D].Zhengzhou:PLA Information Engineering University,2007
[4] 何东,尹青,谢耀宾,等.反编译中数据类型自动重构技术研究[J].计算机科学,2012,39(5):133-136 He Dong,Yin Qing,Xie Yao-bin,et al.Automatic data type reconstruction in decompilation[J].Computer Sciense,2012,39(5):133-136
[5] 马金鑫,李舟军,忽朝俭,等.一种重构二进制代码中类型抽象的方法[J].计算机研究与发展,2013,50(11):2418-2428 Ma Jin-xin,Li Zhou-jun,Hu Chao-jian,et al.A reconstruction method of type abstraction in binary code[J].Journal of Computer Research and Development,2013,50(11):2418-2428
[6] Ding Wei,Gu Zhi-ming,Gao Feng.Reconstruction of data type in obfuscated binary programs[C]∥16th International Confe-rence on Advanced Communication Technology.PyeongChang,South Korea,2014:393-369
[7] Balakrishnan G,Reps T.WYSINWYX:What you see is notwhat you execute[J].ACM Transactions on Programming Languages And Systems,2010,32(6):202-213
[8] Balakrishnan G,Reps T.DIVINE:discovering variables in executables[C]∥Proceedings of the 8th International Conference on Verification,Model Checking,and Abstract Interpretation.Nice,France,2007:1-28
[9] Anand K,Elwazeer K,Kotha A,et al.An accurate stack memory abstraction and symbolic analysis framework for executables[C]∥29th IEEE International Conference on Software Maintenance.Eindhoven,Netherland,2013:90-99
[10] Cousot P,Cousot R.Interpretation:A unified lattice model for static analysis[C]∥Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages.New York,USA 1977:238-252
[11] 王雅文,宫云战,肖庆,等.基于抽象解释的变量值范围分析及应用[J].电子学报,2011,39(2):296-302 Wang Ya-wen,Gong Yun-zhan,Xiao Qing,et al.A method of variable range analysis based on abstract interpretation and its applications[J].ACTA Electronica Sinica,2011,39(2):296-302
[12] Brumley D,Jager I,Avgerinos T,et al.BAP:A binary analysis platform[C]∥23rd International Conference on Computer Aided Verification.Snowbird,UT,USA,2011:463-469
[13] Lee J,Avgerinos T,Brumley D.TIE:Principled Reverse Engi-neering of Types in Binary Programs[C]∥Proceedings of the Network and Distributed System Security Symposium.San Diego,USA,2011:session 5
[14] Song D,Brumley D,Yin Heng,et al.BitBlaze:A new approach to computer security via binary analysis[C]∥4th International Conference on Information Systems Security.Hyderabad,India,2008:1-25
[15] Aho A V,Lam M S,Sethi R,et al.Compilers:Principles,Techniques,and Tools(2nd Edition)[M].Boston:Addison Wesley,2007
[16] 刘絮颖.反编译中控制流重构与控制结构恢复技术研究[D].郑州:解放军信息工程大学,2011 Liu Xu-ying.Research on technology of control flow reconstruction and control structure recovery in decompilation[D].Zhengzhou:PLA Information Engineering University,2011
[17] Durfina L,Kroustek J,Zemek P,et al.Detection and recovery of functions and their arguments in a retargetable decompiler[C]∥19th Working Conference on Reverse Engineering.Kingston,Canada,2012:56-60
[18] 吴滨.汇编级程序辅助分析中的库函数识别技术研究[D].郑州:解放军信息工程大学,2011 Wu Bin.Research on library function identification technology in assemble level program auxiliary analysis[D].Zhengzhou:PLA Information Engineering University,2011
[19] Jing Jing,Jiang Lie-hui,Liu Tie-ming,et al.A precision-tunable CFG reconstruction algorithm[C]∥International Conference on Mechatronic Sciences,Electric Engineering and Computer.Shenyang,China,2013:2095-2099

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!