Reverse Engineering Input Syntactic Structure from Program Execution and Its Applications

doi:10.1109/TSE.2009.54

Return

Reverse Engineering Input Syntactic Structure from Program Execution and Its Applications

2010-09-01

PRE

Zhiqiang Lin *

Xiangyu Zhang

DOI：10.1109/TSE.2009.54

Original

Original request for help

Save

Abstract

En 中文

Program input syntactic structure is essential for a wide range of applications such as test case generation, software debugging, and network security. However, such important information is often not available (e.g., most malware programs make use of secret protocols to communicate) or not directly usable by machines (e.g., many programs specify their inputs in plain text or other random formats). Furthermore, many programs claim they accept inputs with a published format, but their implementations actually support a subset or a variant. Based on the observations that input structure is manifested by the way input symbols are used during execution and most programs take input with top-down or bottom-up grammars, we devise two dynamic analyses, one for each grammar category. Our evaluation on a set of real-world programs shows that our technique is able to precisely reverse engineer input syntactic structure from execution. We apply our technique to hierarchical delta debugging (HDD) and network protocol reverse engineering. Our technique enables the complete automation of HDD, in which programmers were originally required to provide input grammars, and improves the runtime performance of HDD. Our client study on network protocol reverse engineering also shows that our technique supersedes existing techniques.

Keywords:

Input syntactic structure

reverse engineering

control dependence

grammar inference

delta debugging

top-down grammar

bottom-up grammar

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.