An Branch Obfuscation Research on Path Branch Which Formed by Floating-point Comparison
-
摘要:
针对当前分支混淆方法仅对整数比较分支有效的缺陷,该文分析浮点数二进制表示与大小比较的关系,证明了浮点数二进制区间的前缀集合与浮点数区间内数据之间具有前缀匹配关系。使用哈希函数对前缀集合进行保护,利用哈希函数的单向性实现对抗符号执行,通过哈希值比对替换浮点数比较,提出一种基于前缀哈希值比较的分支条件混淆技术,实现了一种在符号执行对抗和混淆还原对抗上具有较强对抗性的混淆方法。最后,通过实验证和分析,证实了该文提出的混淆方法有消耗小、能够有效对抗符号执行和混淆还原的优点,具备较好的实用性。
Abstract:For the faultiness that the recent branch obfuscation method is only efficient on branch condition formed by integer comparison. The relations between the binary representation and big or small comparison of floats are analyzed. The idea that the floats in float interval has prefix matching relation with the prefix set which comes from the binary representation interval of the floats is proved. By protecting the prefix set with Hash function, and based on the comparison of prefix-Hash, a new branch obfuscation method which works well on the branch formed by float number comparison is proposed. The new obfuscation method is powerful on symbolic execution combating and obfuscation recovery combating. At last, the obfuscation proposed in this paper is confirmed to be practical, and is useful to be against symbolic execution and obfuscation recovery.
-
Key words:
- Branch obfuscation /
- Float number comparison /
- Prefix algorithm /
- Symbolic execution
-
算法1 前缀算法 输入:a1a2···an//起始值a的二进制表示 b1b2···bn//结束值b的二进制表示 输出:PrefixSet//区间的前缀集合 PrefixSet Get_Prefix(a1a2···an,b1b2···bn) { for (int k=1; (k<=n) && (ak==bk); k++) { if (k==(n+1)) return { a1a2···an}; } if ((akak+1···an == 00···0) && (bkbk+1···bn == 11···1)) { if (k== 1) return {*}; else return {a1a2···ak-1}; } PrefixSet1 = Get_Prefix(ak+1ak+2···an, 11···1); PrefixSet2 = Get_Prefix(00···0, bk+1bk+2···bn); Return {a1a2···ak-10+PrefixSet1, a1a2···ak-11+PrefixSet2}; } 算法2:isMatch(x, HS) //判断输入为x时,分支条件的取值,算
法返回值为true或者false输入:浮点数x,浮点数区间[a, b]对应二进制前缀集合的sha1集
合HS1和HS2输出:x是否属于浮点数区间[a,b] bool isMatch(x,HS1,HS2) { char tmp[32] = {‘*’,‘*’,···,‘*’}; int Ix= *((int *)&x); char sha1out[32][24]; char sign = (Ix>>(31-i))&1; tmp[0] = sign; for(int i=1; i<32; i++){ tmp[i]=(Ix>>(31-i))&1; sha1out[i]=sha1(tmp,32); char sign = tmp[0]; if(sign == 0) {for(int j=0; j<hashNumofHS1;j++) { if(sha1out[i]==HS1[j]) return true; } } else if(sign == 1) {for(int j=0; j<hashNumofHS2;j++) { if(sha1out[i]==HS2[j]) return true; } } } return false;} 表 1 单分支混淆的消耗数据表
分支条件 空间消耗(Byte) 时间消耗(ms) 解密后前缀数据空间 Sha1算法代码空间 isMatch算法代码空间 if(1.0≤x ≤10.0)混淆后变为:if(isMatch(x, HS1)) 4×20=80 2684 468 0.033 if((x ≤1.0)||((y>10.0)&&(1.0≤z ≤10.0))) 混淆后变为:if(isMatch(x,HS2)||(isMatch (y,HS3) && isMatch(z,HS4))) (9+8+4)×20=440 2684 468 0.102 注释:(1) 空间消耗中,只有前缀数据占用空间是每个分支混淆需要独占的,其余空间是所有分支混淆共享的空间。(2) HS1, HS2, HS3和HS4表示前缀数据的哈希值集合。 表 2 分支混淆前后程序占用空间和执行时间数据表
混淆前的数据处理程序 混淆后的数据处理程序 占用空间(Byte) 37376 41472 执行时间(ms) 2 35.6 被混淆分支数(个) 1 分支执行次数(次) 1000 表 3 混淆方法执行效率比较
混淆方法 单分支单次执行平均时间消耗(ms) 单分支混淆空间消耗(Byte) 实验主机 分支类型 本文方法 0.033 4×103 CPU为Intel I5的主机 浮点数比较 王志方法 0.031 4×103 CPU为Intel I5的主机 整数大小比较 王志方法 (11312-1442.7)/(3×10000)=0.329 4×103 CPU为Intel Core2 Q9400的主机 整数大小比较 陈喆方法 220 9.8×104 CPU为Intel Core2 Q9400的主机 整数大小比较 Ma方法 750 7×103 CPU为Intel Core2 Q9400的主机 整数大小比较 表 4 混淆分支的符号执行测试结果
利用符号执行的程序分析工具 执行时间(min) 结果 Angr 80 求解出使得isMatch返回值为真的分支输入值的解个数为0 KLEE 360 共执行593906条指令和 118个分支执行,但求解出使得isMatch返回值为真的分支输入值的解个数为0 -
Software Management: Security imperative, business opportunity —2018 BSA global software survey. Washington[OL]. https://ww2.bsa.org/-/media/Files/StudiesDownload/2018_BSA_GSS_Report_cn.pdf. 2018. 梁光辉, 庞建民, 单征. 基于代码进化的恶意代码沙箱规避检测技术研究[J]. 电子与信息学报, 2019, 41(2): 341–347. doi: 10.11999/JEIT180257LIANG Guanghu, PANG Jianmin, and SHAN Zheng. Malware sandbox evasion detection based on code evolution[J]. Journal of Electronics &Information Technology, 2019, 41(2): 341–347. doi: 10.11999/JEIT180257 COLLBERG C, THOMBORSON C, and LOW D. A taxonomy of obfuscating transformations[R]. Technical Report 148, 1997. 张跃军, 潘钊, 汪鹏君, 等. 基于状态映射的AES算法硬件混淆设计[J]. 电子与信息学报, 2018, 40(3): 750–757. doi: 10.11999/JEIT170556ZHANG Yuejun, PAN Zhao, WANG Pengjun, et al. Design of hardware obfuscation AES based on state deflection strategy[J]. Journal of Electronics &Information Technology, 2018, 40(3): 750–757. doi: 10.11999/JEIT170556 POPOV I V, DEBRAY S K, and ANDREWS G R. Binary obfuscation using signals[C]. The 16th USENIX Security Symposium, Boston, USA, 2007: 275–290. 贾春福, 王志, 刘昕, 等. 路径模糊: 一种有效抵抗符号执行的二进制混淆技术[J]. 计算机研究与发展, 2011, 48(11): 2111–2119.JIA Chunfu, WANG Zhi, LIU Xin, et al. Branch obfuscation: An efficient binary code obfuscation to impede symbolic execution[J]. Journal of Computer Research and Development, 2011, 48(11): 2111–2119. SHARIF M, LANZI A, GIFFIN J, et al. Impeding malware analysis using conditional code obfuscation[C]. Network and Distributed System Security Symposium, San Diego, USA, 2008: 321–333. WANG Zhi, MING Jiang, JIA Chunfu, et al. Linear obfuscation to combat symbolic execution[C]. The 16th European Symposium on Research in Computer Security, Leuven, Belgium, 2011: 210–226. doi: 10.1007/978-3-642-23822-2_12. ZONG Nan and JIA Chunfu. Branch obfuscation using "Black Boxes"[C]. 2014 Theoretical Aspects of Software Engineering Conference, Changsha, China, 2014: 114–121. doi: 10.1109/TASE.2014.19. MA Haoyu, MA Xinjie, LIU Weijie, et al. Control flow obfuscation using neural network to fight concolic testing[C]. The 10th International Conference on Security and Privacy in Communication Networks, Beijing, China, 2014: 287–304. 王志, 贾春福, 刘伟杰, 等. 一种抵抗符号执行的路径分支混淆技术[J]. 电子学报, 2015, 43(5): 870–878. doi: 10.3969/j.issn.0372-2112.2015.05.006WANG Zhi, JIA Chunfu, LIU Weijie, et al. Branch obfuscation to combat symbolic execution[J]. Acta Electronica Sinica, 2015, 43(5): 870–878. doi: 10.3969/j.issn.0372-2112.2015.05.006 陈喆, 王志, 王晓初, 等. 基于代码移动的二进制程序控制流混淆方法[J]. 计算机研究与发展, 2015, 52(8): 1902–1909. doi: 10.7544/issn1000-1239.2015.20140607CHEN Zhe, WANG Zhi, WANG Xiaochu, et al. Using code mobility to obfuscate control flow in binary codes[J]. Journal of Computer Research and Development, 2015, 52(8): 1902–1909. doi: 10.7544/issn1000-1239.2015.20140607 陈喆, 贾春福, 宗楠, 等. 随机森林在程序分支混淆中的应用[J]. 电子学报, 2018, 46(10): 2458–2466. doi: 10.3969/j.issn.0372-2112.2018.10.020CHEN Zhe, JIA Chunfu, ZONG Nan, et al. Branch obfuscation using random forest[J]. Acta Electronica Sinica, 2018, 46(10): 2458–2466. doi: 10.3969/j.issn.0372-2112.2018.10.020 KING J C. Symbolic execution and program testing[J]. Communications of the ACM, 1976, 19(7): 385–394. doi: 10.1145/360248.360252 崔宝江, 梁晓兵, 王禹, 等. 基于回溯与引导的关键代码区域覆盖的二进制程序测试技术研究[J]. 电子与信息学报, 2012, 34(1): 108–114. doi: 10.3724/SP.J.1146.2011.00532CUI Baojiang, LIANG Xiaobing, WANG Yu, et al. The study of binary program test techniques based on backtracking and leading for covering key code area[J]. Journal of Electronics &Information Technology, 2012, 34(1): 108–114. doi: 10.3724/SP.J.1146.2011.00532 BANESCU S, COLLBERG C, GANESH V, et al. Code obfuscation against symbolic execution attacks[C]. The 32nd Annual Conference on Computer Security Applications, Los Angeles, USA, 2016: 189–200. doi: 10.1145/2991079.2991114. BANESCU S, COLLBERG C, and PRETSCHNER A. Predicting the resilience of obfuscated code against symbolic execution attacks via machine learning[C]. The 26th USENIX Security Symposium, Vancouver, Canada, 2017: 661–678. FAN Jinliang, XU Jun, AMMAR M H, et al. Prefix-preserving IP address anonymization: measurement-based security evaluation and a new cryptography-based scheme[J]. Computer Networks, 2004, 46(2): 253–272. doi: 10.1016/j.comnet.2004.03.033 魏凌波, 冯晓兵, 张驰, 等. 基于前缀保持加密的网络功能外包系统[J]. 通信学报, 2018, 39(4): 159–166. doi: 10.11959/j.issn.1000-436x.2018057WEI Lingbo, FENG Xiaobing, ZHANG Chi, et al. Network function outsourcing system based on prefix-preserving encryption[J]. Journal on Communications, 2018, 39(4): 159–166. doi: 10.11959/j.issn.1000-436x.2018057