Symbolic execution is a powerful technique for systematically exploring the paths of a program and generating the corresponding test inputs. However, its practical usage is often limited by the path explosion problem, that is, the number of explored paths usually grows exponentially with the increase of program size. In this talk, we argue that for the purpose of fault detection it is not necessary to systematically explore the paths. We propose a new symbolic execution approach to mitigate the path explosion problem by predicting and eliminating the redundant paths based on symbolic values. Our approach can achieve the equivalent fault detection capability as traditional symbolic execution without exhaustive path exploration. In addition, we develop a practical implementation called Dependence Guided Symbolic Execution (DGSE) to soundly approximate our approach. Through exploiting program dependence, DGSE can predict and eliminate the redundant paths at a reasonable computational cost. Our empirical study shows that the redundant paths are abundant and widespread in a program. Compared with traditional symbolic execution, DGSE only explores 6.96% to 96.57% of the paths and achieves a speedup of 1.02X to 49.56X.

杨子江博士现任西密西根大学计算机科学系教授。他1996年于中国科技大学计算机系获得学士学位，1999年于美国赖斯大学计算机科学系获得硕士学位，2003年于美国宾夕法尼亚大学计算机与信息科学系获得博士学位。杨博士目前主要从事软件测试及验证领域的研究。迄今为止发表了六十余篇论文(包括CCF推荐A类论文十一篇和B类论文二十篇)及十项美国专利。他获得2008年度ACM TODAES 最佳期刊论文奖, 2008年西密西根大学工学院青年学者奖，2010 PADTAD最佳会议论文奖，2015年谷歌计算机 Engagement奖，和2015年西密西根大学工学院研究成就奖。杨子江博士是国际电子电气工程师协会（IEEE）资深会员，并担任过密西根大学电子与计算机科学系访问教授，NEC 公司美国研发中心科研顾问，美国自然科学基金评委，美国宇航局博士后评委，美国能源部科技企业基金评委等职。