On detecting environment sensitivity using slicing.

Modern malware often evades debuggers, virtual machines, and emulators. It is interesting if one can observe their behavior difference using controlled environments. This paper formalizes the notion of environment sensitivity, and proposes two alternative semantics: one based on program trace and the other based on code coverage. Then it tackles the following question: can one minimize an environment sensitive program? The work presents progressive executable slice, a subprogram generated from a partial control but full data dependency closure of a program under study. It shows that a progressive slice can retain trace based environment sensitivity but not the code coverage sensitivity, for which, a special condition is needed for restraining the slice. The saturated trace set of a program is used as a cost indicator for observing its behavior difference. The paper shows that a progressive slice does not necessarily have a lower observation cost than its container program. To address it, a consistency condition is proposed. The paper introduces a reference algorithm for generating progressive slices, and discusses its approximation in practice.