Differential Slicing: Identifying Causal Execution Differences for Security Applications

Noah Johnson-Walls

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2013-77
May 16, 2013

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-77.pdf

A security analyst often needs to understand two runs of the same program that exhibit a difference in program state or output. This is important, for example, for vulnerability analysis, as well as for analyzing a malware program that features different behaviors when run in different environments. In this paper we propose a differential slicing approach that automates the analysis of such execution differences. Differential slicing outputs a causal difference graph that captures the input differences that triggered the observed difference and the causal path of differences that led from those input differences to the observed difference. The analyst uses the graph to quickly understand the observed difference. We implement differential slicing and evaluate it on the analysis of 11 real-world vulnerabilities and 2 malware samples with environment-dependent behaviors. We also evaluate it in an informal user study with two vulnerability analysts. Our results show that differential slicing successfully identifies the input differences that caused the observed difference and that the causal difference graph significantly reduces the amount of time and effort required for an analyst to understand the observed difference.

Advisor: Dawn Song


BibTeX citation:

@mastersthesis{Johnson-Walls:EECS-2013-77,
    Author = {Johnson-Walls, Noah},
    Title = {Differential Slicing: Identifying Causal Execution Differences for Security Applications},
    School = {EECS Department, University of California, Berkeley},
    Year = {2013},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-77.html},
    Number = {UCB/EECS-2013-77},
    Abstract = {A security analyst often needs to understand two runs of the same program that exhibit a difference in program state or output. This is important, for example, for vulnerability analysis, as well as for analyzing a malware program that features different behaviors when run in different environments. In this paper we propose a differential slicing  approach that automates the analysis of such execution differences. Differential slicing outputs a causal difference graph  that captures the input differences that triggered the observed difference and the causal path of differences that led from those input differences to the observed difference. The analyst uses the graph to quickly understand the observed difference. We implement differential slicing and evaluate it on the analysis of 11 real-world vulnerabilities and 2 malware samples with environment-dependent behaviors. We also evaluate it in an informal user study with two vulnerability analysts.  Our results show that differential slicing successfully identifies the input differences that caused the observed difference and that the causal difference graph significantly reduces the amount of time and effort required for an analyst to understand the observed difference.}
}

EndNote citation:

%0 Thesis
%A Johnson-Walls, Noah
%T Differential Slicing: Identifying Causal Execution Differences for Security Applications
%I EECS Department, University of California, Berkeley
%D 2013
%8 May 16
%@ UCB/EECS-2013-77
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-77.html
%F Johnson-Walls:EECS-2013-77