EtWExplorer: Multi-Priority Scheduling Path Exploration Technology Based on Abstract Syntax Tree Analysis
EtWExplorer: Multi-Priority Scheduling Path Exploration Technology Based on Abstract Syntax Tree Analysis
复制标题
EtWExplorer：基于抽象语法树分析的多优先级调度路径探索技术
DOI：
10.3390/app121910182
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Zhou Xu
中科院分区：
文献类型：
--
作者：
He Xinglu;Wang Pengfei;Lu Kai;Zhou Xu
Symbolic execution is well known as a dynamic vulnerability discovery technique. Its greatest advantage is the capability to analyze the execution information of the program and to explore the path in the program deterministically. This is a more accurate way to determine if there are vulnerabilities in a program than randomized testing by fuzzing. In addition, symbolic execution does not suffer from the problem of decreasing the capability to discover new paths as more paths are discovered, similar to that caused by random-based fuzzing. However, the reason why symbolic execution is not widely used in vulnerability discovery is mainly due to the state space explosion in the program. The state space explosion severely affects the applicability of symbolic execution. To further improve the applicability of symbolic execution, this paper proposes a path exploration technology based on abstract syntax tree analysis. With the distance between the expression generated by the symbolic execution of the repeat location and the “unsatisfiable” condition of the “unsat” state, we can perform multi-priority scheduling for the repeat location state, thus mitigating the impact of the state space explosion on path exploration. We proposed and implemented EtWExplorer, a multi-priority scheduling technique based on abstract syntax tree analysis. With this technique, we can significantly improve the capability of symbolic execution to discover unknown paths even in state space exploration. Experiments show that EtWExplorer introduces a performance overhead of 72% in the worst case and can improve performance by 294% in the best case. EtWExplorer has a 95% improvement in state space explosion mitigation capability and a 199% to 983% improvement in the path exploration capability of block coverage and a 181% to 1047% improvement in the path exploration capability of edge coverage when facing programs that cause a state space explosion.
登录
查看更多内容
DOI：
10.1109/sp40000.2020.00002
发表时间：
2019-06
期刊：
2020 IEEE Symposium on Security and Privacy (SP)
影响因子：
--
作者：
Yaohui Chen;Peng Li;Jun Xu;Shengjian Guo;Rundong Zhou;Yulong Zhang;Tao Wei;Long Lu
通讯作者：
Yaohui Chen;Peng Li;Jun Xu;Shengjian Guo;Rundong Zhou;Yulong Zhang;Tao Wei;Long Lu
DOI：
10.1016/s1571-0661(04)81042-9
发表时间：
2003-10
期刊：
--
影响因子：
--
作者：
N. Nethercote;J. Seward
通讯作者：
N. Nethercote;J. Seward
DOI：
10.1145/1321631.1321746
发表时间：
2007-11
期刊：
Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering
影响因子：
--
作者：
Koushik Sen
通讯作者：
Koushik Sen
DOI：
10.14722/ndss.2020.24018
发表时间：
2020
期刊：
Proceedings 2020 Network and Distributed System Security Symposium
影响因子：
--
作者：
Kyungtae Kim;Dae R. Jeong;C. Kim;Yeongjin Jang;I. Shin;Byoungyoung Lee
通讯作者：
Kyungtae Kim;Dae R. Jeong;C. Kim;Yeongjin Jang;I. Shin;Byoungyoung Lee
DOI：
10.1145/1950365.1950396
发表时间：
2011-03
期刊：
--
影响因子：
--
作者：
Vitaly Chipounov;Volodymyr Kuznetsov;George Candea
通讯作者：
Vitaly Chipounov;Volodymyr Kuznetsov;George Candea