Yongchao Wang
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Interests
Yongchao Wang has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- Charles Zhang
Hong Kong University of Science and Technology, Hong Kong, China
1 shared publication - Peisen Yao
The State Key Laboratory of Blockchain and Data Security, Zhejiang University, Hangzhou, China
1 shared publication - Qingkai Shi
Nanjing University
1 shared publication
Latest Publications
- Open Access
- 31 October 2022
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 6 (OOPSLA2) , 1438-1468
Indexing the extended Dyck-CFL reachability for context-sensitive program analysis
Many context-sensitive dataflow analyses can be formulated as an extended Dyck-CFL reachability problem, where function calls and returns are modeled as partially matched parentheses. Unfortunately, despite many works on the standard Dyck-CFL reachability problem, solving the extended version is still of quadratic space complexity and nearly cubic time complexity, significantly limiting the scalability of program analyses. This paper, for the first time to the best of our knowledge, presents a cheap approach to transforming the extended Dyck-CFL reachability problem to conventional graph reachability, a much easier and well-studied problem. This transformation allows us to benefit from recent advances in reachability indexing schemes, making it possible to answer any reachability query in a context-sensitive dataflow analysis within almost constant time plus only a few extra spaces. We have implemented our approach in two common context-sensitive dataflow analyses, one determines pointer alias relations and the other tracks information flows. Experimental results demonstrate that, compared to their original analyses, we can achieve orders of magnitude (10 2 × to 10 5 ×) speedup at the cost of only a moderate space overhead. Our implementation is publicly available.
- 31 October 2022
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 6 (OOPSLA2) , 1438-1468
Open AccessIndexing the extended Dyck-CFL reachability for context-sensitive program analysis
Many context-sensitive dataflow analyses can be formulated as an extended Dyck-CFL reachability problem, where function calls and returns are modeled as partially matched parentheses. Unfortunately, despite many works on the standard Dyck-CFL reachability problem, solving the extended version is still of quadratic space complexity and nearly cubic time complexity, significantly limiting the scalability of program analyses. This paper, for the first time to the best of our knowledge, presents a cheap approach to transforming the extended Dyck-CFL reachability problem to conventional graph reachability, a much easier and well-studied problem. This transformation allows us to benefit from recent advances in reachability indexing schemes, making it possible to answer any reachability query in a context-sensitive dataflow analysis within almost constant time plus only a few extra spaces. We have implemented our approach in two common context-sensitive dataflow analyses, one determines pointer alias relations and the other tracks information flows. Experimental results demonstrate that, compared to their original analyses, we can achieve orders of magnitude (10 2 × to 10 5 ×) speedup at the cost of only a moderate space overhead. Our implementation is publicly available.