SigGraph: Brute Force Scanning of Kernel Data Structure Instances Using Graph-based Signatures
Zhiqiang Lin, Junghwan Rhee, Xiangyu Zhang, Dongyan Xu, and Xuxian Jiang
$Id: ndss11.t2t, v1.0, last updated %%mtime(%c) Exp $

%! Target:
%! Options: --toc --css-sugar --encoding=iso-8859-1
%! Style: tech.css
%! PreProc:
%! PostProc:
%! include: ''ns10.js''


=== Abstract ===

[[img/ndss11.jpg] img/ndss11.jpg]

Brute force scanning of kernel memory images for finding kernel data structure instances is an important function in many computer security and forensics applications. Brute force scanning requires effective, robust signatures of kernel data structures. Existing approaches often use the value invariants of certain fields as data structure signatures. However, they do not fully exploit the rich points-to relations between kernel data structures. In this paper, we show that such points-to relations can be leveraged to generate graph-based structural invariant signatures. More specifically, we develop SigGraph, a framework that systematically generates non-isomorphic signatures for data structures in an OS kernel. Each signature is a graph rooted at a subject data structure with its edges reflecting the points-to relations with other data structures. Our experiments with a range of Linux kernels show that SigGraph-based signatures achieve high accuracy in recognizing kernel data structure instances via brute force scanning. We further show that SigGraph achieves better robustness against pointer value anomalies and corruptions, without requiring global memory mapping and object reachability. We demonstrate that SigGraph can be applied to kernel memory forensics, kernel rootkit detection, and kernel version inference.




=== Full Paper ===
The full paper can be downloaded here [[PDF file/SigGraph_NDSS11.pdf]]


=== Demo ===
A video clip shows how SigGraph works can be downloaded from [[Demo file/SigGraph.avi]]
---------------------------------------------------------------------------
[HOME index.html]  [SOURCE %%infile]