Chinese Journal of Computers   Full Text
Title	A Polynomial Time Path-Sensitive Taint Analysis Method
Authors	LI Jia-Jing1)，2)，3) WANG Tie-Lei2),3) WEI Tao2),3) FENG Wang-Sen2)，4) ZOU Wei2),3)
Address	1)(School of Mechanical Electronic and Information Engineering， China University of Mining & Technology(Beijing), Beijing 100083) 2)(Key Laboratory of Network and Software Security Assurance(Peking University), Ministry of Education, Beijing 100871) 3)(Institute of Computer Science & Technology, Peking University, Beijing 100871) 4)(Computer Center, Peking University, Beijing 100871)
Year	2009
Issue	No.9(1845—1855)
Abstract &   Background	Abstract This paper proposes a method to solve the path explosion problem in path-sensitive taint analysis. The method transformed the taint analysis problem into a generalized pushdown successor problem by bringing the weighted pushdown system theory into taint analysis, so it could reduce the number of paths to be accurately executed. With this method, taint analysis can be performed in a polynomial time, and counter paths can be automatically generated. The authors designed experiments based on this method to model and detect keylogging behaviors. By comparing the authors’ work with existing methods such as the raw traversal method and the full point-wise method, it is found to have exceptional efficiency in processing complex binary programs with a lot of branches, and has both a smaller time expense and a smaller space expense. Keywords weighted pushdown system; dateflow analysis; taint analysis; malicious behavior; keylogger